拖拽顶点时防止多边形边相交的算法选型咨询

以下是几种实用的算法方案，可在拖拽红色顶点时避免多边形边自相交：

• 局部碰撞检测与约束修正
  这是最直接的方案，核心是实时监控拖拽顶点关联边的相交情况，并限制顶点移动范围：

  1. 拖拽红色顶点V_i时，先获取其相邻的两个顶点V_{i-1}和V_{i+1}（多边形闭合，首尾顶点互相关联）。
  2. 生成两条待检测边：E1 = (V_{i-1}, V_i)、E2 = (V_i, V_{i+1})。
  3. 遍历多边形中除E1、E2及它们的相邻边（避免误判端点接触）之外的所有边，用跨立实验（线段相交检测的经典方法）检查E1、E2是否与这些边相交。
  4. 一旦检测到相交，计算V_i的可行移动区域（即移动后不会导致边相交的区域），将拖拽位置限制在该区域内；或者直接将顶点拉回到最近的无相交位置。

• 保持多边形凸性（限凸多边形场景）
  如果需求是维持凸多边形形态，这种方案能从根源避免自相交：

  1. 拖拽顶点时，实时计算多边形所有内角的角度。
  2. 当发现当前拖拽的顶点所在内角即将超过180°（变为凹角），或移动后会出现凹点时，限制顶点的移动方向，强制保持所有内角为凸角。
  3. 结合线段相交检测做双重保障，因为凸多边形本身不会出现自相交情况。

• 基于三角剖分的约束
  通过维护多边形内部三角剖分的合法性，间接保证多边形边不相交：

  1. 初始状态下对多边形进行合法三角剖分（比如Delaunay三角剖分）。
  2. 拖拽顶点时，更新与该顶点关联的所有三角形，检查是否出现三角形翻转、退化或相交的情况。
  3. 若出现异常，调整顶点位置，或对局部区域重新进行三角剖分，确保所有三角形保持合法，进而保证原多边形边无相交。

• 贪心式顶点重排序（适用于允许调整顶点顺序的场景）
  如果不需要固定顶点的环绕顺序，可通过重排序顶点快速修正相交问题：

  1. 拖拽顶点后，检查多边形是否存在自相交边。
  2. 若存在，以多边形重心为参考点，计算所有顶点的极角，按极角从小到大重新排序顶点，生成新的简单多边形。
  3. 这种方法能快速将相交多边形修正为无相交状态，适合对顶点顺序无严格要求的场景。

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