LineString slicing

[dabreegster]

If I have a non-closed LineString, I often want to slice / split it and get something smaller back. The input could be...

• a [start, end] distance, measured from the start of the linestring
• a [start_percent, end_percent] fraction of the total length (what LineLocatePoint outputs and LineInterpolatePoint inputs)
• if I found a point on a linestring by line intersections, I might have a [start point, end point] that I'm somehow insisting must both be present on the line-string. (See LineString intersection API #985 for an idea to avoid needing this)

There are some edge cases:

• if the input range exceeds the linestring (start a little bit negative, due to floating point error maybe, or length a little past the linestring's length)
• if the output collapses to a single point (maybe because start == end, or because we request [0, epsilon] or [length - epsilon, length]

I'd like to add an implementation of this to georust. Any opinions on the API or impementation, or other edge cases I've not thought about?

CC @BudgieInWA. Today we make heavy use of this type of operation in osm2streets using something not based on georust.

[michaelkirk]

This seems useful, and indeed the LineInterpolatePoint/LineLocatePoint seems like good inspiration, since they're in the same spirit.

As you say, they both take input parameters as a "ratio" of the total line length, but I can easily imagine how "length" is an equally valid input format (In fact their implementations are primarily in terms of length). I can imagine having both.

if I found a point on a linestring by line intersections, I might have a [start point, end point] that I'm somehow insisting must both be present on the line-string. (See #985 for an idea to avoid needing this)

Keep in mind that despite your insistence (😉), the computed intersection point paradoxically might not intersect the line due to floating point representation errors.

Assuming we also get an API like you mentioned above ("a [start_percent, end_percent] fraction of the total length"), an API that I think is reasonable and should sidestep that kind of error:

/// This is probably a bad name, since Slice already means something important in rust. 
/// All of these names are just spitballing, don't take them as a request.
impl Slice for LineString {
    /// subslice of the linestring until it is length T
    fn slice_to_length(&self, length: T) { todo!("assume this is done") }

    /// subslice of the linestring until it is (ratio*100)% of it's original length
    fn slice_to_ratio(&self, ratio: T) { todo!("and/or assume this is done too") }

    /// If `coord` is on the linestring, subslice the linestring from begining until it reaches that `coord`.
    /// If `coord` is not on the linestring, the closest point on the linestring will be used.
    /// (secretly these are one-and-the same case, but maybe it's easier to explain it this way)
    fn slice_to_point(&self, coord: Coord) {
        let ratio = LineLocatePoint.line_locate_point(self, coord);
        self.slice_to_ratio(ratio)
    }
}

WDYT?

[frewsxcv]

See also: #378

[thehappycheese]

Hi @dabreegster, I am also very keen on this feature. I have been chipping away at an implementation in #1050. May I please have your feedback when / if you have time 😊

I opted for a very similar API to what you suggested above. I'd be happy to make changes to names etc. But I need a sanity check on the API / result types I have chosen.

[dabreegster]

Deeply sorry for multi month delay here...

impl Slice for LineString

This API looks good to me, and I like how slice_to_point avoids the floating point problems. Is there a reason to only handle slicing from the start to some specified end? The user can reverse a linestring and the resulting slice if they need the other direction. Should there also be a variant taking a [start, end] range, or does that just multiply the number of possibilities?

(Or maybe I misunderstood the output -- one or two LineStrings? If it's two, maybe something like line.split_at_{point,length,ratio} would make more sense?)

Alternatively, the input could be something like

enum SliceEndpoint {
  Length(T),
  Ratio(T),
  Point(Coord),
  Parameter { segment_index: usize, ratio: T },  // from #1050 
}

fn slice(&self, start: SliceEndpoint, end: SliceEndpoint)

@thehappycheese, I like the API you've laid out -- you've thought about things more generally than I was. Instead of modifying the input in-place to have start/end points, you're splitting at specified points and returning multiple outputs. For line_split_many, looks like you're just returning Vec<Option<T>>, and it's up to the user to find the piece they want based on the input. LineSplitResult and LineSplitTwiceResult confuse me a bit -- feels like a combinatorial explosion of outputs to represent, and some effort to retrieve the first/second/third entry. Any reason to prefer that over the Vec? (And let me know if you prefer the comments moved to the PR)

[thehappycheese]

hi @dabreegster :)

slice_to_point

I can add that in to my current PR easily enough :) Thinking about it though... there could be a special implementation of slice_to_point which further avoids precision issues in the 'ratio' parameter. It could project the new coord onto the nearest bit of the line and then generate two new lines either side of the projected point....

The user can reverse a linestring and the resulting slice if they need the other direction. Should there also be a variant taking a [start, end] range, or does that just multiply the number of possibilities?

I like the idea of being able simultaneously reverse the line portion using a slice. But the simplest implementation just scans the line string once from start to end. I am imagining you would need to check for reversed input and remember the order, do the slice, then as the final step reverse the Vec just before returning. If the linestring just had a separate .reverse() function then users who don't need the slice-and-reverse behavior wouldn't pay for extra checks, and users that do need it would have to do the check externally and manually call .reverse()...

enum SliceEndpoint

Ooo I had not thought of having an enum as the input... that is nice and explicit, and for documentation it is nice because I'd only have to write docs for one function and each variant of SliceEndpoint. It would be harder to document all the similar functions named like line.split_at_{point,length,ratio}.

ratio

What do you think about fraction rather than ratio though? Possibly just my australian english but I think of ratios like 'two-to-one' or 2:1 and fractions as in 'the fractional part of 10.32 is 0.32'. Hence I chose 'fraction' as the parameter name. I don't really mind though, both very similar either would be fine.

LineSplitResult and LineSplitTwiceResult confuse me a bit -- feels like a combinatorial explosion of outputs to represent,

I think you are right about LineSplitTwiceResult... But I am sitting on the fence about LineSplitResult I explain my thinking a bit more back at the PR

[dabreegster]

I like the idea of being able simultaneously reverse the line portion using a slice. But the simplest implementation just scans the line string once from start to end.

I was responding to Michael's earlier suggested API. I think that API is hard to use for this reason -- to split on different ends, a user might have to reverse a bunch. No need to do any of that if a split returns linestrings on either end.

there could be a special implementation of slice_to_point which further avoids precision issues in the 'ratio' parameter. It could project the new coord onto the nearest bit of the line and then generate two new lines either side of the projected point....

Yeah, it feels like there could be some sort of optimization here. Ultimately what I'm doing is intersecting two line strings, and getting half from each of the two inputs. The intersection is already finding some fraction along each of the inputs; it could be wasteful to have to project the intersection point onto both linestrings again just to figure out that fraction.

What do you think about fraction rather than ratio though?

fraction sounds fine to me for the reasons you said. I might tend towards "percent", but then it's never obvious if that's [0, 1] or [0, 100.0].