5

我正在寻找最优化的方法来检测一个点是否在轴对齐的矩形内。

最简单的解决方案需要 4 个分支 (if)，这对性能不利。

4

5 回答 5

8

给定一个段[x0, x1]，当 时，一个点x在段内(x0 - x) * (x1 - x) <= 0。

在二维情况下，您需要执行两次，因此需要两个条件。

于 2012-12-03T14:23:30.037 回答
5

考虑对 XMin-X、X-XMax、YMin-Y、Y-YMax 的值进行 BITWISE-AND 运算并使用得到的符号位。

适用于整数和浮点数。

于 2012-12-03T14:48:14.647 回答
2

我认为无论如何您都需要这四个测试，但是如果您知道该点是否更有可能在矩形内或之外，您可以确保这四个测试仅在最坏的情况下运行。

如果点在里面的可能性更高，你可以做

if ((x>Xmax) || (x<Xmin) || (y>Ymax) || (y<Ymin)) {
 // point not in rectangle
}

否则，做相反的事情：

if ((x<=Xmax) && (x>=Xmin) && (y<=Ymax) && (y>=Ymin)) {
 // point in rectangle
}

我很好奇是否真的会有更好的东西......（除非你可以对矩形边缘的位置做出一些假设，比如它们与 2s 的幂或类似的东西对齐）

于 2012-12-03T14:10:40.357 回答
1

许多架构支持无分支绝对值运算。如果不是，它可以通过乘法来模拟，或者左移一个有符号值并相信特定的“实现依赖”行为。

同样，在 Intel 和 ARM 架构中，操作也很可能是无分支的

((x0<x) && (x<x1))&((y0<y) && (y<y1))

原因是范围检查通常针对序列进行优化：

mov ebx, 1       // not needed on arm
sub eax, imm0    
sub eax, imm1    // this will cause a carry only when both conditions are met
cmovc eax, ebx   // movcs reg, #1    on ARM

(x) 和 (y) 表达式之间的位和也是无分支的。

编辑最初的想法是：

给定测试范围：a<=x<=b，首先定义中点。然后可以用 |(x-mid)| 测试两边 <一个; 乘以因子 B 使 A 为 2 的幂... (x-mid)*B < 2^n 和平方
((x-mid)*B)^2 < 2^2n

该值仅在最低有效 2n 位设置位（如果满足条件）。对范围 y 和 OR 执行相同操作。在这种情况下，必须选择因子 C，以便 (y-midy)^2 缩放到相同的 2^2n。

 return (((x-mid)*B)*(((x-mid)*B) | ((y-mid)*C)*((y-mid)*C))) >> (n*2);

AABB 内部的 x,y 的返回值为 0，外部的 x,y 的返回值为非零。（这里的操作是or，因为人们对 (a&&b) & (c&&d) 的补集感兴趣，即 (!(a&&b)) | (!(c&dd));

于 2012-12-03T14:26:59.227 回答
0

您没有告诉我们您对可能值的范围和所需分辨率的了解，也没有告诉我们您想要优化的标准。

一个解决方案是预先计算一个二维布尔数组（如果你能负担得起的话），你可以查找你的坐标对。花费 1 次乘法（或移位）、1 次加法（用于地址计算）和 1 次内存读取。

或两个一维布尔数组。花费 2 次加法、两次内存读取和 1 次 AND，以及更小的表。

于 2012-12-03T14:43:12.127 回答