代码之家 › 专栏 › 技术社区 › FoxyZ

如何修正我的可见性图生成算法?

path-finding geometry algorithm python

FoxyZ · 技术社区 · 6 年前

我试图编写一个代码,从一组点和墙(障碍物)生成可见性图。我的算法不正确,在某些情况下,如果两个点之间有多个墙相交于一条边,则会失败。

下面是我的算法的一种伪python代码:

Intersect(wall, P, Q):
    returns True if wall segment intersects with PQ segment

Cross(wall, P, Q):
    returns True if wall segment crosses PQ segment

for i in range(len(nodes)):
    for j in range(i + 1, len(nodes)):
        flag = True
        for wall in walls:
            if (Cross(wall, nodes[i].pos, nodes[j].pos)):
                flag = False
        if (flag):
            nodes[i].adj.append(nodes[j])
            nodes[j].adj.append(nodes[i])

以下是其中一个失败的测试:

墙壁:

w1 -> (1, 0),(2, 1)
w2 -> (2, 1),(3, 2)

要检查的节点:

node1 -> (0, 2)
node2 -> (4, 0)

为了澄清, Cross 意味着两个线段相交(共享一个点),但它们不共享任何一个线段的起点或终点。

2 回复 | 直到 6 年前

Christopher Bruns 6 年前

当视图光线只是这样擦墙时,您需要跟踪擦墙是在墙的左边缘还是在右边缘,如从视点P所示。

def LeftIntersect(wall, P, Q):
    if Cross(wall, P, Q):
        return False
    if not Intersect(wall, P, Q):
        return False
    if magnitude(cross_product(PQ, wall_midpoint)) <= 0:
        return False
    return True

def RightIntersect(wall, P, Q):
    if Cross(wall, P, Q):
        return False
    if not Intersect(wall, P, Q):
        return False
    if magnitude(cross_product(PQ, wall_midpoint)) >= 0:
        return False 
    return True

for i in range(len(nodes)):
    for j in range(i + 1, len(nodes)):
        crossCount = 0
        leftIntersectCount = 0
        rightIntersectCount = 0
        for wall in walls:
            if (Cross(wall, nodes[i].pos, nodes[j].pos)):
                crossCount += 1
            if (LeftIntersect(wall, nodes[i].pos, nodes[j].pos)):
                leftIntersectCount += 1
            if (RightIntersect(wall, nodes[i].pos, nodes[j].pos)):
                rightIntersectCount += 1
        visible = True
        if (crossCount > 0)
            visible = False
        if (leftIntersect > 0 && rightIntersect > 0)
            visible = False        
        if (visible):
            nodes[i].adj.append(nodes[j])
            nodes[j].adj.append(nodes[i])

Dillon Davis 6 年前

[node_a, node_b, wall_start, wall_end] 看看第三个点是否沿着另两个点之间的线段。一种快速而准确的方法是首先在每个点之间建立一个向量,并用两个点积来确定中间点确实位于中间。此外,还需要检查向量的方向,以确保它们是平行的,这是同样快的。如果两者都通过,则第三个点位于另两个点之间的线段上。

在python中

def intersect(a, b, c):
    (ax, ay), (bx, by), (cx, cy) = a, b, c
    bax, bay = bx-ax, by-ay
    bcx, bcy = bx-cx, by-cy
    acx, acy = ax-cx, ay-cy
    if bax*bcx + bay*bcy < 0: return False
    if bax*acx + bay*acy > 0: return False
    return bax*bcy == bay*bcx

实际上,最好检查一下 bax*bcy == bay*bcx

然后检查任意两点是否与给定墙相交-

def wall_hit(node1, node2, wall_start, wall_end):
    return intersect(node1, node2, wall_start) or \
    intersect(node1, node2, wall_end) or \
    intersect(wall_start, wall_end, node1) or \
    intersect(wall_start, wall_end, node2)

因为大多数检查都会在第一次或第二次检查后有效地“短路” intersect() wall_hit() 会不会短路,如果其中任何一个真的击中,我不认为这将是太昂贵的实施。

如果您需要优化它,您可以始终计算并重用 bax, bay = bx-ax, by-ay; ... lru_cache 装饰工 functools . 另外,如果使用内联方法,则可能会重新排序条件语句和 bax, bay = ... 计算来延迟计算它们,以便您可能不需要计算所有中间值来断言命中/不命中。