检查一条线是否以任何方式穿过多边形

Question

我正在制作一个程序，可以找到图像上两点之间的路径（很快就会成为视频帧）。我所做的是使用多边形对象来识别路径之间的障碍物，并使用该多边形对象根据需要绕过。我的代码如下：

SimplePoint = tuple[int, int]

def getPolygonsInWay(start: SimplePoint, end: SimplePoint, polygons: list[Polygon]) -> list[Polygon]:
    line = LineString([start, end])
    polygonsInWay = [polygon for polygon in polygons if line.crosses(polygon)]  # make sure line.crosses() doesnt return true if the starting point is on the polygon
    return polygonsInWay

def getPaths(start: SimplePoint, end: SimplePoint, polygons: list[Polygon], prev_points: list[SimplePoint] = []) -> list[list[SimplePoint]]:
    polygonsInWay = getPolygonsInWay(start, end, polygons)
    if not polygonsInWay:
        return [[start, end]]

    closestPolygon = closestPolygonToPoint(start, polygons)
    xyValsOld = closestPolygon.exterior.xy
    xyVals = []

    for i in range(len(xyValsOld[0])):
        xyVals.append((xyValsOld[0][i], xyValsOld[1][i]))

    xyVals = list(set(xyVals)) # remove duplicates

    polXVals = [val[0] for val in xyVals]
    polYVals = [val[1] for val in xyVals]

    okPoints = []

    for i in range(len(polXVals)):
        if start == (polXVals[i], polYVals[i]):
            continue
        if int(polXVals[i]) != polXVals[i] or int(polYVals[i]) != polYVals[i]:
            continue
        if (int(polXVals[i]), int(polYVals[i])) in prev_points:
            continue
        if closestPolygon not in getPolygonsInWay(start, (polXVals[i], polYVals[i]), polygons): #and closestPolygon not in getPolygonsInWay((polXVals[i], polYVals[i]), end, polygons):
            okPoints.append((int(polXVals[i]), int(polYVals[i])))

    paths = [[start] for _ in range(len(okPoints))]

    for i in range(len(okPoints)):
        point = (okPoints[i][0], okPoints[i][1])
        paths[i].extend(getShortestPath(getPaths(point, end, polygons, prev_points + [point]), point, end))

    return paths

目前，我使用的唯一障碍是简单的形状，如矩形、正方形、圆形等，一旦一切正常，我将改用视频。当函数

line.crosses(polygon)

中的列表推导式中的

getPolygonsInWay

在两个部分是矩形的对角线时返回 false 时，就会出现问题。我已经查看了文档，但我不知道用什么来确保我正确地捕获这个案例，所以我在这里问了这个问题。

编辑：按照要求，示例多边形、起点和终点如下：

polygon = Polygon([[411, 182], [411, 335], [210, 335], [210, 182]])
start = (440, 35)
end = (90, 600)

使用上面的代码，运行后得到以下路径

getShortestPath(getPaths(start, end, polygons, []))

：

[(440, 35), (411, 182), (210, 335), (90, 600)]

Answer 1

我相信你感兴趣的是

line.intersects(polygon)

:

如果对象的边界或内部以任何方式与另一个对象的边界或内部相交，则返回 True。

根据文档。

附注如果您的代码片段提供了示例多边形和线条实例来说明您的问题，而不是您的

getPaths

逻辑，将会有所帮助。