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

我试图编写一个代码，从一组点和墙（障碍物）生成可见性图。我的算法不正确，在某些情况下，如果两个点之间有多个墙相交于一条边，则会失败。
下面是我的算法的一种伪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表示两个线段相交（共享一个点），但它们不共享任何点，即这两个线段的起点或终点。

最佳答案

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

关于python - 如何修复构建可见度图的算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54101717/