Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LineString intersection API #985

Open
dabreegster opened this issue Feb 16, 2023 · 2 comments
Open

LineString intersection API #985

dabreegster opened this issue Feb 16, 2023 · 2 comments

Comments

@dabreegster
Copy link
Contributor

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
Copy link
Member

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
Copy link
Contributor Author

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? :\

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants