pathfinding
The Double Order Scaled Approximation (DOSA), rev. 1
This is a companion paper proving scaled integer edge weights can be used as in Thorup’s algorithm
for SSSP to retrieve shortest paths in two-dimensional obstacle maps in grid-space. The proof extends to
n-dimensional spaces over the integers. Before getting started, we need to cover some ground covered in my
paper (pending publication; see below) regarding digital curvature and pathfinding.
Topological all shortest paths automatique’ (TASPA) v0.4
As promised, here’s the initial release of the polygon fitting source code! Most have had no trouble installing it under various distributions of Linux. The install script does run into problems in various BSD installations and is untested under MacOS and Windows. That said, leave a comment if you run into problems so I can make the next package a little better 
TASPA is a designed to demonstrate a transitional vertex thinning algorithm based on convex polygon fitting. It makes a copy of the input bitmap file, showing the fitted polygons, the vertices used in path finding after thinning, and (optionally) a sample shortest path between two random points. For now, TASPA is limited to monochromatic pixel weights (either a pixel is ‘passable’ or ‘impassible’ and ‘passable’ pixels have a weight of 1) and undirected graphs (A to B is equivalent to B to A). It is possible this will be extended to support multi-chromatic (semi-passable) pixel weights and even weight heuristics, such as ’safest route’ vs. ’shortest route’ balancing. Please inform me if you have any particular features you would like to see in future releases.
NOTE: I would appreciate any feedback concerning bugs, along with a copy of the input and output bitmaps from which you found them.