Check if a line goes through a polygon in any way

Question

I am making a program that find a path between 2 points on an image (soon to be frame of a video). What I have done is that I use Polygon objects to identify obstacles between the path, and with this polygon objects I go around as necessary. My code is as follows:

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

At the moment, the only obstacles I am using are simple shapes such as rectangles, squares, circles, etc, and I will switch to using the video once everything works fine. The problem occurs when line.crosses(polygon) in the list comprehension in the function getPolygonsInWay returns false when the two parts are the diagonal of the rectangle. I have looked at the documentation but I cannot figure out what to use to make sure I catch this case properly, so I asked this question here.

Edit: As asked, an example polygon, start, and end points are below:

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

With the code above, I get the following path after running getShortestPath(getPaths(start, end, polygons, [])): [(440, 35), (411, 182), (210, 335), (90, 600)]

Answer 1

I found the method line.within(polygon) that checks if the line is inside the passed polygon. I do not know why I did not see it before but now I did. By doing line.crosses(polygon) or line.within(polygon) in the list comprehension if condition, I managed to get a path going around the rectangle. I will now test this with other basic shapes and then unlimitedly test it with what this is being used for.