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

Question

我们有一个由连接器和段组成的数据集.每个段都有两个连接器,但每个连接器可以属于零个或多个段(即左侧图像中的连接器"A"没有段,而连接器"M"有三个,MR,ML和MN.)

可以理解,只要任何线条相交或相交,就会有连接器,因此我们不必担心偶数/奇数规则,重叠或部分封闭的多边形等,因为它们不适用.

简而言之,我们试图识别所有创建的多边形(右图中的彩色形状).我相信这可以分两步完成.

第1部分:删除多余的物品

独立连接器(这里的连接器'A')可以简单地移除,因为它们不能成为形状轮廓的一部分.

引用单个段(连接器"B"和"E")的浮动端点也可以被移除,因为它们也不能成为形状轮廓的一部分.这也将删除他们引用的段(BC和ED).

递归地执行上述操作将接下来将'C'识别为端点(因为'B'和BC已被移除),因此它和它的剩余段CD也可以被移除.在下一个递归传递中,连接器"D"和段DF也将被移除,等等.

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

第2步:多边形检测

每个段可以在两个方向上跟踪.例如,连接"O"和"P"的段可以是OP或PO.选取顺时针的跟踪方向,OP将属于多边形OPQN,而PO将属于多边形POI.

以下逻辑假设顺时针方向.

从任何线段开始,当跟踪时,如果返回到起点,则已识别出潜在的多边形.通过在你追踪时保持你的航向角度的运行增量(这是你的航向转动多少并且不要与简单地在段之间添加角度混淆),完成后,如果该角度是正的,你已经检测到有效多边形.如果它是负数,则表示您检测到"包含"多边形,这意味着包含一个或多个"有效"多边形.整个形状(或多个形状)的外周都包含多边形.

考虑方形的情况,对角线分为两个三角形.跟踪每个段两次 - 每个方向一次 - 最终会得到三个可能有效的多边形:一个正方形和两个三角形.三角形将具有正角度增量,告诉您它们是有效的,但是正方形的角度增量将为负,告诉您包含多边形.

注意:包含多边形也可以等于有效多边形.它只是在相反的方向"伤口".

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

注意:您还必须测试在此过程中遇到的其他多边形,还要测试形状检测期间任何先前遇到的点的每个点.如果您发现重新访问了相同的点,请保存自第一次遇到该点以来创建的多边形,检查它的角度.如果它是正数,则它是一个有效的多边形(并且您实际上当前正在跟踪包含多边形.)如果它是负数,则您检测到包含多边形(在这种情况下,您当前正在跟踪有效多边形.)最后,全部删除累积堆栈上的段返回到上次遇到该点的第一个实例,并继续进行检测.

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

当在两个方向上跟踪某个段时,可以将其视为"已使用",并且不需要对该段进行进一步处理.继续处理所有未使用的段.一旦在两个方向上跟踪了所有段,您就可以确定已找到所有多边形 - 有效和包含 - .

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

无论如何,这就是我想出来的,但我想知道是否有更好/更简单的方法.思考？

Answer 1

暗示：

您的问题具有几何方面（不是纯粹的连通性），因为面可能不会重叠并且已知很简单。我建议采用扫描线方法。

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

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

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

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

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

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

清理后，删除中间顶点：