# removing overlap (proposal)

*This is a proposal for an algorithm to remove overlap. It was
suggested as a replacement for the old algorithm in fontforge to give
better stability and correctness. Since work is being done to
incorporate the geometry library
lib2geom into fontforge, the
following algorithm is kept for reference purposes.*

**disclaimer:** *Currently this is work in progress. While the author
is positive that this information is helpful for anyone implementing
the algorithm, no guarantee is made for completeness or correctness.*

### The problem

The goal is to remove any overlapping regions from a set of closed paths. To determine if a point is on the interior or exterior of a path, the nonzero winding rule is used. The algorithm doesn’t depend on the type of curve used, as long as the following operations are supported:

- Given two curves, return all overlapping points
- Split a curve at a certain point into two curves.

#### Input:

A set of closed paths consisting of cubic bezier segments. We can see each curve as an directed edge, being directed from its first control point to its last. The following properties should be present:

- For every curve endpoint (first or last control point) the number of curves going in and out should be exactly the same.
- A point is on the inside of the path if the winding number is nonzero.

#### Output:

A set of curves, such that:

- No curves overlap except in the endpoints.
- Every offcurve point has a winding number of either zero or one.
- If a point has a nonzero winding number in the input, it will have a winding number of one in the output, otherwise zero.
- Some error may be acceptable due to floating point errors, as long as the deviation is small, and has no visual artifacts.

It is possible to give more requirements, like to minimize the number of curves used.

### Overview

The technique used is a plane sweep similar to the Bentley Ottman Algorithm for calculating intersections of line segments. This algorithm has a running time of \(O((n+k) log(n))\). This is not theoretically optimal, but it has a good trade-off between ease of implementation and efficiency.

The basic idea is to sweep a vertical line from left to right over all the elements. During the sweep information about adjacency and winding numbers is kept about all the segments that intersect the line. New intersections are calculated and inside curves are discarded.

### Detailed algorithm

*To be written.*

### Finding an intersection between two bézier curves

The most used curves in CAGD are bézier curves and NURBS. Good
algorithms exist for finding intersections between two bézier curves
of any degree. A fast and stable algorithm is *bézier clipping*. For
general information consult Computer Aided Geometry
Design by Thomas Sederberg,
paragraph 7.7. The paper Curve intersection by beziér
clipping
has more in-depth information about this algorithm.

It’s implemented in lib2geom, which can be used as a reference implementation. I also have an implementation in haskell.

A faster, but more involved algorithm is implicitization, which can be found in Computer Aided Geometry Design.