Detecting self crossing in closed Bezier curves

I've 开发者_StackOverflowcreated 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

I have actually found a working solution which is using built in Java2D functions and is EXTREMELY fast...

Simply create a Path2D out of your curves, then create an area out of your Path2D and invoke the method Area.isSingular();

It works... See this small example.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Area;
import java.awt.geom.CubicCurve2D;
import java.awt.geom.Path2D;

import javax.swing.JFrame;
import javax.swing.JPanel;



public class Test {
@SuppressWarnings("serial")
public static void main(String[] args) {
    JFrame f = new JFrame("Test");
    JPanel c = new JPanel() {
        Area a;
        Path2D p;
        {
            p = new Path2D.Double();
            p.append(new CubicCurve2D.Double(0, 0, 100, 0, 150, 50, 200, 100), true);
            p.append(new CubicCurve2D.Double(200, 100, 200, 150, 150,0, 50, 100), true);
            p.append(new CubicCurve2D.Double(100, 100, 100, 50, 50, 50, 0, 0), true);
            a = new Area(p);
            setPreferredSize(new Dimension(300, 300));
        }
        @Override
        protected void paintComponent(Graphics g) {
            g.setColor(Color.black);
            ((Graphics2D)g).fill(p);
            System.out.println(a.isSingular());
        }
    };
    f.setContentPane(c);
    f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    f.pack();
    f.setVisible(true);
}
}

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.

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.

I'm not sure if this helps, but it is similar to a problem in polygon rendering, where you have, for each scan line Y, an array of (X, flag) value pairs where lines cross that scan line.

Follow each curve in the shape, and where it crosses each scan line Y, record (X, flag) where flag = 1 if going "north" and flag = -1 if going "south".

If on each scan line you consider the pairs in X order, and keep a running sum of the flag values, then the sum between a span of two X values will be positive if the curve is clockwise, and negative if the curve is counterclockwise.

If all spans are +1 or all spans are -1, the curve does not cross itself.

Edit: this takes time linear in the number of scan lines crossed by the figure. Then the resulting data structure can be used to render the figure.

Here some recursive algorithm from a lecture of Prof. Georg Umlauf

INTERSECT(b_0,...,b_m;c_0,...,c_n, EPSILON)
  if [min b_i, max b_i] AND [min c_i, max c_i] != EMPTY { // check bounding boxes
    if m*(m-1)*max||delta^2(b_i)|| > EPSILON) { // check flatness
      Calculate b'_0, ..., b'_2m over [0, 0.5, 1] with the deCasteljau algorithm;
      INTERSECT(b'_0,...,b'_m;c_0,...,c_n;EPSILON);
      INTERSECT(b'_m,...,b'_2m;c_0,...,c_n;EPSILON);
    }
  }
  else {
    if (n*n-1)*max||delta^2(c_i)|| > EPSILON then {
      Calculate c'_0, ..., c'_2m over [0, 0.5, 1] with the deCasteljau algorithm;
      INTERSECT(b_0,...,b_m;c'_0,...,c'_n;EPSILON);
      INTERSECT(b_0,...,b_m;c'_n,...,c'_2n;EPSILON);
    }
    else {
      Intersect line segments b_0b_m and c_0c_n;
    }
  }

where delta^2(b_i) is defined as b_{i+2} - 2*b_{i+1} + b_i.