Clip a linestring to a polygon

[dabreegster]

How hard would it be to implement a clip operation taking a polygon and linestring, and returning the piece of the linestring that intersects the polygon? I think the linestring could already be represented by a path, but I haven't yet tried to see if I can pass in a path that isn't a valid loop.

[NailxSharipov]

Supporting LineString or similar structures is quite a complex feature to add. The library doesn't currently support LineString at all. First I need to think about how best to integrate this.

[NailxSharipov]

Considering new StringGraph it's became possible.

Here's how it can be achieved:

trait Clip api:

let path: F32Path = vec![
    F32Point::new(-10.0, -10.0),
    F32Point::new(-10.0, 10.0),
    F32Point::new(10.0, 10.0),
    F32Point::new(10.0, -10.0),
];
let inside_lines = path.clip_line(
    [F32Point::new(0.0, -15.0), F32Point::new(0.0, 15.0)],
    FillRule::NonZero,
    ClipRule { invert: false, boundary_included: false },
);

let outside_lines = path.clip_line(
    [F32Point::new(0.0, -15.0), F32Point::new(0.0, 15.0)],
    FillRule::NonZero,
    ClipRule { invert: true, boundary_included: false },
);

F32StringOverlay api:

let path: F32Path = vec![
    F32Point::new(-10.0, -10.0),
    F32Point::new(-10.0, 10.0),
    F32Point::new(10.0, 10.0),
    F32Point::new(10.0, -10.0),
];

let line = [F32Point::new(0.0, -15.0), F32Point::new(0.0, 15.0)];

let mut overlay = F32StringOverlay::new();

overlay.add_shape_path(path);
overlay.add_string_line(line);

let graph = overlay.into_graph(fill_rule);

let inside_lines = graph.clip_string_lines(ClipRule { invert: false, boundary_included: false });
let outside_lines = graph.clip_string_lines(ClipRule { invert: true, boundary_included: false });

[michaelkirk]

This looks great!

I haven't dug in yet, but the signature surprised me:

pub fn clip_string_lines(&self, clip_rule: ClipRule) -> Vec<F64Line>

I was expecting something like:

pub fn clip_string_lines(&self, clip_rule: ClipRule) -> Vec<F64Path>

In the trivial case, it's probably the same:

But when the line re-enters the shape, it'd be nice to have separate paths for each of the contiguous segments:

I haven't looked yet, but I'm hoping I can trivially assemble the contiguous segments myself, just by inspecting the F64Line, and starting a new F64Path whenever the next F64Line is disjoint from the previous.

[NailxSharipov]

Right now the result is a set of unordered, disjoint segments. However, returning connected paths instead is achievable, especially if it's not necessary to satisfy the original path order.

[michaelkirk]

Interestingly enough, my naive assumption that the output line segments would be in order of their input was able to pass my test cases, but it sounds like you're saying that's a coincidence.

Is there existing code in i_overlay that would be useful for merging the disjoint segments? I don't particularly care about ordering.

[NailxSharipov]

If path is more preferable approach the most easy way to achieve it. Is convert overlay into graph and then extract paths using deep search.

[NailxSharipov]

Replace output to Vec<F64Path> in 1.7.1

[michaelkirk]

I won't have time to test it until the end of the week, but the API looks to be exactly what I wanted. Thank you!

[michaelkirk]

Ok, I've tested this and it works great. Thank you for making this change!

I've added some additional test cases from JTS's Polygon x Line intersections, and am happy to see them all passing.

I've also done some preliminary benchmarks and it appears to be only a little slower than our existing implementation. Given that your library seems to avoid all the problems we've had with floating point resiliency, I'm happy to take a small performance hit, and will soon propose including your library in georust/geo.

[NailxSharipov]

I'm glad to hear everything is working well, and great job with testing new api. I also will add editor/test app soon for better testing from my side.

Regarding the performance hit, I wanted to suggest a potential optimization. The F64StringOverlay is useful when you need to accumulate your complex geometry, but if you already have all the geometry data upfront, it's preferable to use the trait-based API instead.

And here is why:

Currently, F64StringOverlay performs extra clone operations to accumulate all geometry first and then calculates a F64PointAdapter, which later converts the float data to int. These cloning steps could be avoided when we know all data, which is exactly the trait case.

Additionally, for trait case, some optimizations can be done at the int level, which should improve performance by 10-20%. I’m planning to implement these optimizations in the next version. I’ll keep you updated!

[michaelkirk]

Yes - I noticed it was a bit redundant to copy my Vec of f64 to your Vec of f64!

So, if I understand correctly, this trait based approach doesn't exist yet, but you're currently working on it? I'd be happy to give it a try once it's available.