从线段生成格子图

Question

我有两个矩形，我试图在它们之间找到一条视觉上令人愉悦的纯直线路线。

为此，我想生成以下晶格/网格作为图形结构（连接到其他顶点的顶点列表），这样我就可以在其上运行像 Djikstra 那样的寻路算法：

这是通过填充每个矩形以获得一个新矩形（上面的红色和蓝色），并获取这些新矩形（绿色）的边界框来获得的。然后从矩形每条边的中心投射光线并细分这些接触的线。

但是，我无法弄清楚如何以有效的方式生成这个格子作为图形结构。

理想情况下，我正在寻找一种算法和数据结构，允许我逐条线段构建图形线段，细分新线段与它们相交的现有线段（边缘）。

Answer 1

我找到了能够做到这一点的isect库。

它获取线路列表并查找所有交叉点，返回交叉点列表以及从每个交叉点到其他交叉点的线路。

使用此输出可以轻松创建一个图形，其中节点是交点，每个交点的线是边。

同一作者甚至有一个 图形库 和 Djikstra's/A* 路径查找库 用于他们的图形。