平面点集生成无交叉无重复点三角形的实现思路咨询

核心算法选型 #

你的需求本质是平面点集的无交叉三角剖分，最优选择是Delaunay三角剖分，该算法天然保证生成的三角形无交叉、所有点都被覆盖、不会出现重复使用点的问题，是工业界通用的同类问题解决方案。

分步实现逻辑 #

• 第一步：点集预处理
  先拆分输入点集的坐标与标签，提取所有点的x、y数值存入坐标数组，同时建立索引到标签的映射关系，方便后续将算法输出的索引转换为你需要的A、B等字符标识。
• 第二步：执行三角剖分
  两种实现路径可选：
  1. 快速实现（推荐）：直接调用成熟的第三方库完成计算，Python场景下可使用scipy.spatial.Delaunay接口，输入坐标数组后可直接返回所有三角形的顶点索引，不需要自行实现复杂的几何计算逻辑。
  2. 手动实现：如果需要自行编写算法逻辑，可选择增量式Delaunay剖分方案：
     • 先构造一个能覆盖所有输入点的超大外接三角形作为初始剖分结构
     • 逐个将输入点插入现有剖分：找到包含当前点的三角形，将其拆分为3个小三角形，之后校验新生成的边是否满足Delaunay空圆特性，不满足则翻转边调整，直到所有边符合要求
     • 全部点插入完成后，删除所有包含初始超大三角形顶点的三角形，剩余结果即为符合要求的剖分
• 第三步：结果转换与校验
  把算法输出的顶点索引替换为对应的字符标签，即可得到你要求的triangles输出格式。可额外增加校验逻辑：编写线段相交判断函数，遍历所有三角形的边确认无交叉，同时统计所有点的出现次数确认无遗漏。

示例代码（Python） #

from scipy.spatial import Delaunay
import numpy as np

# 输入点集
points = [
    (5, 6, 'A'),
    (5, -8, 'B'),
    (-2, 2, 'C'),
    (-10, 4, 'D'),
    (8, 1, 'E'),
    (-8, 8, 'F'),
    (2, 7, 'G')
]

# 预处理坐标与标签
coords = np.array([(p[0], p[1]) for p in points])
label_map = [p[2] for p in points]

# 执行Delaunay三角剖分
delaunay_res = Delaunay(coords)

# 转换为要求的输出格式
triangles = [[label_map[idx] for idx in simplex] for simplex in delaunay_res.simplices]
print(triangles)

运行上述代码可直接输出符合要求的三角形集合，剖分结果天然无交叉、所有点均被使用。

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