LineString intersection API

[dabreegster]

I would love to have an API to find the points where two LineStrings intersect. The naive implementation would be something like

use geo::algorithm::line_intersection::{line_intersection, LineIntersection};

/// Return all intersections between two line-strings, ordered from the beginning of ls1
fn intersection(ls1: &geo::LineString<f64>, ls2: geo::LineString<f64>) -> Vec<LineIntersection> {
  let mut results = Vec::new();
  for line1 in ls1.lines() {
    for line2 in ls2.lines() {
      results.extend(line_intersection(line1, line2));
   }
  }
  results
}

Does this belong in geo? Any opinions on what the API should look like, or how it should be implemented?

• is_proper for points in the middle of a linestring should probably always be false, even if the shared point was an endpoint within a line segment
• Note today we have Intersects, but this doesn't identify where the hits are
• Should this only be defined between two line-strings, or is dealing with MultiLineString and such important?

More info in LineIntersection

And relatedly, I want to propose extending the LineIntersection result. I don't just want the point back; I want to know the distance along the first line (or linestring, in the new proposed API) where the point was found. In my particular use case, this is necessary to then slice/trim the line-string to begin or end at that point.

LineLocatePoint could be used as followup, but it would unnecessarily repeat work, and it may be subject to slight floating-point drift sometimes. It returns a fraction [0, 1] where the point is found. Maybe we could add that fraction to LineIntersection output too?

Context

@BudgieInWA and I are using an implementation in https://github.com/a-b-street/abstreet/blob/main/geom/src/polyline.rs to do this kind of thing right now. We want to move towards just using geo for geometry, and this is one of the meatier pieces of logic missing today.

[michaelkirk]

It's not exactly as you described, but do you think something like https://postgis.net/docs/ST_Split.html would serve your purposes?

(it doesn't yet exist in georust)

[dabreegster]

It's not exactly as you described, but do you think something like https://postgis.net/docs/ST_Split.html would serve your purposes?

(Months later, sorry...) Yes actually, splitting two line-strings and getting back up to 4 results is logically the thing I'm trying to do. I'll have a closer look through these APIs. It's definitely not easy to implement in georust, right? :\