New algorithm closest points

[vissarion]

I am working on a new algorithm (closest_points) that given any two geometries A, B computes the two closest points, a, b such that a belongs to A and b belongs to B. In other words the distance from a to b equals the distance from A to B. Here is the working branch https://github.com/vissarion/geometry/tree/feature/shortest_points_new

There are cases of pairs of geometries where a and b are not unique. E.g. two spherical or geographic boxes with overlapping longitude bands, two cartesian geometries with parallel segments, a linestring and a point where more than one segment obtain the minimum distance to a point, etc.

Hence, in general the closest set is a set of point pairs and/or segment pairs. This could be modelled as a pair of multipoint and a multilinestring. That is, this pair will be the output of the closest_points algorithm. That said maybe the name closest_points is a bit misleading.

Another question here is what happens when the distance is 0. One simple solution could be to also return the distance and in the case of distance 0 the closest set has no meaning.

What do you think? Any ideas/objections?

[awulkiew]

I would not worry about the uniqueness. I think we should return the first found closest pair without any additional guarantees. This will allow us to implement the algorithm of the smallest complexity which works the same as distance and comparable_distance so we'll be able to reuse the code for all algorithms.

Regarding returning the distance together with closest points I think I'd prefer not doing that. Internally the algorithm should probably be based on comparable distances. And the intention of the user may be to calculate comparable distance (not real distance). So this would add unnecessary overhead.

I also wouldn't worry about a user calling either distance or comparable_distance later for the points returned from closest_points because it has the most sense to call this algorithm for complex geometries which requires to call comparable_distance multiple times internally. One more call doesn't add much. This of course depends on the size of geometries.

Regarding the distance 0. I propose to also return a pair of points. It is possible to do this without additional computation but it would require to add an algorithm/utility internally replacing intersects/disjoint. Basically intersects returning a point related to the intersection somehow. In intersects internally get_turns is called which finds an intersection point and then if it is not found within/point_in_geometry is called for both geometries in order to check if one geometry is within the other. The information about the closest points being either first found intersection point or one of the points used to test for within is there.

So I suggest to simply return any pair of closest points that was found ASAP.

[adityamohan29]

Hi, Has a PR been submitted for this issue yet or does @vissarion want someone else to work on this? Else we can try a divide-and-conquer approach for the same (which proves to be quite efficient, as I have implemented it before). https://en.wikipedia.org/wiki/Dynamic_convex_hull

[sudo-panda]

@spacewafer vissarion has been working on this for quite a while as you can see it in his fork

[adityamohan29]

@sudo-panda Oh alright then, Thanks!

[vissarion]

Implemented in https://github.com/boostorg/geometry/pull/939 https://github.com/boostorg/geometry/pull/923