1

我试图找出最有效/快速的方法将大量凸四边形（四个给定的 x,y 点）添加到数组/列表中，然后检查这些四边形是否在边界内或边界上那些四边形。

我最初尝试使用光线投射，但认为这有点矫枉过正，因为我知道我所有的多边形都是四边形并且它们也是凸的。

目前，我将每个四边形分成两个共享一条边的三角形，然后使用它们的区域检查该点是否在这两个三角形的每一个上或之中。

例如三角形 ABC 和测试点 P。 if (areaPAB + areaPAC + areaPBC == areaABC) { return true; }

这似乎运行得有点慢，因为我需要计算 4 个不同三角形的面积来运行检查，如果四边形的第一个三角形返回 false，我必须再获得 4 个区域。（我在检查中包含了一点 epsilon 以弥补浮点错误）

我希望有一种更快的方法，它可能涉及对一个四边形的点进行单次检查，而不是将其分成两个三角形。

我试图通过将多边形放入数组 [,] 来减少检查次数。添加多边形时，它会检查最小和最大 x 和 y 值，然后使用这些值，将相同的多边形放置到正确的数组位置。根据可用多边形检查点时，它会从列表数组中检索正确的列表。

我一直在搜索类似的问题，我认为我现在使用的可能是确定一个点是否在三角形中的最快方法，但我希望有更好的方法来测试一个四边形总是凸的。我查找的每个多边形测试似乎都是针对具有许多边或不规则形状的多边形进行测试。

感谢您花时间阅读我冗长的问题，了解什么是一个简单的问题。

4

2 回答 2

1

我相信最快的方法是：

1：通过叉积符号找到所有向量对的相互方向（DirectedEdge-CheckedPoint）。如果所有四个符号都相同，则点在里面

加法：对于每条边

EV[i] = V[i+1] - V[i], where V[] - vertices in order
PV[i] = P - V[i]
Cross[i] = CrossProduct(EV[i], PV[i]) = EV[i].X * PV[i].Y - EV[i].Y * PV[i].X

如果点 P 相对于第 i 条边 (V[i] - V[i+1]) 在左半平面内，则 Cross[i] 值为正，否则为负。如果所有 Cross[] 值为正，则点 p 在四边形内，顶点按逆时针顺序排列。f 所有 Cross[] 值为负，则点 p 在四边形内，顶点按顺时针顺序排列。如果值有不同的符号，则点在四边形之外。

如果四元组对于许多点查询是相同的，那么dmuir建议为每条边预先计算均匀线方程。均匀线方程是 a * x + b * y + c = 0。 (a, b) 是边缘的法线向量。这个方程有一个重要的性质：表达式的符号 (a * Px + b * Y + c) 确定半平面，点 P 所在的位置（对于叉积）

2：将四边形拆分为 2 个三角形，并为每个三角形使用向量方法：用基向量表示 CheckedPoint 向量。

P = a*V1+b*V2

当 a,b>=0 且它们的总和 <=1 时，点在内部

两种方法都需要大约 10-15 次加法、6-10 次乘法和 2-7 次比较（我不考虑浮点误差补偿）

于 2012-09-28T05:46:45.720 回答
1

如果您有能力为每个四边形存储其每个边的方程，那么您可以在 MBo 的答案上节省一点时间。

例如，如果四边形的每个边都有一个向内指向的法线向量 N，并且有一个常数 d（对于边上的一个顶点 p 来说是 Np），那么当且仅当 Nx > = d 每条边。因此，每条边有 2 次乘法、1 次加法和 1 次比较，每个点最多需要执行 4 次测试。此技术适用于任何凸多边形。

于 2012-09-28T13:18:40.063 回答