algorithm - 在段和连接器的集合中检测所有闭合路径的最有效方法是什么？

Question

我们有一个由连接器和段组成的数据集。每个段正好有两个连接器，但每个连接器可以属于零个或多个段(即下图中左图中的连接器“A”没有段，而连接器“M”有三个，M-R、M-L 和 M-N。)

It is understood that wherever any lines meet or intersect, there will be a connector so we don't have to worry about even/odd rules, overlapping or partially-enclosed polygons, etc. as they don't apply.

简而言之，我们正在尝试识别所有创建的多边形(右侧图像中的彩色形状)。我相信这可以通过两个步骤完成。



第 1 部分:删除多余的项目

独立连接器(此处为连接器“A”)可以简单地移除，因为它们不能成为形状轮廓的一部分。

引用单个线段(连接器“B”和“E”)的 float 端点也可以删除，因为它们也不能成为形状轮廓的一部分。这也将删除它们的引用段(B-C 和 E-D)。

以递归方式执行上述操作接下来会将“C”识别为端点(因为“B”和 B-C 已被删除)，因此它及其剩余的 C-D 段也可以被删除。在下一次递归传递中，连接器“D”和段 D-F 也将被删除，依此类推。

但是，我还没有找到识别段 H-I 的好方法。也就是说，我认为这可以在多边形检测过程中实现，因为这样的线段只会是复合路径的结果，并且会在一个形状的检测过程中在两个方向上进行跟踪。 (更多关于下面的内容。)

第二步:多边形检测

每个段都可以在两个方向上进行跟踪。例如，连接'O'和'P'的段可以是O-P或P-O。选择顺时针的轨迹方向，O-P 将属于多边形 O-P-Q-N 而 P-O 将属于多边形 P-O-I。

以下逻辑假设跟踪方向为顺时针。

从任何线段开始，在跟踪时，如果您回到起点，您就已经确定了一个潜在的多边形。通过在跟踪时保持航向角度的运行增量(这是航向转动的幅度，不要与简单地添加段之间的角度混淆)，完成后，如果该角度为正，则您已检测到有效的多边形。如果它是负数，则您已检测到一个“包含”多边形，这意味着该多边形包含一个或多个“有效”多边形。整个形状(或多个形状)的外周全都包含多边形。

考虑一个正方形的情况，对角线分成两个三角形。跟踪每个线段两次——每个方向一次——你最终会得到三个可能有效的多边形:一个正方形和两个三角形。三角形将有一个正角 delta 告诉您它们是有效的，但正方形的角 delta 将为负，告诉您这是包含多边形。

Note: A containing polygon can be equal to a valid polygon too. It will just be 'wound' in the opposite direction.

考虑一个简单的三角形。顺时针轨迹将产生有效的多边形。第二次尝试顺时针追踪实际上会产生逆时针追踪，这会给你一个负角增量，告诉你这实际上是形状的轮廓。

Note: You also have to test for other polygons encountered along the way by also testing each point for any previously-encountered point during that shape detection. If you find you've revisited the same point, save off the polygon created since the first encounter of that point, check it's angle. If it's positive, it's a valid polygon (and you're actually currently tracing a containing polygon.) If it's negative, you've detected a containing polygon (in which case you're currently tracing a valid polygon.) Finally, remove all segments on your accumulation stack back to the first instance that point was last encountered and continue on with your detection.

例如，如果您从“J”开始并逆时针追踪，您将经过“I”、“H”、“G”、“F”，然后您将回到“H”。您刚刚发现了一个具有负角的多边形 H-G-F，因此您知道它是一个包含多边形。从堆栈中删除这三个段并继续。现在你将再次点击“我”。在这种情况下，您在此过程中已经访问了同一段，但在另一个方向，因此只需从堆栈中完全删除该段并继续，在 'O' 然后是 'N' 等旁边。您最终将成为回到'J'。

当一个段在两个方向上都被跟踪时，它可以被认为是“使用过的”并且不需要对该段进行进一步的处理。继续处理所有未使用的段。一旦在两个方向上跟踪了所有线段，您就可以确定所有多边形——有效的和包含的——都已找到。

最后，检查每个包含多边形以查看它是否属于任何有效多边形。如果是这样，请将其从创建复合路径的有效多边形中排除。在此处的示例中，包含多边形 H-G-F 包含在有效的青色多边形中，因此应将其排除。请注意，还有一个有效的 H-F-G 多边形，此处标记为红色。

无论如何，这就是我想出的，但我想知道是否有更好/更简单的方法。想法？

Answer 1

提示 :

您的问题具有几何方面(不是纯连通性)，因为面可能不会重叠并且已知很简单。我会推荐一种扫描线方法。

首先清理以丢弃所有 float 端点。

然后考虑一条从上到下移动的水平线，一个顶点一个顶点。在 Seewpline 的每个位置上，它都包含或与多个线段相交。从左到右对所有顶点/交点进行排序，您会得到不重叠的线段。

诀窍是随着扫描线的进行跟踪端点，以便找到区域的左右边界。

在给定的示例中，您将依次考虑点

R  K        J
RM KL G     JI
 M  L GF GH JI
 MN    F GH JI
 MN       H JI
  N  O       I
  NQ   P
   Q

(对表示交叉点)。

由此，您应该能够从连接性考虑重建左/右轮廓

R M | K L
K L M N | G F H | G H | J I (and embedded G F H | G H)
N Q | O P Q
O P | I P

这是通过将现有边的端点和交叉点从扫描线链接到扫描线而获得的图形。



并在清理后，删除中间顶点: