点坐标轴对齐矩形测试？

我的矩形结构有这些成员： x，y，宽度，高度。点坐标轴对齐矩形测试？

给定一个点x，y 知道x，y是否在矩形内部的最快方法是什么？我会做很多这些，所以速度很重要。

2010-10-08 jmasterx

C或C++快速PtInRect该函数快速pointinrect快一点？再次，你不是写在两个，你在写什么？强制性的：如果速度真的很重要，你会得到尽可能干净的工作，*然后*描述它。 – GManNickG 2010-10-08 20:14:12

你想要严格的内部还是边界可以接受？另外，选择一种语言。 – JoshD 2010-10-08 20:15:27

它是因为c或C++的答案适合我 – jmasterx 2010-10-08 20:16:55

这是怎么了，我通常做。给定一个矩形外的点，这将在4个案例中的3个中进行更少的测试。有时候只有一个测试完成。

if(point.x < rect.x) return false; 
if(point.y < rect.y) return false; 
if(point.x >= rect.x + rect.width) return false; 
if(point.y >= rect.y + rect.height) return false; 
return true;

您使用哪一个应该取决于您是否预计更多的碰撞或更多的失误。

来源

2010-10-08 20:46:59

较少的比较是一个崇高的目标，但不会像其他答案中的&&操作符的短路性质那样实现这一目标吗？ – Arun 2010-10-08 21:21:16

是的，这就是我编辑我的答案的原因，因为我忘记了短路。但我仍然喜欢这样，因为我认为它看起来更干净。你怎么看？ – 2010-10-08 21:27:02

出于好奇，为什么你包括一个矩形的左侧和顶侧，但排除右侧和底部？（在屏幕坐标中）。 – Wodzu 2016-12-01 08:23:23

if (p.x > x && p.y > y && p.x < x+width && p.y < y+height)

这应该只是几个汇编指令。

它假设矩形的x，y总是矩形的最小值坐标。它还会折扣矩形边框上的点。

来源

2010-10-08 20:14:30 JoshD

如果不是逻辑运算符，而是使用按位元的运算符，它可能会变得更快：比较结果非常便宜，我认为即使执行所有这些运算也可能比添加运算更快三个分支。但是，像往常一样，剖析是唯一知道的方法。 – 2010-10-08 20:43:19

在C++（可平凡转换为C）：

bool pointInRectangle(Point const & p, Rectangle const & r) { 
    return 
     ((r.x <= p.x) && (p.x <= (r.x + r.width))) && 
     ((r.y <= p.y) && (p.y <= (r.y + r.height))); 
}

来源

2010-10-08 20:29:23 Arun

这是很多括号:) – JoshD 2010-10-08 20:37:21

@JoshD：那是真的。我永远不会记住优先事项..所以，为了避免我和读者的困惑，我总是放宽括号:)。 – Arun 2010-10-08 20:42:19

但是你非常有信心点算子在加法之前加入：D（对不起，我忍不住自己） – JoshD 2010-10-08 20:47:44

如果您要定位特定的CPU，例如x86，您可以使用SIMD（即SSE）进行非常快速的无分支测试。诀窍是使用4 x 32位整数表示映射到SIMD向量的矩形（它需要大小为16个字节，并且对齐16个字节）。

来源

2010-10-08 21:07:02

在编写比赛时，我发现了两个更好的答案。首先，它使用两个点的坐标，而不是高度/宽度慢，也假设一个点是两个浮点，矩形是四个浮点;对于不同的数据类型，这个逻辑可能需要改变！首先，使用知道Intel SSE指令的编译器，以正确的方式组合&和& & &的测试速度要快很多。这种结合了两种测试为一体，但保持了快速出第二两个测试：

if((p.x>=r.lx)&(p.x<=r.hx)&&(p.y>=r.ly)&(p.y<=r.hy)) 
    ptisinrect=true;

目前，采用128位SSE指令，这是比所有& &的更快编译，但使用256位AVX2设置较慢，即使所有的&的。但是，如果您将程序设置为测试阵列中的许多点，则可以使其完全向量化并显着提高性能（仍然使用SSE而不是AVX或AVX2）。向量化是一种简单的并行化，它有一些严格的要求。例如，循环中不能有短路，并且不能一次保存多个相同的变量。

所以要看看非矢量化代码，查找“计数” ptinrects并退出这个简单的例子，如果足够发现：

for(unsigned a=0;a<n;++a) 
{ 
    if((pp[a].x>=r.lx)&&(pp[a].x<=r.hx)&&(pp[a].y>=r.ly)&&(pp[a].y<=r.hy)) 
    { 
     ++found; 
     if(found>count) 
      return true; 
    }

}

下面的代码的一个例子同样的事情，只向量化搜索0到n ptinrects，但仍然在矩形中找到'count'点时退出。请注意，这个代码可以读取访问32点过去N，所以阵列需要与空间32多分，被分配：

typedef struct ab 
{ 
    int64_t a[4]; 
}; 
typedef struct{ 
union{ 
    ab ab; 
    int8_t o[32]; 
    }; 
}xmmb; 
xmmb o; 
for(unsigned i=0;i<n;i+=32) 
{ 
    for(unsigned a=0;a<32;++a) 
    { 
     o.o[a]=((pp[i+a].x>=r.lx)&(p[i+a].x<=r.hx)&(p[i+a].y>=r.ly)&(p[i+a].y<=r.hy)); 
    } 

    for(unsigned kk=0;kk<4;++kk) 
    { 
     if(o.ab.a[kk]) 
     for(unsigned a=kk<<3;a<(kk+1)<<3;++a) 
     { 
      if(o.o[a]) 
      { 
       if(i+a<n) 
       { 
        ++found; 
        if(found>count) 
         return true; 
       } 
      } 
     } 
    } 
}

即使它是相当奇怪的看着，这个代码更比以前更快例！它正在做的是以矢量并行方式运行ptrect测试，并将真/假存储在32个8位字节的数组中。然后它每次检查8个（因此与4个64位的联合）来保存测试。然后看看任何有真正价值的东西，并将它们添加到计数中。

再说一次，这只适用于128位SSE，并且当编译为256位AVX2时，它现在（feb 2015）较慢，所以请使用开关或编译指示以保持SSE 最后，此代码可能具有语法错误之类，因为它进入到这个格式是不切正粘贴简单：d

标签：在矩形

来源

2015-02-05 09:06:32 floppybunny

点坐标轴对齐矩形测试？

回答

相关问题