PHP前端开发

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

百变鹏仔 1天前 #Python
文章标签 多边形
问题内容

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

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 polygonsinwaydef 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

目前,我使用的唯一障碍是简单的形状,例如矩形、正方形、圆形等,一旦一切正常,我将改用视频。当两个部分是矩形的对角线时,函数 getpolygonsinway 中的列表理解中的 line.crosses(polygon) 返回 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)]


正确答案


我找到了 line.within(polygon) 方法,该方法检查该线是否位于传递的多边形内部。我不知道为什么我以前没有看到它,但现在我看到了。通过在列表理解 if 条件中执行 line.crosses(polygon) 或 line.within(polygon) ,我设法获得了围绕矩形的路径。我现在将使用其他基本形状来测试它,然后无限地测试它的用途。