Search code examples
computational-geometryconvex-hullvoronoidelaunay

How to use computational geometry techniques to deal with inaccurate map coordinates

I am trying to build route optimization software and I am using openstreetmaps for the interface. I have an implementation of the savings algorithm on the backend that helps determine the optimal route for making a series of deliveries.

The problem I am having is that some of the coordinates being returned for places clicked on the map are wrong. Suppose I have to make a delivery at 2 different places. The coordinates of those 2 places plus where I start from and return to when I am done should form a triangle. Some times the coordinates returned can be so wrong that the triangle inequality theorem is violated.

I have been reading Skiena's Algorithm design manual and was wondering, given a wrong pair of coordinates can any of the techniques discussed (convex hulls, Voronoi diagrams, Delaunay triangulation etc) be used to determine what is the most likely correct coordinates such that the triangle inequality theorem is not violated?

Thank you

Solution

  • In general, (as far as I know) there are 4 approaches to deal with the issue:

    1. Controlled perturbation
    2. Snap rounding
    3. Exact Geometric Computation
    4. (EGC) Ad hoc

    The first 2 have been partially attempted, but they are far from being practical as an automatic way to address the issue. For example, there were several publications about the snap-rounding approach in 2D, but non in 3D. It may be easy to apply snap rounding, but you must be able to comprehend the resulting topology, and above all, the software must become robust.

    Accepting approximately equal floating points values falls under the Ad-hoc category. The resulting software is almost always not completely robust---an input case that breaks robustness is out there waiting to be fed. Moreover, slight changes to the code may break it further and require adjusting those tolerance conditions constantly.

    CGAL follows the EGC paradigm. Like any software, CGAL is not bugs free, but the robustness issue is eliminated. You can read more about it in the CGAL website or, e.g., in the book "CGAL Arrangements and Their Applications". While the book is dedicated to specific packages of CGAL, it does touch on the EGC subject; see Section 1.3.2.