java - 我们如何找到三角形内的点数？

Question

我想找到总数。如果给定二维笛卡尔平面中所有三个顶点的 x 和 y 坐标，则位于三角形内部和边界上的点的数量。我正在考虑将三角形封闭在一个矩形内，然后找到直线方程，并将逐个检查点以满足不等式。有没有更好的计算方法来解决这个问题？

请帮我。

Answer 1

您取 3-tringe 边向量的所有组合的叉积。如果结果向量的方向与向量到点 p 和向量到三角形点（A、B 或 C）之一的叉积结果不同，则 p 不在三角形中。（叉积将产生3D）

更详细的解释： http: //www.blackpawn.com/texts/pointinpoly/default.html

Answer 2

查看http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry3上的PointInPolygon描述，以很好地总结测试点是否在多边形中的一般情况。由于您有一个总是凸的三角形，因此这简化为（伪代码）：

for point in test_points:
  //infinity can just be a point outside the bounding box of the triangle
  ray := line from point to infinity 
  intersection_points := 0

  for side in triangle_sides
    isect := intersection ray, side
    intersection_points++ if isect

  return intersection_points %2 == 1