Unify line measurement traits (tracking issue)

[michaelkirk]

We have a lot of algorithms (bearing, destination, distance, etc.) implemented across different metric spaces (haversine, euclidean, geodesic), and the current arrangement, arrived at organically, can be pretty confusing.

e.g. It took me a while to realize that we already have haversine corollaries to some euclidean methods. Same problem in #1208.

I think we can rearrange things to be more obvious and discoverable to users

TODO

• Unify line measures #1216 - introduces the pattern, implements Distance, Bearing, Destination, InterpolatePoint on Haversine, Geodesic, Rhumb, and Euclidean (point to point only)
  • deprecate legacy line measure traits  #1222
• Unified Length trait One Length trait to rule them all 💍 #256
• Unified Densify trait unify Densify trait (adds support for Geodesic, Rhumb) #1231
• Move remaining EuclideanDistance traits to new Distance trait (currently only point 2 point) and deprecate EuclideanDistance deprecate EuclideanDistance #1232
• Implement InterpolatePoint::point_at_distance_between (current API only supports point_at_ratio_between: Add InterpolatePoint::point_at_distance_between for line_measures. #1235
• Unified LineInterpolatePoint trait for LineString (name tbd)
• Unified LineLocatePoint trait for LineString (name tbd)
• Unified LineSegmentize trait for LineString
  • combine with? LineString slicing #986
  • combine with? Segementize LineString into arbitrary lengths. #1183
  • combine with? Line Slice #378
• Add euclidean bearing trait?
• VincentyDistance: What to do with it? Tricky because it has fallible output. Distance::Output associated type might do it.
  • If we impl a fallible distance<Vincenty>, can we then impl fallible length<Vincenty>?
• CrossTrackDistance:
  • Add impl Haversine::distance(Line, Point): Add Haversine:distance for Line vs. Point (same as CrossTrackDistance) #1243
  • Breaking: Generically implement point.cross_track_distance<MetricSpace>(line) for at least Euclidean and Haversine (maybe rhumb? I'm not sure there's an analytical solution for Geodesic)
• HausdorffDistance: It's an algorithm, not a MetricSpace. It's currently implemented in terms of Euclidean distance. Would it make sense to implement it as a trait on other MetricSpaces, e.g. HausdorfDistance using Haversine?
• FrechetDistance: It's an algorithm, not a metric space. It's currently implemented in terms of Euclidean distance. Would it make sense to implement it as a trait on other MetricSpaces, e.g. FrechetDistance using Haversine?
• Closest: assumes euclidean
• rewrite top level algorithm docs, organize all the line_measures traits together: Remove deprecated line measurement traits from geo crate root docs index #1238
• Customizable measures (e.g. custom earth radius, flattening) - this might be further down the road.
• Remove deprecated traits in a future release
  • Migrate any good tests to the modern traits now that they're not being tested vicariously.
• Cleanup: move RhumbCalculation into Rhumb struct

Proposal introducing new line measures pattern

Introduce a struct per metric space:

struct Haversine;
struct Geodesic;
struct Euclidean;
...

Introduce a unified trait per algorithm, and implement that trait on each struct:

trait Bearing<T: CoordFloat> {
  fn bearing(p1: Point<T>, p2: Point<T>) -> T
}

impl Bearing for Haversine {
  fn bearing(p1: Point<T>, p2: Point<T>) -> T {
    todo!()
  }
}

impl Bearing for Geodesic {
  fn bearing(p1: Point<T>, p2: Point<T>) -> T {
    todo!()
  }
}

impl Bearing for Euclidean {
  fn bearing(p1: Point<T>, p2: Point<T>) -> T {
    todo!()
  }
}

NOTES

Current Measurement Traits

Here our existing traits that seem at least somewhat related to the notion at hand. I don't intend to unify all of these, but there are some definite patterns that I think we can capture to make things more intuitive to people.

As a csv: measurements.csv

Rendered:

Trait	area_signed	area_unsigned	bearing	closest_point	densify	destination	distance	intermediate	intermediate_fill	length	(➡Oddballs ➡)	interpolate_point	cross_track_distance	bearing_distance	perimeter	perimeter_and_area_signed	perimeter_and_area_unsigned
GeodesicArea	geodesic_area_signed	geodesic_area_unsigned													geodesic_perimeter	geodesic_perimeter_area_signed	geodesic_perimeter_area_unsigned
GeodesicBearing			geodesic_bearing											geodesic_bearing_distance
GeodesicDestination						geodesic_destination
GeodesicDistance							geodesic_distance (point to point only)
GeodesicIntermediate								geodesic_intermediate	geodesic_intermediate_fill
GeodesicLength										geodesic_length
HaversineBearing			haversine_bearing
HaversineClosestPoint				haversine_closest_point
DensifyHaversine					densify_haversine
HaversineDestination						haversine_destination
HaversineDistance							haversine_distance (point to point only)
HaversineIntermediate								haversine_intermediate	haversine_intermediate_fill
HaversineLength										haversine_length
Area (Euclidean)	signed_area	unsigned_area
ClosestPoint (Euclidean)				closest_point
Densify (Euclidean)					densify (euclidean)
EuclideanDistance							euclidean_distance (all geoms)
EuclideanLength										euclidean_length
RhumbBearing			rhumb_bearing
RhumbDestination						rhumb_destination
RhumbDistance							rhumb_distance
RhumbIntermediate								rhumb_intermediate	rhumb_intermediate_fill
RhumbLength										rhumb_length
(⬇Oddballs ⬇)
HausdorffDistance							hausdorff_distance (point to point only)
VincentyDistance							vincenty_distance
VincentyLength										vincenty_length
CrossTrackDistance													cross_track_distance (haversine)
LineInterpolatePoint												line_interpolate_point (euclidean)

/cc @JivanRoquet original author of the HaversineIntermediate trait in #230
/cc @JosiahParry original author of the DensifyHaversine trait in #1081

[michaelkirk]

Oh man, the plot thickens.

Maybe we shouldn't just get rid of HaversineIntermediate, because there are sibling traits: GeodesicIntermediate and RhumbIntermediate.

I don't have a solution yet and have run out of time to think about this today, but I'm open to proposals about how to re-align things to increase uniformity and decrease redundancy.

[JosiahParry]

One option would be to have an IntermediatePoint trait that requires an enum like DistanceType::Rhumb, DistanceType::Haversine, DistanceType::Euclidean, DistanceType::Geodesic. Then, for simplicity have convenience functions in the module.

fn intermediate_haversine(start: &Point, end: &Point, prop: f64) {}
fn intermediate_geodesic(start: &Point, end: &Point, prop: f64) {}
fn intermediate_euclidean(start: &Point, end: &Point, prop: f64) {}
fn intermediate_rhumb(start: &Point, end: &Point, prop: f64) {}

[michaelkirk]

I spent a while trying to understand our existing "measurement" traits - see the new table in the issue description.

It exposes a bit of overlap, some inconsistencies, and some missing functionality. There are also some "similar/related" traits that don't exactly fit the pattern, which I've labeled as "oddballs".

[michaelkirk]

Next up, I want to collapse these into some kind of conceptual "metric space" trait:

(WIP)

I don't know that it will actually be implementable as such, but if nothing else it will be helpful documentation. I am hopeful that it will lead to some clarify about how to more coherently organize our implementations as well.

[michaelkirk]

I've rescoped this issue a bit and fleshed out some of the details. I hope to have the first PR improving (I think!) the situation by the end of today.

[frewsxcv]

Next up, I want to collapse these into some kind of conceptual "metric space" trait:

(WIP)

I don't know that it will actually be implementable as such, but if nothing else it will be helpful documentation. I am hopeful that it will lead to some clarify about how to more coherently organize our implementations as well.

Don't forget EuclideanLength et al. See also #256.

[michaelkirk]

Don't forget EuclideanLength et al.

It's in there! We don't currently have implementations for all the algorithms for Euclidean, but I'd like to add them in a followup.

See also #256.

Ah yes! I forgot about that issue. I just opened #1216 which takes a similar direction, though I haven't included the length trait yet. It's already a huge PR, so I'm trying to omit things when possible, while still keeping the codebase coherent enough to be deployed.

[michaelkirk]

I'm going to re-open this as a tracking issue since there are several other things I'd like to accomplish under this umbrella. I'll update the description soon.