Split a polygon by linestrings

[dabreegster]

How hard would it be to support splitting a polygon by one or more linestrings? I could approximate this today by first buffering the linestring into a very thin polygon (using something like https://github.com/jbuckmccready/cavalier_contours) and then using difference. But it'd be quite useful to avoid the buffering step and have the resulting pieces fit together without any gaps.

[NailxSharipov]

Currently, structures like LineString are not supported. I have some ideas on how to implement them, but it will take time to explore fully, so I don't expect to add this feature in the near future.

For now, you can achieve this by creating a thin polygon with 2px height. It's a dirty hack, but must work.

[dabreegster]

Thanks for the quick reply. I've been thinking about ways of implementing this, and have come up with:

1. Brute-force look for all intersections between all of the input linestrings and the polygon's boundary. Split each of them into smaller linestrings when those intersections happen. (An r-tree can speed up the search) (Edit: this sounds quite similar to your overlay graph)
2. Create an undirected graph from all of the linestrings
3. Find all cycles in the graph, collecting the points in order as it goes. Each cycle is a resulting polygon. This could be done by visiting every unvisited edge in the graph, then figuring out how to consistently trace either clockwise or counter-clockwise.

I think I've attempted some parts of this before, but gotten stuck on floating point issues (from bad input geometry with self-intersections; but the application I have in mind now would be much better) and the clockwise ordering. But reading through https://ishape-rust.github.io/iShape-js/overlay/extract/extract_shapes.html and your use of fixed-precision vectors, I think something like this could work. As I have time, I'll try something like this and keep you posted, in case the result is useful to adapt here.

[NailxSharipov]

Current logic is using sweep line algorithm for splitting edges. No need to fix it.
It operates with:

pub(crate) struct Segment {
    pub(crate) x_segment: XSegment,
    pub(crate) count: ShapeCount,
    // need to add cutting marker 
}

For adding split lines we need only add some marker enum or bool value to Segment is it a special segment. One thing to be care here, it's current logic delete all segments with count: ShapeCount == 0. Must not do it for special segment. Probably better to add marker dirctly to ShapeCount struct.

a < b always! (a.x < b.x || a.x == b.x && a.y < b.y)

pub(crate) struct XSegment {
    pub(crate) a: IntPoint,
    pub(crate) b: IntPoint,
}

winding count

pub struct ShapeCount {
    pub(crate) subj: i32,
    pub(crate) clip: i32,
}

after splitting and filling steps we get a graph:

pub struct OverlayGraph {
    pub(crate) solver: Solver,
    pub(crate) nodes: Vec<OverlayNode>,
    pub(crate) links: Vec<OverlayLink>,
}

pub(crate) struct OverlayLink {
    pub(crate) a: IdPoint,
    pub(crate) b: IdPoint,
    pub(crate) fill: SegmentFill,
}

pub type SegmentFill = u8;

And for fill we use only first 4 bits. We can use 5th bit as slicing marker.

Next, we need to rework OverlayGraph::extract_shapes_min_area, with a focus on the sub-function find_nearest_counter_wise_link_to. It doesn’t seem like a huge task, and I’ll aim to implement it next week.

This could be useful both for slicing and filtering such lines.

However, I’m not sure what else we can do with these LineStrings. May be I’m missing some use cases, which makes it hard for me to plan an optimal API for them.

[dabreegster]

I prototyped over the weekend and got an edge splitter to work, and started on extracting faces from a planar graph, but there are bugs with sorting the edges clockwise (that I know how to fix, just need more time). I don't understand iOverlay well enough to follow most of what you wrote, but I'm sure your implementation is going to wind up much more general and nice.

I can help with use cases though. In https://github.com/a-b-street/ltn and some other applications (mesh density image from TfL's doc, page 15), a large area needs to be partitioned by a bunch of "main" roads and "severances" such as rivers and railways:


So given a large polygon covering the whole area (sometimes just a bounding box, sometimes a more detailed shape) and a bunch of linestrings representing segments of roads and rivers, split the polygon into smaller pieces. A final API like split_polygon(Polygon, Vec<LineString>) -> Vec<Polygon> is my aim. I've attempted calculating this kind of thing directly on a rich graph structure from the road network, but a road network isn't always a planar graph (when bridges / tunnels are involved) and the method is quite brittle. I've since recognized the usefulness of just doing this at the geometric level, then later relating it back to the road network structure.

A use case for #6, clipping a linestring to a polygon (or maybe it's easier to frame this as "split a linestring by a polygon", fn split_linestring(LineString, Polygon) -> Vec<LineString>) is simpler. In some analyses I work on, a road segment needs to be assigned to a census zone. Most roads are fully within one zone, but sometimes they cross, and it's useful to either pick the zone that contains most of the road by length, or to split the road into two pieces.

If it's helpful to generate some "real world" inputs, I can do it easily from OpenStreetMap data from different places. If so, I assume Euclidean space is necessary. Is GeoJSON (with Euclidean coordinates) a useful format for you to work with, or do you prefer something else for encoding lists of points?

[dabreegster]

Edit: it's kind of a diversion, but if you'd like to explore my prior approach of tracing around road boundaries and gluing them together to make large areas, it's still online:

1. https://play.abstreet.org/0.3.49/abstreet.html?--dev
2. Press Ctrl+D to enter a debug mode
3. Press Ctrl+B to enter "blockfinding" mode
4. Play around with merging adjacent blocks
   

This approach of building up areas "bottom-up" is unfortunately brittle. The same problems can be solved by dividing a large area by the "important" linestrings, and that problem might be very nicely solvable here