使用形状的几何点

Question

当前的方法是在区域边界之间定期生成平行线，然后将它们切成段与障碍物或地图边界相交的段。这是一个可以说明这一点的图像。

我有线段，我想使用该区域的地图上的每个点，障碍物和相交的分子变成图表上的节点。该图应忠实地代表每个点的邻接。之后，我计划制作一种至少一次访问每个节点的遍历算法。 我想知道出于我的目的，是否有一种简洁的方法可以将几何特征从Shapely转换为连接的图。 这里是为割草区域和相交线生成几何形状的相关代码：

import numpy as np
from shapely.geometry import Point, Polygon, LineString, MultiLineString, GeometryCollection

def generate_intersections(areaCoords, obstacleCoords, spacing = 1.0):
    # Create Shapely polygons
    area = Polygon(areaCoords)
    obstacle = Polygon(obstacleCoords)
    map = area.difference(obstacle)

    # Obtain bounding box
    minX, minY, maxX, maxY = area.bounds
    
    # Generate parallel lines within bounding box
    lines = []
    y = minY
    while y <= maxY:
        lines.append(LineString( [(minX,y),(maxX,y)] ))
        y += spacing
    
    # Cut lines where they intersect with Boundaries/Obstacle,
    intersections = []

    for line in lines:
        parallel = []
        intersection = line.intersection(map)

        if intersection.is_empty:
            continue
        
        # Line intersects with boundaries only
        if isinstance(intersection, LineString):
            coords = list(intersection.xy)
            parallel.append(coords)

        # Line intersects with obstacle and boundaries
        elif isinstance(intersection, (MultiLineString, GeometryCollection)):
            for g in list(intersection.geoms):
                parallel.append(list(g.xy))
        
        intersections.append(parallel)

    return intersections

if __name__ == "__main__":
    # Polygon Coordinates
    areaCoords = [(2,0),(14,0),(14,12),(2,12)]
    obstacleCoords = [(4,5),(9,5),(9,9),(4,9)]

    # Get intersecting points
    intersections = generate_intersections(areaCoords,obstacleCoords,2.0)

宣布割草区域（蓝线）和障碍物（红线）是多边形的，所有边缘严格垂直或水平，如您所示：

可以连接一对点的三种方式（即图之间将具有边缘）。

Answer 1

点位于定义区域多边形的边缘，并且具有相同的x坐标和y坐标，这些坐标因生成的线（橙色）之间的间距而有所不同。

一个点位于割草区域的边缘，另一个在障碍物的边缘，它们都具有相同的坐标，并且它们之间的线段不会与障碍物相交。

1. 因此，算法看起来像这样：

2.  - LOOP P1 over all points
      - LOOP P2 over all points > P1
         - If P1,P2 satisfy any one of the 3 ways described above
               - Add edge between P1 and P2.