LineLocatePoint in the Euclidean space spends a lot of time calculating hypot

[AndrewLipscomb]

LineLocatePoint appears to spend a lot of time calculating a hypotenuse. I believe some of these calculations are unnecessary.

At the very least

geo/geo/src/algorithm/line_locate_point.rs

Line 101 in 70b1c1f

let segment_distance_to_point = segment.euclidean_distance(p);

appears to only be used for "shortest seen so far", that could be the cheaper non-sqrt'ed distance.

I believe the other values will all need to be sqrt'ed - but given there is one potential improvement in there, maybe worth a double check from the more knowledgable guys here.

[michaelkirk]

That seems plausible. Is this something you're interested in working on?

[AndrewLipscomb]

I am interested, I just wanted a sanity check before I spent time looking at it.

Does geo itself have a trait comparable to the Boost C++ boost::geometry::comparable_distance method? I've noticed that does exist but effectively is an export of the same trait from rtree (https://docs.rs/rstar/latest/rstar/trait.PointDistance.html). FWIW - I have no idea what a "comparable distance" would be for the other MetricSpace's - I don't work often in non-Euclidean (even non-UTM) projections

Is that trait bankable enough to rely on? Or is there a geo-exclusive way to get that?

[michaelkirk]

I don't think we yet have something like comparable_distance.

I agree it looks plausible, but I wouldn't recommend rstar::PointDistance as the basis for this feature. The existing implementations should be correct, but it's not implemented for all geometry types.

We've considered implementing it for all geometries, but are kind of at an impasse: #984 has some further discussion

I'd recommend something more targeted, even if it's slightly redundant with some existing trait definitions.

I have no idea what a "comparable distance" would be for the other MetricSpace's

I don't know that you have to address this - LineLocatePoint is (currently anyway) strictly Euclidean. If you can speed up the Euclidean calculation (and only the euclidean calculation) that's still valuable.

[AndrewLipscomb]

Gonna have a crack at this today. For what its worth, my last couple of weeks have had me reaching for a trait doing something like the Boost comparable_distance functions - so it seems like any work I do here could hit two things.

I'll roll both into a PR and get some feedback