Description
This is an ongoing project that hopes to solve the following problem: given a geometrical description of polygonal obstacles in a region, what is the shortest path between any two points near the region? The approach taken here is to compute the full visibility graph for the polygonal arrangement and then apply an A* shortest-path search on the graph to determine the shortest path.
Download
Preliminary visibility code. This can compute total visibility graphs among a set of polygon/polyline obstacles. An example program that uses the API is included. Currently, a possible bug is the inability to handle colinear points (the original paper claimed the points must be in general position). However, I have not run into problems with this yet. It certainly helps that I compare only indexes to points rather than compare points directly against each other.