How to fix my algorithm for building visibility graph?

Question

I'm trying to write a code that generates a visibility graph from a set of points and walls (obstacles). My algorithms is not correct and fails on some cases where there is more than one wall intersecting an edge between two points.

Here's kind of a pseudo-python code for my algorithm :

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])

How can I fix my algorithm?

Here's one of the tests where it fails:

Walls :

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

Nodes to be checked:

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

There shouldn't be an edge but my algorithm generates an edge because the edge does not Cross any wall (it intersects but not cross).

For clarification, Cross means that two segments intersect (share a point,) but they don't share any point that is either the start or end of any of the two segments.

I suspect your problem may lie in floating point comparison. You must be dealing with floats in your `Cross` and `Intersect` methods. Note that `a == b` will not be useful if `a` and `b` are floats. — John Anderson, Jan 09 '19 at 02:27
My problem is unrelated to implementation. I'm not trying to debug some code. Rather with my **definitions** my algorithm is wrong and fails on the presented test. I only provided the pseudo-code for convenience, the actual code is in C++ and much different. But like I said code has nothing to do with my question. — FoxyZ, Jan 09 '19 at 11:32

score 1 · Answer 1 · answered Jan 17 '19 at 17:40

When the view ray just grazes a wall like this, you need to keep track of whether the grazing was at the left edge of the wall or at the right edge, as seen from viewpoint 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])

In this algorithm, when segment P,Q has 2 intersection (one from rigth and on from left) but on different point this still yield non-visable but it shouldn't — dWinder, Jan 18 '19 at 06:22

score 0 · Answer 2 · answered Jan 11 '19 at 19:31

The first way that comes to mind for me is to check every pair of three from [node_a, node_b, wall_start, wall_end] and see if the third point lines along the segment between the other two. A quick and accurate way to do this is first create a vector between each of the points, and take two dot products to make sure the "middle" point really does lie in the middle. Additionally is necessary to also check the direction of the vectors to make sure they are parallel, which is equally fast. If both pass, then the third point lies along the segment between the other two.

In 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

In practice, it might be better to check bax*bcy == bay*bcx first, since it is just as fast but probably more likely to fail (and break early) for non-intersecting points.

To then check if any two points intersects a given wall-

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)

Since most of the checks will effectively "short-circuit" after the first or second check in each intersect() call, and each wall_hit() will short-circuit if any of them do hit, I don't think this would be too costly to implement.

If you need to optimize it, you could always compute + reuse the bax, bay = bx-ax, by-ay; ... calculations by either inlining all the function calls and reordering, or by computing them in a separate function and then caching with the lru_cache decorator from functools. Additionally, if you go with the inlining approach, you can likely reorder the conditionals and bax, bay = ... calculations to lazy evaluate them so that you may not need to compute all the intermediate values to assert hit/no_hit.

How to fix my algorithm for building visibility graph?

2 Answers2