testing - 检查点是否在凸四边形内或上的最有效方法

Question

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

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

目前，我将每个四边形拆分为共享一条边的两个三角形，然后使用它们的面积检查该点是在这两个三角形上还是在这两个三角形中。

例如三角形 ABC 和测试点 P。如果(areaPAB + areaPAC + areaPBC == areaABC){ 返回真；

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

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

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

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

感谢您花时间阅读我冗长的问题，其实这是一个很简单的问题。

Answer 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 * P.x + b * Y + c) 确定半平面，P点所在的位置(作为叉积)

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

P = a*V1+b*V2

当a,b>=0且它们的和<=1时，点在里面

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