Check if a line passes through a polygon in any way

Question content

I'm making a program that can find the path between two points on an image (soon to be a video frame). What I do is use a polygon object to identify obstacles between paths and use that polygon object to get around as needed. 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

Currently the only stumbling blocks for me to use are simple shapes like rectangles, squares, circles, etc. I will switch to video once everything works fine. The problem occurs when the list comprehension line.crosses(polygon) in function getpolygonsinway returns false when the two parts are diagonals of a rectangle. I've looked at the documentation but I don't know what to use to make sure I'm capturing this case correctly, so I'm asking the question here.

Edit: As requested, sample polygons, start points, and end points are as follows:

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

Using the above code, run getshortestpath(getpaths(start, end, polygons, [])) and get the following path: [(440, 35), (411, 182), (210, 335), (90, 600)]

Correct answer

I found the line.within(polygon) method which checks if the line is inside the passed polygon. I don't know why I didn't see it before, but now I do. I managed to get the path around the rectangle by doing line.crosses(polygon) or line.within(polygon) in a list comprehension if condition. I'm going to test it now with other basic shapes and then ad infinitum to test its uses.

The above is the detailed content of Check if a line passes through a polygon in any way. For more information, please follow other related articles on the PHP Chinese website!