math - 内部有 N 个点的三角形的数量

Question

给定平面上的一些点(最多 500 点)，没有 3 共线。我们必须确定顶点来自给定点并且在它们内部恰好包含 N 个点的三角形的数量。如何有效解决这个问题？朴素的 O(n^4) 算法太慢了。有什么更好的方法吗？

Answer 1

您可以尝试将三角形视为三个半空间的交集。要找到三角形 A、B、C 内的点数，首先考虑 AB 方向上无穷大线一侧的点集。让这些集合 L(AB) 和 R(AB) 为左右的点。类似地，您与其他两条边相同，并构建集 L(AC) 和 R(AC) 以及集 L(BC) 和 R(BC)。

所以ABC中的点数将是L(AB)、L(AC)和L(BC)交点的点数。 (您可能需要根据三角形的方向考虑 R(AB))。

现在，如果我们要考虑全套 500 点。首先取所有点对 AB 并构造集合 L(AB) 和 R(AB)。这将需要 O(n^3) 次操作。

接下来我们测试所有三角形并找到三个集合的交点。如果我们对集合使用一些哈希表结构，那么找到交点就像一个哈希表查找。如果 L(AB) 有 l 个元素，则 L(AC) 有 m 个元素和 L(BC) n 个元素。说 l > m > n。对于 L(BC) 中的每个点，我们需要在 L(AC) 和 L(BC) 中进行查找，这样最多可以进行 2n 次哈希表查找。

考虑几何查找表可能会更快。
将您的整个域划分为一个粗网格，比如 10 x 10 的网格。然后我们可以将每个点放入一个集合 G(i,j) 中。然后我们可以将集合 L(AB) 拆分为每个网格单元。假设称这些集合为 L(AB,i,j) 和 R(AB,i,j)。在测试交叉点时，首先要检查哪些网格单元位于交叉点中。这极大地减少了搜索空间，并且由于每个集合 L(AB,i,j) 包含更少的成员，因此哈希表查找将更少。