Archive for February, 2009
Polygonal Segmentation: Update
Its not perfect but its another milestone; my polygonal segmentation code now does a thorough enough job for one of its original intended purposes: reduction of vertices needed in path finding algorithms. Using only those vertices on a topological map which are shared between two or more convex polygons, we can generate an adjacency matrix of a relatively small size in a very short span of time (compared to using either all vertices or all passable points). This is because all-paths path finding algorithms are inherently O(v^2) algorithms so one of the best optimizations we can come up with is to mathematically reduce the set of all vertices used to the minimal set of necessary vertices in order to find our way from any point to any other point.
In choosing to include only those vertices shared by two or more polygons, we exclude all vertices that would only be visible (and therefore useful) from within a specific polygon. In other words, we only use the vertices that run between separate ‘regions’ in the map and don’t bother with those which are only useful within a specific ‘region’. Here I’m saying ‘region’ when I mean an area of a map in which any path from point X to point Y, in that same region, is a trivial matter of line of sight — in our original words: a convex polygon.
Below is the most recent output from the program, in full scale so the meticulous reader may pick up on some of the optimizations that still need to be more finely tuned.
Once the adjacency matrix is full, there should be no points in the map that are not visible from at least one of the vertices in the matrix, unless the point is within an entirely solitary convex polygon (I haven’t bothered to prove this yet, as it seems fairly obvious: one cannot be in a properly segmented map without being inside a convex polygon; one cannot be in a convex polygon and not have a line of sight to all of its vertices; there exists no convex polygon without shared vertices such that the points inside the polygon are accessible by any path from any other point in the map… something like that). This means we now have full access to the achievable shortest (or approximately so) paths from any point to any other point on our map — and we’ve done it in (again, approximately) a mathematically efficient way, both in terms of CPU time and post-processing memory allocation.