我正试图找出最有效/最快速的方法，将大量凸四边形(四个给定的x，y点)添加到数组/列表中，然后对照这些四边形检查一个点是否在这些四边形的边界内或边界上。
我最初尝试使用光线投射，但认为这有点过头了，因为我知道我所有的多边形都是四边形，而且它们都是凸的。
目前，我正在将每个四边形拆分为共享一条边的两个三角形，然后使用它们的面积检查该点是否在这两个三角形中的每一个上。
例如三角形ABC和测试点P。if(areaPAB+areaPAC+areaPBC==areaABC)｛返回true；｝
这似乎运行有点慢，因为我需要计算4个不同三角形的面积来运行检查，如果四边形的第一个三角形返回false，我必须再获得4个面积。(我在检查中包含了一点ε，以弥补浮点错误)
我希望有一种更快的方法，可以将一个点与四边形进行单次检查，而不是将其拆分为两个三角形。
我试图通过将多边形放入数组[，]来减少检查次数。添加多边形时，它会检查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次比较(我不考虑浮点误差补偿)
如果你有能力存储每个四边形的每个边的方程，那么你可以在MBo的答案上节省一点时间。
例如，如果四边形的每条边都有一个向内指向的法向量N，并且有一个常数d(对于边上的一个顶点p来说是N.p)，那么点x就在四边形中，当且仅当每条边的N.x>=d。因此，这是两次乘法，每边一次加法和一次比较，每个点最多需要执行4次测试。这种技术适用于任何凸多边形。