python - 如何修复构建可见性图的算法？

Question

我正在尝试编写一个代码，从一组点和墙壁(障碍物)生成可见性图。我的算法不正确，并且在某些情况下会失败，因为两点之间有不止一堵墙与边相交。

这是我的算法的一种伪 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 表示两个线段相交(共享一个点)，但它们不共享任何两个线段的起点或终点。

Answer 1

当观察光线像这样擦过墙时，您需要跟踪擦过是在墙的左边缘还是右边缘，如从视点 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])