Start or end point on polygon boundary

[kh90909]

When the start or end point is on the boundary of a polygon, VisGraph.shortest_path() throws an error, as demonstrated in this test case:

import pyvisgraph as vg
polys = [[vg.Point(3.0,2.0), vg.Point(6.0,2.0), vg.Point(6.0,7.0), vg.Point(3.0,7.0)]]
g = vg.VisGraph()
g.build(polys)
s = vg.Point(3.0,5.0)
e = vg.Point(8.0,5.0)
path = g.shortest_path(s, e)
print path

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-64-23f53555023b> in <module>()
      5 s  = vg.Point(3.0,5.0)
      6 e = vg.Point(8.0,5.0)
----> 7 path = g.shortest_path(s, e)
      8 print path

pyvisgraph\vis_graph.py in shortest_path(self, origin, destination)
    128             for v in visible_vertices(destination, self.graph, origin=orgn):
    129                 add_to_visg.add_edge(Edge(destination, v))
--> 130         return shortest_path(self.visgraph, origin, destination, add_to_visg)
    131 
    132     def point_in_polygon(self, point):

pyvisgraph\shortest_path.py in shortest_path(graph, origin, destination, add_to_visgraph)
     68         path.append(destination)
     69         if destination == origin: break
---> 70         destination = P[destination]
     71     path.reverse()
     72     return path

KeyError: Point(8.00, 5.00)

Not sure if this is the intended behavior.

It seems unusual that pyvisgraph will run the shortest path along a polygon boundary, e.g. as in the illustration below, yet not allow the start or end point to be on the boundary.

(source code for this illustration is here)

In this application of a pixelated map with integer coordinates, it's not a trivial issue: the start and end points must be 1-pixel outside the polygon, yet the interior points of the path can be on the polygon boundary.

My clunky workaround is to use Shapely to move the start and/or end points outward along the edge normal by 0.1 units. This avoids the error, and gives the correct result when the path coordinates are rounded back to integers.

[pepaczz]

I confirm running to the same issue. My workaround was to generate Shapely buffer around the point, iterate over the buffer's points and pick the one the most distatnt from the polygon.