polygon_crossing misses a few cases about pyvisgraph HOT 11 CLOSED

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

from pyvisgraph.

@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?

from pyvisgraph.

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.

from pyvisgraph.

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

from pyvisgraph.

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.

from pyvisgraph.

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

from pyvisgraph.

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

from pyvisgraph.

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.

from pyvisgraph.

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

from pyvisgraph.

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.

from pyvisgraph.

@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.

from pyvisgraph.