封闭bezier曲线的自交叉检测

实际上我已经找到了一个工作解决方案,它使用内置的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);
}
}

你所能做的就是取 Bezier curve :

并将组成成对曲线的不同贝塞尔曲线相等,以查看[0,1]中是否有解决方案。当然,如果重叠的部分是不同曲线的一部分,这会有所帮助。当一条曲线与自身相交时,它不会有帮助…

编辑:

我引用了二次曲线函数,所以这是三次曲线:

这个方程确实很难解。作为另一种选择,我建议使用更宽松的方法。你能做的就是把每条曲线“分割”成n个点,然后用上面的函数计算它们的位置。然后,对于这些点中的每个点,您将考虑任意半径的磁盘(取决于曲线的大小),并搜索这些磁盘的交点。您将需要忽略顺序磁盘的交点,因为这些交点只是因为它们在单个曲线段上彼此太近。

这个方法应该很快,但是如果你选择了“错误的”参数(n大小和半径),你可能会失去准确性,但是你可以进行实验。

我想你可以通过

• 使用 FlatteningPathIterator 得到一个近似于blob的多边形。
• 将多边形周围的路径划分为非渐变的子路径 Y (也就是说,向下的路径想象只使用铅笔向下的笔划绘制多边形)。
• 一致地沿着向下的路径行走,只将每条线段与至少重叠在 Y 尺寸。

这很简单,避免了( n ^二 )你担心的表现。对于一般的基本blob,如图中所示,只有两条向下的路径。

您可以进一步减少比较的数量,方法是保持向下的路径在运行时水平排序(a TreeSet 也许吧。

另一种只比较 Y 维度是使用 interval tree .

我不确定这是否有帮助,但它类似于多边形渲染中的一个问题,对于每个扫描行y,有一个(x,flag)值对数组,其中的行穿过该扫描行。

沿着形状中的每条曲线,在它穿过每条扫描线y的地方,记录(x,flag),其中flag=1表示“北”,flag=-1表示“南”。

如果在每一条扫描线上,按x顺序考虑两个x值对,并保持标志值的连续和,则两个x值的跨度之间的和在曲线为顺时针时为正,在曲线为逆时针时为负。

如果“所有跨距”为+1或“所有跨距”为-1,则曲线不会与自身相交。

编辑:这需要时间线性扫描线的数字交叉。然后,生成的数据结构可用于呈现图形。

这里有一些递归算法 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;
    }
  }

在哪里? delta^2(b_i) 定义为 b_{i+2} - 2*b_{i+1} + b_i .