时间戳

首页 > 解决方案 > 网格上节点的相互可见性

python-3.x - 网格上节点的相互可见性

问题描述

我有一个简单的网格，我需要检查两个节点的相互可见性。所有墙和节点的协调都是已知的。我需要检查两个节点的相互可见性。

我尝试过使用向量，但没有得到可接受的结果。该算法有效，但它不适合我的程序，因此我必须对数据进行转换以获得可接受的结果。

我将此代码用于检查节点以实现相互可见性：

def finding_vector_grid(start, goal):
    distance = [start[0]-goal[0], start[1]-goal[1]]
    norm = math.sqrt(distance[0] ** 2 + distance[1] ** 2)
    if norm == 0: return [1, 1]
    direction = [(distance[0]/norm), (distance[1]/norm)]
    return direction

def finding_vector_path(start, goal):
    path = [start]
    direction = finding_vector_grid((start[0]*cell_width, start[1]*cell_height),
        (goal[0]*cell_width, goal[1]*cell_height))
    x, y = start[0]*cell_width, start[1]*cell_height
    point = start

    while True:
        if point not in path and in_map(point):
            path.append(point)
        elif not in_map(point):
            break

        x -= direction[0]
        y -= direction[1]
        point = (x//cell_width, y//cell_height)
    return path

def vector_obstacles_clean(path, obstacles):
    result = []
    for node in path:
        if node in obstacles:
            result.append(node)
            break
        result.append(node)
    return result

例如：

path =  finding_vector_path((0, 0), (0, 5))
path = vector_obstacles_clean(path, [(0, 3)])
  1. in_map - 检查点是否不在国外地图边界；
  2. 开始，目标 - 元组宽度 x 和 y 坐标；
  3. cell_width, cell_height - 具有节点宽度和高度（以像素为单位）的 int 变量（我使用 pygame 进行可视化图）。

我对这种方法没有任何问题，但它不适用于图表，它“单独”工作，它不是我需要的。我英语不好，请见谅：）

标签： python-3.xgraphgrid

解决方案

您发布的代码看起来非常好，您的问题并没有说明需要改进的地方。

您可能更愿意一次将整数 X 或 Y 指针递增一个像素，而不是对向量进行 FP 算术。考虑使用Bresenham 的直线算法start，它枚举和之间的视线中的像素goal。关键的观察是，对于给定的斜率，它会注意到 X 或 Y 是否会更快地增加，并在该索引上循环。

推荐阅读