我正在尝试找出最有效/快速的方法来将大量凸四边形(四个给定的 x,y 点)添加到数组/列表中，然后检查这些四边形是否有一个点在或在这些四边形的边界上。
我最初尝试使用光线转换，但认为这有点矫枉过正，因为我知道我的所有多边形都是四边形，而且它们也都是凸面。
目前，我将每个四边形分成两个共享边的三角形，然后使用它们的面积检查该点是否位于这两个三角形上或其中。
例如 三角形ABC和测试点P。 if (areaPAB +areaPAC+areaPBC==areaABC) { 返回 true; }
这似乎运行得有点慢，因为我需要计算 4 个不同三角形的面积来运行检查，如果四边形的第一个三角形返回 false，我必须再获得 4 个区域。 (我在检查中包含了一点 epsilon，以弥补浮点错误)
我希望有一种更快的方法，可能需要对一个点与四边形进行一次检查，而不是将其分成两个三角形。
我尝试通过将多边形放入数组[,]来减少检查次数。添加多边形时，它会检查最小和最大 x 和 y 值，然后使用这些值将相同的多边形放置到正确的数组位置中。当根据可用多边形检查点时，它会从列表数组中检索正确的列表。
我一直在搜索类似的问题，我认为我现在使用的可能是确定点是否在三角形中的最快方法，但我希望有更好的方法来测试始终是凸的四边形。我查找的每个多边形测试似乎都是针对具有许多边或不规则形状的多边形进行测试。
感谢您花时间阅读我的冗长问题，这实际上是一个简单的问题。
最佳答案
我认为最快的方法是:
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 在四边形内部，顶点按逆时针顺序排列。如果所有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 次比较(我不考虑浮点误差补偿)
关于testing - 检查点是否位于凸四边形内或凸四边形上的最有效方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12629335/