algorithm - 从一组线中查找封闭（表面）区域

Question

我正在尝试自动“填充”我的代码中完全由行（段）包围的所有区域。

我拥有的是 2D 空间中固定大小 (x,y) 的网格，以及由起点和终点定义的线列表。这些线不一定包含一个空间。

视觉示例 。

我正在寻找的是该区域在此处以不同颜色的蓝色阴影（特别是它们的边界点，因为我正在尝试为这些区域创建网格）

我怎样才能通过算法找到这些区域？

标签： algorithmlinelinear-algebraareasurface

Answer 1

诀窍是找到定义每个区域（多边形）的相交线段的完整电路。

假设线段用字母（A，B，C，...）命名。

我会先建立一个表格，让您按线段查找交点。

A -> B
A -> C
A -> D
B -> A
C -> A
C -> D
D -> A

（在这个例子中，ACD 形成了一个三角形区域，而 B 只是恰好穿过 A 的一条杂散线段。）

选择一条线段，比如 A，并检查它的第一个交点，恰好是线段 B。现在我们开始扫描 B 的交点。B连接回A，完成一个电路，但只有两个步骤，所以它不是一个有效的区域。

由于B没有更多的路口，我们回溯并查看A的下一个路口，也就是和C的路口。C的第一个路口是和A的，完成了一个循环，但是只有两步，所以不是有效区域。但是C的下一个交点是D，而D的第一个交点是A，这样就完成了一个三步循环，所以现在我们有了有效区域，具体来说就是一个三角形。该区域由我们在电路中使用的交叉点定义：Pac、Pcd、Pda。

一旦您探索了 A 的所有可能路径，您将从 B 重新开始。请注意，您会多次找到区域，因此您必须过滤掉重复项。但是您不能完全跳过检查 B，因为它可能是您尚未找到的另一个区域的边缘。