Closest Point

[Michael-F-Bryan]

Would it be possible to add a closest Points algorithm? I'm guessing that it's be a trait which returns either a single point (intersection), a pair of points (closest Points on object A and B), or some sort of "infinite points" marker for when two lines are exactly parallel.

[urschrei]

Do you mean between all combinations of geometries? It's certainly possible, but it would be a lot of work; some of the current distance algorithms check for intersection first and stop if one is found, without calculating the point at which it occurs, or are implemented using algorithms that don't retain the nearest point. Also, the Polygon-Polygon, Polygon-LineString and LineString-LineString distance PR (#115) is still open (although it's close to done).
Have you got a specific use case in mind for which we could do something less extensive?

[mbattifarano]

If we had buffer, union, and intersection (all planned as far as I know), I think this would be straightforward:
union(intersection(buffer(A, mindist(A, B), B), intersection(buffer(B, mindist(A, B)), A))
the union of the set of all points in B that are within mindist of A and the set of all points in A that are within mindist of B.

[urschrei]

Good point, but I don’t think anyone’s made progress on #80, and buffer ops on polygons require a half-edge data structure and straight-skeleton algorithm, so quite a lot of work.

[Michael-F-Bryan]

I should preface this by saying I'm actually using this as a general-purpose geometry library instead of anything geography related...

My use case is I want to let a user click on an object (Line, Polygon, or LineString) and then split that object into two halves where it was clicked. In a prototype I figured out whether the split point lies exactly on a line, returning an error if it doesn't. However because moving a mouse is hard and floating points are annoying it'd be nice to let the user click and then I can say "if the click point is less than x mm away from the closest point to this line, pretend the user clicked on that closest point".

How I'd implement this is by first implementing it for the line-point combination, then for closest point between a Point and LineString or Polygon can be figured out by iterating over the line segments and checking individually.

In this case I'm mainly interested in the closest distance between a point and something else, but it'd be nice to do something like line-line or polygon-polygon. That's not critical though.

[Michael-F-Bryan]

I've implemented a version of this for trying to find the closest place on pretty much any object to a Point. It's fairly brute-force at the moment and essentially iterates over the elements in an object, trying to find the "best" position. It'd be nice to get some feedback to hear what other people think of it.