Clip in BooleanOps flips some of the LineStrings in the MultiLineString

[oyhj1801]

I'm working with directed LineStrings and when I try and clip a MultiLineString to a Polygon extent some of the LineStrings get reversed.

Before clipping:

After clipping

The teeth are pointing 90 degrees to the left of the direction of the LineString.
In the upper image some LineStrings are on top of each other where two tiles overlap, after clipping all map-tiles to the intended extent, no LinesStrings overlap but some have been reversed (indicated by the teeth pointing in the opposite direction) as can be seen in the bottom image.

[michaelkirk]

Are you seeing this on geo-0.29.0, just released yesterday? There was a major change to the clip operation.

Can you please provide a minimal example of the data set that produces this behavior?

[oyhj1801]

Yes this is on geo-0.29.0

I'll try and find an example

[oyhj1801]

The reversing seems to consistently happen when a LineString doubles back on it self outside of the clip extent.
Here is one example of the bug for a MultiLineString containing only a single LineString for a LineString generated by my program followed by a minimal example.


The red line is the input MulitLineString, containing only a single LineString, the green and blue are the output after clipping. The star symbolizes the end of a LineString.
The clipping extent of the minimal example is a square with bottom left corner in the origin and top right corner at (6,6)

[oyhj1801]

The reversing is not unique to geo 0.29 but happens for all versions 0.29 - 0.23

[dabreegster]

Do you have sample input data as WKT, GeoJSON, etc? Ideally a minimally runnable script that shows this behavior

[oyhj1801]

use geo::{coord, BooleanOps, LineString, MultiLineString, Polygon};

fn main() {
    // for any positive values in max coord > 3
    let max = coord! {x: 6., y: 6.};

    let extent = Polygon::new(
        LineString::new(vec![
            coord! {x: 0., y: max.y},
            coord! {x: 0., y: 0.},
            coord! {x: max.x, y: 0.},
            coord! {x: max.x, y: max.y},
            coord! {x: 0., y: max.y},
        ]),
        vec![],
    );

    let lines = MultiLineString::new(vec![LineString::new(vec![
        coord! {x: -1., y: max.y-1.},
        coord! {x: max.x-1., y: -1.},
        coord! {x: -1., y: 2.},
    ])]);

    let expected = MultiLineString::new(vec![
        LineString::new(vec![
            coord! {x: 0., y: max.y-1. - max.y/max.x * 1.},
            coord! {x: -1. + max.x/max.y * (max.y - 1.0), y: 0.},
        ]),
        LineString::new(vec![
            coord! {x: max.x-1. - max.x/3. * 1., y: 0.},
            coord! {x: 0., y: -1. - 3./max.x * -(max.x-1.)},
        ]),
    ]);

    let clipped_lines = extent.clip(&lines, false);

    println!("clip extent: {:?}", extent);
    println!("input: {:?}", lines);
    println!("output: {:?}", clipped_lines);
    println!(
        "expected: {:?} (ordered as encountered along the input)",
        expected
    );
}

Here you can see that the output differs from the expected in both the order of the segments (not important for me and guessing clip is not supposed to preserve 'internal' order anyways) and flips one of the output segments

[NailxSharipov]

Yes, current algorithm does not keep original order. The current logic just traverse the graph and in fact it can be absolutly random. But it's not hard to keep it, I just haven't know that it's important. I'll try to fix it in the next version.

[michaelkirk]

Thank you for the good reproduction @oyhj1801, and thank you for taking prompt interest @NailxSharipov!