1

我想将顶点和边的现有数据分成两个或多个未连接的图。我想举以下例子:

想象两个六边形彼此重叠,但位于不同的 Z 轴上。

六边形 1 有以下顶点 A(0,0,1), B(1,0,2), C(2,1,2), D(1,2,1), E(0,2,1) , F(-1,2,1)。连通性如下:AB、BC、CD、DE、EF、FA。图 1 的这一部分,因为所有顶点都在该层中连接。

Hexagon2有以下顶点A1(0,0,6), B1(1,0,7), C1(2,1,7), D1(1,2,8), E1(0,2,7), F1(-1,2,6)。连接方式如下:A1-B1、B1-C1、C1-D1、D1-E1、E1-F1、F1-A1。这是图 2 的一部分

我的数据采用以下形式:我可以用来形成图形的顶点列表和边列表。我想消除图 2 并仅将图 1 的顶点和连接性提供给我的算法的多边形确定部分。我的真实数据包含大约 1000 个连接的多边形,如图 1 和大约 100 个(面积大得多)多边形,如图 2。我想消除图 2。

4

1 回答 1

2

您描述的问题与连接的组件有关。

Python Networkx模块具有处理此类图形问题的功能。您正在寻找返回所有组件的connected_components函数,然后您可以选择适当的组件(可能由顶点数决定)。

于 2012-10-25T10:57:19.150 回答