如何在绘图中查找循环/多边形？

Question

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

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

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

任务是找到图中所有不包含子区域的闭合区域。

只有15个：

我尝试过使用networkx中的循环方法，尝试使用shapely查找多边形，但还没有找到合适的方法。

这是一段代码，可帮助您使用我上面指定的坐标构建所有线条：

# 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. 输出空多边形列表