我正在折腾一个机器人割草机的路径规划算法，目标是让它覆盖指定区域内的所有草地，同时避开障碍物或者限制区域。目前我用Python的Shapely库来定义区域的几何形状——蓝色区域是待割草的范围，红色是不能进入的限制区域。

我当前的实现思路是：在区域的边界范围内生成等间距的平行线，然后在这些线与障碍物或地图边界相交的位置，把线切割成小段，效果就像下面这张图展示的那样：

得到这些线段之后，我打算把区域、障碍物的顶点，再加上所有的交点，都转换成图的节点，让这个图能准确体现每个节点之间的邻接关系。之后我还会做一个遍历算法，确保每个节点至少被访问一次。

现在我想请教的是：有没有一种简洁的方法，能把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)

备注：内容来源于stack exchange，提问作者Tomasm64