基于线段生成网格图：矩形间rectilinear路径规划问询

核心思路 #

我们的目标是动态维护一个由线段和顶点组成的图结构：从初始边界框线段开始，逐个处理从扩充矩形边中点发射的射线，每新增一条射线时，检测其与已有线段的交点，在交点处拆分已有线段，同时更新图的顶点和边关系，最终得到可用于Dijkstra算法的网格图。

关键数据结构选型 #

• 空间索引（四叉树/线段树）：用来快速定位与新射线可能相交的已有线段，避免暴力遍历所有线段，大幅提升相交检测效率。四叉树更适配2D矩形空间场景，能按区域划分线段，查询时仅检查射线覆盖区域内的线段。
• 顶点哈希表：用坐标元组（如(x, y)）作为键，存储对应的顶点对象，避免重复创建相同坐标的顶点。每个顶点对象维护一个相邻顶点列表，记录直接连通的其他顶点（即图的边）。
• 线段对象：每条线段存储两个端点的引用（指向顶点哈希表中的对象），以及线段的方向、所属来源（如边界框、某矩形的中点射线），方便后续拆分和管理。

逐段构建与细分的算法步骤 #

1. 预处理阶段 #

• 生成两个矩形的扩充矩形，计算它们的最小边界框（绿色框），将边界框的四条边加入初始线段集合。同时在顶点哈希表中创建边界框的四个顶点，为每条边的两个端点建立双向相邻关系。
• 收集所有射线起点：每个扩充矩形的四条边中点，共8个点。

2. 逐个处理射线 #

对每个中点，沿垂直于对应边的方向发射rectilinear射线（比如水平边的中点发射垂直射线，垂直边的中点发射水平射线）：

• 确定射线的延伸范围：从起点出发，直到触及边界框的边或已有线段。
• 用空间索引查询射线覆盖区域内的所有已有线段，逐一进行相交检测。
• 对每个有效交点（位于线段内部，非端点）：
  1. 在顶点哈希表中添加该交点（若不存在）。
  2. 从线段集合中删除原线段，替换为两条新线段：原线段起点到交点、交点到原线段终点。
  3. 更新新线段两端顶点的相邻列表，同时将新线段加入空间索引。
• 将射线从起点到最近交点（或边界框边）的线段加入集合，连接对应的顶点，更新相邻列表。
• 若射线穿过交点后仍未到达边界框，以交点为新起点，重复上述步骤处理剩余射线段。

3. 图结构收尾 #

• 遍历所有顶点，确保相邻列表是双向的（比如顶点A的列表包含B，则B的列表必须包含A）。
• 清理重复边：同一对顶点之间只保留一条边，避免冗余。

优化细节 #

• 精度控制：使用浮点坐标时，设置一个极小的epsilon值（如1e-8），用于判断点是否重合、是否在线段上，避免因浮点误差导致的错误拆分。
• 空间索引动态更新：每次拆分线段后，及时从索引中移除旧线段，添加新线段，保证后续查询的准确性。
• 射线终止优化：一旦射线触及边界框的边，立即停止延伸，无需继续检测后续线段。

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