c++ - 从节点和关系生成 block 的算法

Question

我有节点列表和它们之间的线，它看起来像这样:

我需要的是生成 block ，在这种情况下它会是这样的: 区 block 1:1,2,14,11 block 2:2,13,12,14 区 block 3:2,3,4,5,6,12,13 区 block 4:6,7,12 等等……

有人知道如何为此创建算法吗？谢谢

Answer 1

您可以先将每个节点的边按顺时针顺序排序。 (例如，基于键 atan2(dy,dx) 排序，其中 dx,dy 是沿边的 vector 。)

然后以每条边(以及沿边的两个方向)为起点，沿着 block 的逆时针方向跟随边。

要逆时针方向，您会在目标节点的排序列表中找到传入边，并沿着列表中的下一条边退出。

例如，如果您从边 11->14 开始，那么当您到达节点 14 时，您就会知道接下来要走边 14->2(因为节点 14 的边将按顺时针顺序排列 14 ->12、14->11、14->2)。当您到达起始节点时，您已识别出一个区 block 。

您可以在跟随边缘时将边缘标记为已使用，以避免两次生成相同的 block 。 (如果起始边已被标记为在该方向使用，则跳过起始边。)

这也会生成一个由背景区域组成的 block 0。