algorithm - 快速计算三角形内的点

Question

我需要找出给定列表中三角形内的点数。这里的问题是，最多可以有一百万个点。

我尝试了一种简单的方法:如果三角形的面积等于通过一次取三角形的 2 个点和要检查的点形成的 3 个三角形的面积之和，则其内部。这没有任何精度错误，因为我没有除以二来求面积。

但我需要更快的东西。目标是速度。是否可以通过某种预处理来加快速度，忽略基于某些标准或类似内容的某些点？

编辑:忘记添加关键细节。积分一旦给出，即为固定。然后点是静态的，需要检查多达一百万个三角形...

编辑 2:事实证明，一个好的(也许也是最佳的)方法是使用线扫描。尽管如此，还是感谢您的回答!

Answer 1

根据计算几何学，最快的方法是通过重心坐标变换。如果你有一个固定的三角形和许多测试点，那么这种方法会特别快，因为一旦你计算出三角形的 3 个点的重心坐标，你就完成了大部分工作。这是完整的算法，其中 ABC 是三角形，P 是被测点:

// Compute vectors        
v0 = C - A
v1 = B - A
v2 = P - A

// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)

// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom

// Check if point is in triangle
return (u >= 0) && (v >= 0) && (u + v < 1)

这里的重心坐标是相对于 A 计算的，但 B 或 C 也可以。

要测试其他点，您只需重新计算 v2、dot02、dot12、u 和 v。invDenom 等数量保持不变。