boostorg/geometry — pull request #182 by mkaravel (2014-11-19 22:33:51+00:00)
Title: Feature/new cross track strategy

In this PR the `cross_track<>` distance strategy is implemented in a different way:
* It has a comparable counterpart, which among other things enables the comparisons with distances computed with `comparable::haversine<>`.
* It is more efficient with respect to the current `cross_track<>` strategy implementation.

I have performed the following benchmark: I have considered the segment `SEGMENT(0.05 0, 179.95 0)` which is almost half the equator (units in degrees). Then I took `N` random points on the sphere, where `N` took the values 10^2, 10^3, 10^4, 10^5, 10^6 and 10^7. Using these point sets I computed:

1. The distance of each point to the segment.
2. The distance of the points seen as a multipoint to the segment, using `bg::distance`. Notice than in this case the distance algorithm computes the closest point/segment pair using comparable distances, and then returns this distance as is if the strategy passed is a comparable one, or computes the true distance for the closest point/segment pair if a non-comparable strategy is passed.

In each case I used the old cross track strategy, the new one, and the new comparable one (the last one to measure the time difference when computing comparable distances). For each case I measured the relative gain as a percentage:
```
gain = 100 * (TIME(old_strategy) - TIME(new_strategy)) / TIME(old_strategy)
```
* For the old/new non-comparable strategies and for Case (1) the gain was between 22 and 30%.
* For the old/new comparable strategies and for Case (1) the gain was between 21 and 44%.
* For the old/new non-comparable strategies and for Case (2) the gain was between 29 and 32%.
* For the old/new comparable strategies and for Case (2) the gain was between 28 and 52%.

The reason for choosing this particular segment is that a random point on the sphere has about the same probability (equal approximately to 1/2) to be closer to one of the endpoints of the segment or the segment's interior, thus covering equally both major cases in the `cross_track<>` strategy computation algorithm.

Finally, the unit test for the computation of distances between pointlike and linear geometries has been updated to account for the new strategy proposed.