如何处理梯形图中的边重合、相交及其他特殊情况？

一、顶点重合（Vertex Coincidence） #

• 预处理阶段统一顶点：以顶点坐标为键（需处理精度问题，可采用固定小数位取整或整数化转换）构建哈希表，将所有重合顶点映射为同一实例，确保后续处理中边的端点引用统一。
• 构建梯形图时，遇到关联重合顶点的边，直接合并其拓扑关联关系，避免重复计算。

二、边重合（Edge Coincidence） #

分场景处理： #

1. 完全重合边（如两条(0,0)→(0,1)）
   • 预处理去重：以边的两个统一顶点+无向标识为键构建哈希表，仅保留唯一边实例，重复边直接丢弃；若需保留边属性（如权重），可将属性合并至同一条边（如求和、取最大值）。
2. 部分重合边（如(0,0)→(0,1)与(0,-1)→(0,2)）
   • 拆分原边为无重叠线段：先计算重合区间的端点，将原边拆分为(0,-1)→(0,0)、(0,0)→(0,1)、(0,1)→(0,2)三段，再按完全重合边的规则处理拆分后的线段。

三、边相交（Edge Intersection） #

• 先排除已处理的重合边，对剩余边执行相交检测：
  • 采用快速排斥实验+跨立实验的线段相交算法判断是否相交，若为内部相交则计算交点坐标。
  • 将交点作为新顶点加入顶点集合（同步做顶点去重），并将相交的两条边拆分为交点分割后的子线段，确保后续拓扑构建基于无相交的线段。
• 注意：端点相交属于顶点重合范畴，需提前在预处理阶段完成统一。

四、零长度边（Zero Length Edge） #

• 预处理阶段直接过滤：判断边的两个端点坐标在误差范围内完全相同，直接丢弃该边（无拓扑意义）；若业务需保留元数据，可单独存储，不参与梯形图拓扑构建流程。

相关参考资料建议 #

• 《Computational Geometry: Algorithms and Applications》：计算几何经典教材，其中线段处理、平面剖分章节详细覆盖了重合、相交等特殊情况的底层算法逻辑。
• CGAL库平面剖分模块源码：开源计算几何库的实现中包含完整的拓扑异常处理细节，可参考其核心逻辑。
• 《Trapezoidal Maps and Triangulations》专项学术论文：聚焦梯形图构建的研究，部分论文会深入讨论拓扑特殊情况的处理策略。

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