GSoC2017 Boost.Geometry:Filtering of compare distance predicates Proposal

In some algorithms there is the need to compare two distances of two point pairs. Especially, computing distances on ellipsoid in Boost.Geometry used compare_distance() function, which need to calculate the actual distance of two geodesic segments on the ellipsoid. Boost.Geometry used Vincenty formula, the time complexity of this algorithm is hard to estimate and expensive.

To reduce the time complexity, this project tried to use the following approaches:

• Condition Division:Compute the Euclidean distances first, if the length of two segments are very close, defined not “far enough” means “very close”. then fall back to expensive geographic distance calculation otherwise return the result by comparing those numbers obtained by less expensive cartesian computation.
• Calculation with Sectorial Area:Get cross-section through the center of ellipsoid and the geodesic segments, then calculate the sectorial area, which is easy to compare distances.
• Calculation with Performing a local spheroid approximation and return the 2D distance by map projection:Perform a local spheroid approximation, then use methods of map projection to calculate the distances.