algorithm - 从一组线中查找封闭(表面)区域

Question

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

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

Visual Example.

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

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

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，因为它可能是您尚未找到的另一个区域的边缘。