JavaScript实现多边形三角化：平面扫描算法的边检测问题

一、平面扫描法的O(n log n)交点检测优化 #

你之前的O(n²)遍历所有边的方法，问题在于重复检查了大量与当前竖线无关的边。平面扫描算法能做到O(n log n)复杂度，核心是靠**事件点队列（EPQ）和活性边列表（AEL）**两个数据结构：

核心流程调整 #

1. 预处理边：把每条多边形边的两个端点按x坐标从小到大排序，记录边的端点坐标（用于后续计算交点）。
2. 初始化数据结构：
   • 事件点队列：将所有多边形顶点按x坐标升序排列（x相同时按y坐标排序）。
   • 活性边列表：初始为空，用来维护当前扫描线（竖线）正在穿过的多边形边。
3. 处理每个事件点（顶点(x1,y1)）：
   • 先清理AEL：移除所有右端点x等于x1的边（这些边不再被当前竖线穿过）。
   • 找交点：直接计算AEL中每条边与竖线x=x1的交点y值。对于简单多边形，竖线从顶点出发只会有一个有效穿出交点（因为不自交、无孔洞），筛选出这个交点即可。
   • 更新AEL：将当前顶点关联的两条邻边（前一条和后一条边）加入AEL，加入时保持AEL按交点y值排序（保证后续操作的log n复杂度）。

AEL的插入、删除、查找操作可以用有序数组结合二分查找实现（JavaScript原生即可完成），每次操作复杂度O(log n)，总共有n个事件点，整体复杂度就降到了O(n log n)。

二、更简便的多边形三角化方案 #

如果不是必须实现扫描线-梯形分割的流程，**耳切法（Ear Clipping）**是更适合JavaScript实现的方案，逻辑直观，代码量小：

耳切法核心步骤 #

1. 遍历多边形的每个顶点，判断是否为“耳”：
   • 耳的判定条件：顶点是凸顶点（内角<180°），且该顶点与前后相邻顶点组成的三角形内部，不包含多边形的其他顶点。
2. 切割耳：找到一个耳后，将对应的三角形加入三角化结果，然后从多边形顶点列表中移除该耳顶点。
3. 重复上述步骤，直到多边形仅剩3个顶点（最后一个三角形）。

现成工具库推荐 #

如果不想手动实现，JavaScript生态里有成熟的轻量库：

• earcut.js：专门针对简单多边形的高效耳切法实现，体积小、速度快，直接通过npm安装使用：

  import earcut from 'earcut';
  
  // 顶点格式：[x0,y0, x1,y1, ..., xn,yn]
  const polygonVertices = [0, 0, 10, 0, 12, 5, 8, 10, 0, 8];
  // 得到三角化后的顶点索引数组（每三个索引对应一个三角形）
  const triangleIndices = earcut(polygonVertices);
  

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