Closed thehappycheese closed 3 months ago
Hi @urschrei, @michaelkirk, it seems like every time I push changes to my fork it is triggering all the checks on this draft PR. Should I be concerned about the usage?
Hi @urschrei, @michaelkirk, it seems like every time I push changes to my fork it is triggering all the checks on this draft PR. Should I be concerned about the usage?
CI is configured to run tests on all PR's (even drafts). Maybe it's possible to turn CI off for draft PR's, but I prefer it as it is. In fact I actually sometimes use draft PR's exactly for this purpose: as a way to see if CI passes before I'm ready to mark it as ready and waste a living human's time on it.
I'm not overly concerned about the usage. If you don't want it to run, you could close the PR until you're ready.
CI is configured to run tests on all PR's (even drafts). Maybe it's possible to turn CI off for draft PR's, but I prefer it as it is. In fact I actually sometimes use draft PR's exactly for this purpose: as a way to see if CI passes before I'm ready to mark it as ready and waste a living human's time on it.
I'm not overly concerned about the usage. If you don't want it to run, you could close the PR until you're ready.
Thanks @michaelkirk I'll try to limit unnecessary pushes for now anyway. I had understood an early draft PR as a way of letting others know I'm having a go at some feature. Perhaps I will open them a bit later in the process in future.
I thought this PR would be a two or three quick commits but it's turning out to be tricky :/
I'm late here, but let me drop 2 cents. I've implemented something like this for myself in Python and Rust, also working with OSM streets data.
The best way to use was to have "line-substring" method with "from" and "to" fractions or distances. If I were to code this, I'd have 2 separate methods, to avoid confusion. The "parameter" mode makes sense, and I'd make it separate as well.
Other options were:
I've implemented something like this for myself in Python and Rust, also working with OSM streets data.
Is your implementation public? Would love to check it out if so. (Currently looking through https://github.com/culebron/rust_routing/ -- cool stuff!)
Is your implementation public? Would love to check it out if so. (Currently looking through https://github.com/culebron/rust_routing/ -- cool stuff!)
Thanks, actually the credit goes to you, who inspired me to try Rust. I implemented that before learning of fast_paths
crate, and it turned out not so useful, because ALT algorithm doesn't work as advertized (no speedup, nodes visited reduced x2, not x20).
Here's the Python and Rust code, free to use. Actually, it turned out I did use cutting in Python, but had to add a convenient wrapper around it.
```python def line_substring(line, start=None, end=None): if start is not None: start = clip_position(line.length, start) if end is not None: end = clip_position(line.length, end) if end is not None and start is not None: if end < start: start, end = end, start end -= start return cut_line(cut_line(line, start)[1], end)[0] def clip_position(length, position): if position is None: return None if position < -length: return 0 if position > length: return length if position < 0: return position + length return position def cut_line(line, distance): # Cuts a line in two at a distance from its starting point empty_line = LineString() if distance is None: return line, line if line is None or line.is_empty: return empty_line, empty_line distance = clip_position(line.length, distance) if distance == 0: return empty_line, line if distance >= line.length: return line, empty_line coords = list(line.coords) points = [Point(p) for p in coords] distances = [[line.project(p), p] for p in points] distances[-1][0] = line.length if not any(d == distance for d, p in distances): distances += [[distance, line.interpolate(distance)]] distances = sorted(distances, key=lambda v: v[0]) line1 = [p for d, p in distances if d <= distance] line2 = [p for d, p in distances if d >= distance] line1 = LineString(line1) if len(line1) > 1 else empty_line line2 = LineString(line2) if len(line2) > 1 else empty_line return line1, line2 ```
```rust
use geo::{Coord, LineString, EuclideanDistance, LineInterpolatePoint, EuclideanLength};
pub trait LineSubstring {
fn sub_frac(&self, start: f32, end: f32) -> Option
Closing this for the time being. If you find the time to work on this, please reopen!
CHANGES.md
if knowledge of this change could be valuable to users.cargo fmt --all -- --check
[ ] ran
cargo clippy --all-features --all-targets -- -Dwarnings
Split a
Line
orLineString
based on one or two fractional distances along the length using proposed trait methodsLineSplit::line_split(fraction)
andLineSplit::line_split_twice(fraction_start, fraction_end)
Previously discussed in #378 and #986
Needed for #935 see this comment
Still to do / discuss
Instead ofIn addition toline_split_twice
, considerline_split_many
. Being able to split atn
locations is desirable as discussed in #985 and #986line_split_twice
?line_split_many
LineSplit
trait's default implementation forline_split_many
andline_split_twice
are failing tests due to precision issues which arise because these use a lazy implementation which just repeatedly applies theline_split
function. The error seems to compound much faster than I expected 😞 For the same reasons, these methods are also super inefficient.None
? Or just automatically swap thefraction_start
&fraction_end
arguments? Currently it does the latter.Consider supportingparameter
andlength_along
in addition tofraction
(see discussion below)Perhaps in a future PR
Consider breakingmeasure_line_string()
into a separate trait?Perhaps in a future PR
Consider optimization using dedicated prepared geometry typesLineStringMeasured
andLineMeasured
(see discussion below)Perhaps in a future PR
Example Usage
Click to expand code examples
Line LineSplit::line_split() ```rust let line = Line::new( coord! {x: 0.0_f32, y:0.0_f32}, coord! {x:10.0_f32, y:0.0_f32}, ); let result = line.line_split(0.6); assert_eq!( result, Some(LineSplitResult::FirstSecond( Line::new( coord! {x: 0.0_f32, y:0.0_f32}, coord! {x: 6.0_f32, y:0.0_f32}, ), Line::new( coord! {x: 6.0_f32, y:0.0_f32}, coord! {x:10.0_f32, y:0.0_f32}, ) )) ); ``` LineString LineSplit::line_Split() ```rust let line_string: LineStringImplementation Notes
Return Types
At first I tried implementing the return types like
Option<(Option<Line>, Option<Line>)>
but this causes issues in the implementation (non exhaustive match statements) and uncertainty for the user; The user may expect to possibly receiveSome((None, None))
which is never possible.Therefore the following types were implemented:
line_split
returnsOption<LineSplitResult<T>>
andline_split_twice
returnsOption<LineSplitTwiceResult<T>>
So that we get the best of both worlds I implemented
LineSplitResult::as_tuple()->(Option<&T>, Option<&T>)
and a set of single item accessors likeLineSplitResult::first()
andLineSplitResult::second()
which returnOption<&T>
I also added
.into_
variants, eginto_first
andinto_tuple
to consume the result and discard other returned data.This works great for
line_split()
but for theline_split_twice()
function I am still wondering if these return types are the best option. For example theLineSplitTwiceResult::FirstThird
variant is pretty confusing, although from an implementation point of view it makes total sense; it happens when there is no 'Second' line segment because thefraction_start==fraction_end
.Further Thoughts
Fraction
vsLength-Along
vsParameter
A point on a line string can be identified in three ways; as a
fraction
of length along, as alength along
the line, or as something that I call 'parameter
'A parameter is just a float where the integer part represents the segment index and the fractional part represents the
fraction
along the next line segment. In my previous tinkering I found that many algorithms are naturally faster when using parameters internally. This is because they do not need to know the length of every segment, and the total length of the linestring. Only the segment with the fractional part needs to be measured.It seems natural to me that line intersection algorithms and line split algorithms should have the option to use 'parameter' instead of fraction.
LineStringMeasured
andLineMeasured
In previous projects I have implemented 'measured' types which might look something like
struct LineStringMeasure<T>{(coordinates:Vec<Coord<T>>, length_segments:Vec<T>, length_total:T}
. For repeated queries on the same line, these can massively reduce the number of repeated length calculations. No idea if it would result in real performance improvements because storing the extra data may reduce cache locality etc.