Self-intersection removal in offset curves

2.8k Views Asked by At

When you compute offset curves (also called parallel curves), by offsetting a fixed distance along the normals to a given curve, the resulting curve self-intersects when the offset distance exceeds the radius of curvature (see below).

I am looking for a practical way to detect and remove the inner "pockets" that appear. The output should be a continuous curve with the self-intersection replaced by a corner point.

My curves are actually cubic arcs, but I work with flattening and discrete points, so one can see the curve as a smooth polyline. In a variant of the question, the offset is also varying along the curve.

enter image description here

Update:

There is a straightforward way to detect the cusps: they arise where the radius of curvature equals the offset distance. In the discrete setting, the osculating circle can be approximated by the circumscribing circle of three consecutive vertices.

In the figure, you see offset vertices, which are in red when the estimated curvature is smaller than the offset. This principle allows to find evidence of self-intersections.

enter image description here

I suspect that the "ladder" formed by the initial polyline and the corresponding offsetted points can help find the intersection efficiently.

enter image description here

1

There are 1 best solutions below

2
On

Since your curves are polygonal curves, the offset curves are also polygonal curves. For any given offset curve, you need to detect self-intersection, and then clip off the loop at the self-intersection point. You will need robust code for segment-segment intersection. Then you need to decide on how much you care about efficiency, and how complex an algorithm you are willing to code.

Self-intersection can be tested efficiently by a sweep-line algorithm, but that may be overkill here because the loops tend to be small, so intersections are likely to be local. You could find example algorithms by searching for "polygon self-intersection detection." For example: "Check if Polygon is Self-Intersecting."