检测闭合Bezier曲线中的自交叉

Question

我通过将立方贝塞尔曲线拼接在一起创建了一个"blob"形状(截图如下).我希望能够检测到曲线越过自身或其他曲线的情况,并且想知道是否有推荐的方法或已知的算法来执行此操作？

我的一个想法是使用a FlatteningPathIterator将形状分解为直线段然后检测给定的段是否与另一个段相交,但我对是否有更好的方法感兴趣(因为这将具有二次性能).如果我继续追求这种方法,Java中的库函数是否检测两个线段是否重叠？

谢谢.

没有交叉

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

交叉

交叉http://www.freeimagehosting.net/uploads/823748f8bb.png

Answer 1

我实际上找到了一个工作解决方案，它使用内置的 Java2D 函数并且速度非常快......

只需从曲线中创建一个 Path2D，然后从 Path2D 中创建一个区域并调用方法 Area.isSingular();

它有效......请参阅这个小例子。

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);
}
}