内有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) 包含更少的成员，因此哈希表查找也会更少。