CODEWITHSUNDEEP
algorithmgeometry
zigzag
zigzag

Reputation: 627

Split self-intersecting path into simple non-self-intersecting paths

What is an efficient way to split a self-intersecting open path into multiple simple non-self-intersecting paths?

Path is in 2D space made of connected line segments. It can be represented by a collection of points, where the first point is a start of a path and the last point is an end of a path. (e.g. black path in the picture)

I'm using Clipper2 library to create a buffer around a path (blue outline in the picture is the desired outcome), but Clipper.InflatePaths() doesn't support self-intersecting paths. So, I need to break down any complex (self-intersecting) path into multiple simple (non-self-intersecting) paths (see right side of the picture for example), as an intermediate step of buffer creation.

  1. Split complex path to simple paths
  2. Create buffer around each simple path (Clipper.InflatePaths())
  3. Union all buffers (Clipper.Union()) to create a single buffer polygon.

enter image description here

Upvotes: 2

Views: 436

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

There are certainly ways to do what you ask for, but there are easier ways to do what you want.

The easiest way is to inflate each line segment separately and then union all the results.

The next-easiest way is to break paths to keep the range of directions travelled along the path within 180 degrees, since it is impossible for resulting path to intersect itself.

Upvotes: 1

Related Questions