如何在绘图中找到无弦循环？

Question

输入数据是由两个或多个二维点组成的线数组：

coordinates = [(x, y, x1, y1, x2, y2, etc.), (x3, y3, x4, y4, etc.)].

这里是所有坐标：https://pastebin.com/raw/uj71Wz0U.

问题是找到图中所有的无弦循环。我们需要考虑到弦不仅可以在图形的点之间绘制，还可以例如从一条线的中间到另一条线的中间绘制。

我的图中只有 15 个这样的循环：

我尝试过使用networkx的无弦循环方法，但我还没有找到专门适合我的情况的方法。

这是一段代码，可帮助绘制我上面指定的坐标处的所有线条：

# Create coordinate lists for each pair of points
x_coords = []
y_coords = []
all_connections = []

for coord_set in coords:
    x_pair = []
    y_pair = []
    connections_pair = []
    for i in range(len(coord_set) // 2 - 1):
        x1, y1 = coord_set[2*i], coord_set[2*i+1]
        x2, y2 = coord_set[2*i+2], coord_set[2*i+3]
        x_pair.extend([x1, x2])
        y_pair.extend([y1, y2])
        connections_pair.append(((x1, y1), (x2, y2))))
        all_connections.append(((x1, y1), (x2, y2))))
    x_coords.append(x_pair)
    y_coords.append(y_pair)

print(all_connections)


# Plot the graph
for i in range(len(x_coords)):
    plt.plot(x_coords[i], y_coords[i], marker='o')

plt.xlabel('X')
plt.ylabel('Y')
plt.title('Line Chart')
plt.grid(True)
plt.show()

Answer 1

假设输入中指定了每条线交点的坐标：

1. 找到所有多边形

- Construct undirected graph. 
      ( Vertices are specified in the input.  Edges are lines between vertices. )
- Construct empty list of polygons
- Loop over every vertex specified in the input
- Check if it is a member of a polygon 
        ( is there a path from the vertex that loops back again to the starting vertex.  
        Any decent graph theory library will give you a method to do this. )
- If polygon is unique, add to list of polygons

2. 找到空多边形

- Loop over vertices
   - Loop over list of polygons
     - IF vertex NOT part of polygon
         - IF vertex INSIDE polygon  
               ( algorithm https://ravenspoint.wordpress.com/2010/06/27/in-or-out/ )
               - REMOVE polygon from list of polygons 
                       ( careful not to invalidate loop iterator )

3. 输出空多边形列表

请注意，如果线 can 交叉而没有输入指定的坐标，则必须检查属于多边形的每对线是否相交（任何计算几何文本将提供算法）并删除两个多边形重叠的）