Detecting self crossing in closed Bezier curves

Question

I've created a "blob" shape by patching cubic Bezier curves together (screenshot below). I'd like to be able to detect the situation where a curve has crossed over either itself or another curve and was wondering if there's a recommended approach or known algorithm for doing this?

One idea I had was to use a FlatteningPathIterator to decompose the shape into straight line segments and then detect whether a given segment crosses with another one, but I'd be interested in whether there's a better approach (as this will have quadratic performance). If I do pursue this method are there library functions in Java to detect whether two line segments are overlapping?

Thanks.

No Cross-Over

No Crossover http://www.freeimagehosting.net/uploads/7ad585414d.png

Cross-Over

Crossover http://www.freeimagehosting.net/uploads/823748f8bb.png

Answer 1

What you can do is take the vector function for the Bezier curve :

And equate the different bezier curves that make up your curve in pairs to see if there is a solution in [0,1]. Of course that would help in the case where the parts that overlap are part of different curves. It wont help in the case where one curve intersects itself...

EDIT :

I quoted the quadratic curve function so this is the cubic:

And it is indeed hard to solve the equation. As an alternative i propose to use a more loose method. What you can do is "split" each curve into n points and calculate their position using the function above. Then for each of those points you will consider a disk of arbitrary radius (depending on the sizes of the curves) and search for intersections of these disks. You will need to disregard intersections of sequential disks since the intersect only because they lie too close to each other on a single curve segment.

This method should be very fast but you can lose accuracy if you select "wrong" parameters (the n size and the radius) but you can experiment.

Answer 2

I think you can get a decent approximation by

• Using FlatteningPathIterator to get a polygon that approximates the blob.
• Dividing the path around the polygon into subpaths of nondecreasing y (that is, downward paths—imagine drawing the polygon using only downward strokes of the pencil).
• Walking the downward paths in concert, comparing each line segment only with line segments that at least overlap in the y dimension.

This is pretty simple and avoids the O(n²) performance you're worried about. For your average basic blob, like the ones in your illustration, there are only two downward paths.

You can reduce the number of comparisons further by keeping the downward paths sorted horizontally as you go (a TreeSet, perhaps).

Another way to compare only line segments that overlap in the y dimension is to use an interval tree.