boostorg/geometry — pull request #161 by mkaravel (2014-10-14 08:48:06+00:00)
Title: Re-factoring of bg::distance

In this PR I do a major re-factoring of the `boost::geometry::distance` code. The motivation for doing this re-factoring is due to the following reasons:
* A lot of code can be unified due to the introduction of the segment iterator
* The code is re-designed to first compute the closest features between two geometries and then compute the distance as the distance of the closest feature. A consequence of this is that there is already code that can serve for future implementations of DB GIS functionalities like `ST_ClosestPair` and `ST_ShortestLine`. The other reason is that changes in boost 1.56 broke functionality related to distances in spherical/geographical coordinate system; with this re-factoring this functionality should be available again.

As part of this re-factoring, a few optimizations where made:
* On the code side, the dispatching mechanism is now more compact (because of the use of the segment iterator it is possible to write general algorithms applicable to multiple geometries at the same time)
* On the efficiency side, the R-Tree is now used with segments as objects (for linear and areal geometries), instead of points. For linear geometries this completely avoids the previously existing call to `bg::intersects`. Also there is only one R-Tree now instead of two in the previous version.
* Also on the efficiency side, the point-to-ring algorithm was optimized: previously when calling the relevant static apply method, both (1) the containment of the point in the geometry and (2) the distance of the point to the boundary were computed. In the new version, the containment of the point is computed first, and if needed, its distance to the boundary. So the new version should be faster for points inside the ring.
* The point-to-polygon distance computation is also optimized. In the previous version both the containment of the point in the polygon and the distance to its boundary were always computed (with the latter meaning that the distance of the point to the boundary of all rings of the polygon was computed). In the new version, the point is tested for containment in the exterior ring. If it is not contained inside, the distance of the point to the exterior ring is computed. For points inside, the point is tested for containment in each of the inner rings (holes). If such a hole is found, the distance to this hole's boundary is returned, without further consideration of other holes. If no such hole is found, the point is inside the polygon and 0 distance is returned.