polygon_crossing misses a few cases

[eshira]

I narrowed down a mistake in evaluating visible vertices to a failure to detect a point inside a polygon. In the function polygon_crossing there is a section intended to evaluate edges where one or both edge points sit on the ray from the point to +INF in the X direction. It fails in some cases.

In the picture below, the red line indicates two points mistakenly identified as visible to each other. In the process, a point inside the T-shaped polygon along the red line shown is mistakenly identified as outside the polygon.

I never found the bug exactly, but I came up with some slightly reworked logic that seems functional so far. The reworked logic is as follows:

• When both edge points lie on the ray, do nothing
• When just one edge point is on the ray, pick the other edge point and figure out if it lies above or below the ray (in Y dimension). Count total above-ray cases and below-ray cases in two separate counters.
  -After every edge was evaluated, see if both counters are odd (I think it is actually sufficient to see if either is odd, based on assumptions on the polygon being properly formed). If so, this counts as a crossing overall, so increment the crossing counter by 1.

[TaipanRex]

Excellent work, thanks for the input. I'll look into fixing this.

[TaipanRex]

@eshira I tried replicating this bug, but cant seem to get it. I did the below test case, drawing a T-shaped polygon, but the test passes:

def test_collin5(self):
        graph = Graph([[Point(7,2), Point(9,2), Point(9,10), Point(14,10),
                        Point(14,12), Point(5,12), Point(5,10), Point(7,10)]])
        assert point_in_polygon(Point(8,10), graph) == 0
        assert Point(5,10) not in visible_vertices(Point(9,10), graph)

You wouldnt happen to have the coordinates you used in your posted graph still?

[eshira]

I don't have the code, but I reconstructed a similar case. The problem doesn't occur when visibility graph Point objects are made explicitly, as in Point(7,2) above. I create my points by specifying center points of square obstacles, and then doing some math to create the 4 corners of the square.

I uploaded it as a txt.
test1.txt

Okay actually I'm realizing that this is the bug demonstrating the rounding issue, not the issue this thread is about. But I do suspect if you are trying to construct a case to fail, try generating the points of the T using some math instead of explicitly creating them.

[eshira]

Here is the result of that test1 file, run on the original pyvisgraph, and then using a modified version of pyvisgraph (uses the fixes I suggested in the Issues I opened).

[TaipanRex]

I narrowed the problem down to Point(0.86, 0.86) being visible to target t. visible_vertices evaluates Point(0.86, 0.86) as visible to t because it thinks that the points on the segment t, Point(1.14, 1.14) and Point(0.86, 0.86) are not collinear. If you look at the ccw function and plugged in ccw(t, Point(1.14, 1.14), Point(0.86, 0.86)), it evaluates to -1 (where it should be 0 - note I am here not using the manually entered polygon). If you look at the actual area number calculated in ccw, it results to -5.55111512313e-17, i.e. very close to zero. This bug is therefore a floating point precision problem and I have solved it as follows:

Add a constant to visible_vertices.py:

COLIN_TOLERANCE = 15

I chose a tolerance of 15; I tried 10 but had some cases where that was not enough.

in ccw() change the first line of code to:

area = round((B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x), COLIN_TOLERANCE)

I modified the test case as follows, which now passes:

from math import pi, cos, sin
    def test_collin5(self):
        r = 0.2  # Radius of polygon
        n = 4  # Sides of polygon
        c = Point(1.0, 1.0)  # Center of polygon
        verts = []
        for i in range(n):
            verts.append(Point(r * cos(2*pi * i/n - pi/4) + c.x,
                               r * sin(2*pi * i/n - pi/4) + c.y))
        g = vg.VisGraph()
        g.build([verts])
        s = Point(0, 0)
        t = Point(1.7, 1.7)
        shortest = g.shortest_path(s, t)
        visible = visible_vertices(t, g.graph, s, None)
        assert verts[3] not in visible
        assert verts[1] not in shortest
        assert verts[3] not in shortest

If you have a chance to test it on your usecase that would be great, then i'll push the fix.

[TaipanRex]

I just realized you found this bug in issue #19 :). Did you ever try your (same) fix as the fix for the above issue?

[TaipanRex]

I also just realized you edited your comment, sooo I will try and replicate the t-polygon then.

[eshira]

Yeah, sorry I lost that original code for the T polygon! I was in a rush and wasn't sticking with best practices or version control. If you're interested I am happy to share the whole code, which will probably be able to replicate the issue if the obstacles are re-arranged into a T, but it needs to be picked apart a bit (some of the additions I made to the pyvisgraph code involve support for polygons with interior holes; I need to roll back the rest of the changes but keep that for it to work).

Admittedly I never took the time to completely understand the existing polygon_crossing code; I just worked out cases on paper to see if I could find logic that would work for when the point being checked was on the line of the polygon, and replaced the old logic with that. If memory serves that did solve one problem immediately, so there might be something to reviewing that logic.

[deboc]

Hi,
I find another failure case and I guess I fixed it in pull request #28

[TaipanRex]

Ok so I have figured out what the bug is with @eshira T-polygon example. When we run visible_vertices, it will also add edges that are visible internally to a polygon, then the algorithm checks all of these visible edges and removes the ones that are internal to the polygon (except the edges that outline the polygon). We use edge_in_polygon for that, which uses polygon_crossing to check if the middle point of each visible edge is inside the polygon. Colinearity is a problem it deals with, but only deals with three of six cases:

In case no. 1, we count 1 intersection for the two edges that have point x in them. In cases no. 2 and 3, we do not count any intersection for the two edges. Similarly, for case no. 4, we count 1 intersection and ignore cases 5 and 6.

The second set of colinearity issues is not dealt with. Thats why @eshira T-polygon is having problems. It seems more complicated than the first set, because now you have 3 edges that trigger colinearity.

[TaipanRex]

@deboc I thought more about it and I think your e1cd1dd is actually an extremely elegant fix. What you are saying is, lets just ignore the edge x to y in cases 4-6, then cases 4-6 are actually just the same as cases 1-3! I'll write the 6 cases as tests and see if it holds, which I am pretty sure it does.