如何获取每个封闭区域边界的坐标？

Question

我有一组坐标，这些坐标组成了一个图形：

我的任务是找出所有封闭物体的边界坐标。总共有15个封闭的物体。我该如何在AutoCAD中实现这个功能？或者用Python来做。

输入的数据量很大，所以我只展示一下数据的格式 - coordinates_list = [[x, y, z, x1, y1, z1], [x2, y2, z2, x3, y3, z3] 等等]。

我尝试在AutoCAD中使用 _-BOUNDARY 命令，但这个命令不管用，因为它无法读取坐标。

在Python中，我尝试使用深度优先搜索（DFS）算法，但它总是找到的物体数量比较少。

Answer 1

我觉得你需要的东西叫做循环基，不过我不是百分之百确定。你可以试试用networkx这个Python库来构建循环基，具体可以参考这个例子。从算法的角度来看，它大致是这样工作的：

1. 首先构建一个生成树。在这个树中，会有一些边是缺失的。
2. 然后遍历每一条缺失的边，构建一个循环，把它加到树中。每一个这样的循环都会成为循环基的一部分。

我不太确定你正在解决的问题，比如你是需要一个基，还是一个最小基，或者是图中所有循环的完整列举，但很可能你可以通过同样的networkx库找到解决方案。

Answer 2

正如@CaptainTrunky提到的，在这种情况下，你需要使用networkx库中的cycle_basic。我一开始没有得到想要的结果，因为区域的边界显示得不完整。为了让它们正确显示，你需要在最后重复第一个点：

coordinates = [(x1, y2, x2, y2), (x2, y2, x3, y4), etc.].

point_lists = [[pair for pair in zip(line[::2],line[1::2])] for line in coordinates]
edges = [segment for point_list in point_lists for segment in zip(point_list[::-1], point_list[1:])]
G = nx.from_edgelist(edges)

# cycle_basis
cycle_basis = nx.cycle_basis(G)
print("cycle_basis: =", len(cycle_basis)))
for cycle in cycle_basis:
    cycle.append(cycle[0])
    print(cycle)