平面图中空三角形的高效生成与计数算法咨询

你提到的暴力枚举所有三点组合、再逐点判断三角形内部是否含其他点的方案，时间复杂度为O(n⁴)，点集规模超过100的时候就会出现明显的性能瓶颈，目前工程界通用的高效实现思路如下：

首选方案：极角排序+双指针增量扫描 #

这个方案实现难度低、常数小，是绝大多数场景下的最优选择，整体时间复杂度为O(n² log n + T)，其中T是点集包含的空三角形总数，已经非常接近理论效率下界：

• 逐次遍历点集中的每个点p_i，将其作为所有待枚举空三角形的固定公共顶点，总共执行n轮遍历。
• 对每一个固定的p_i，把剩下的n-1个点按照相对于p_i的极角做升序排序，极角相同的点按照到p_i的距离从小到大排序。为了方便处理极角跨0度的循环边界，把排序后的点列表复制一份拼接在原列表末尾，得到长度为2(n-1)的线性序列，不需要额外实现环形数组逻辑。
• 对极角序列里的每个点p_j，维护一个单调移动的指针k，初始值为j+1：
  • 顺着极角递增的方向移动k，只要三角形p_i p_j p_k内部不包含其他点，就记录这个空三角形；
  • 一旦发现点落在三角形内部/边上，立刻停止移动k——由于极角有序，k之后的点和p_i、p_j构成的三角形必然包含当前这个点，不可能是空三角形，不需要继续往后判断。
• 因为双指针只会顺着序列单向移动、不会回退，每一轮固定p_i的扫描和三角形记录总开销为O(n + t_i)，其中t_i是以p_i为顶点的空三角形数量，所有轮次的t_i求和就是总空三角形数T。加上每轮排序的O(n log n)开销，整体固定开销仅为O(n² log n)，没有多余的冗余判断。

复杂度说明 #

不存在时间复杂度显著低于O(n² log n + T)的枚举算法：

• 最坏情况下（所有点处于凸位置），任意三点构成的三角形都是空三角形，T=C(n,3)=O(n³)，这时候任何枚举算法都必须花O(n³)时间输出所有结果，不可能有亚立方级别的枚举方案。
• 如果你的需求只是统计空三角形的总数、不需要输出每个三角形的顶点，可以基于Delaunay三角剖分把时间复杂度压到O(n²)，但这个方案无法直接枚举所有空三角形。

实现注意事项

• 所有位置判断统一用整数叉积实现，不要用浮点数计算极角、点到直线的距离，避免浮点精度误差：判断点的相对极角位置、判断点是否在三角形内部，都可以通过叉积的符号直接判定，不需要做开方、三角函数等耗时运算。
• 三点共线构成的退化三角形面积为0，不属于有效空三角形，极角排序时按距离排序的步骤就是为了提前过滤这类共线情况，碰到共线点直接跳过即可。
• 扫描时要保证p_i p_j到p_i p_k的张角不超过180度，避免重复枚举同一个三角形。

内容的提问来源于stack exchange，提问作者byteherder