检测闭合贝塞尔曲线中的自交叉

Question

我通过将三次贝塞尔曲线修补在一起创建了一个“斑点”形状（下面的屏幕截图）。我希望能够检测曲线与自身或另一条曲线交叉的情况，并且想知道是否有推荐的方法或已知的算法可以做到这一点？

我的一个想法是使用 FlatteningPathIterator 将形状分解为直线段，然后检测给定的线段是否与另一个线段交叉，但我感兴趣的是是否有更好的方法（如这将具有二次性能）。如果我确实采用这种方法，Java中是否有库函数可以检测两条线段是否重叠？

谢谢。

无交叉

无交叉 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);
}
}

Answer 2

您可以做的是采用 贝塞尔曲线 的矢量函数：

并将成对组成曲线的不同贝塞尔曲线等同起来，看看 [ 中是否有解决方案0,1]。当然，这在重叠部分属于不同曲线的情况下会有所帮助。在一条曲线与自身相交的情况下它不会有帮助...

编辑：

我引用了二次曲线函数，所以这是三次曲线：

求解方程确实很难。作为替代方案，我建议使用更宽松的方法。您可以做的是将每条曲线“拆分”为 n 个点，并使用上面的函数计算它们的位置。然后，对于每个点，您将考虑任意半径的圆盘（取决于曲线的大小）并搜索这些圆盘的交点。您将需要忽略连续圆盘的相交，因为相交只是因为它们在单个曲线段上彼此距离太近。

此方法应该非常快，但如果选择“错误”参数（n 大小和半径），则可能会失去准确性，但您可以进行实验。

Answer 3

获得不错的近似值

• 我认为您可以通过使用 FlatteningPathIterator 获得近似斑点的多边形来
• 。将多边形周围的路径划分为非递减 y 的子路径（即，向下路径 - 想象一下仅使用铅笔向下的笔触绘制多边形）。
• 一致地沿着向下的路径行走，仅将每个线段与至少在 y 维度上重叠的线段进行比较。

这非常简单，并且避免了您担心的 O(n²) 性能。对于普通的基本斑点（如插图中的斑点），只有两条向下的路径。

您可以通过保持向下路径水平排序来进一步减少比较次数（也许是一个TreeSet）。

仅比较 y 维度中重叠的线段的另一种方法是使用 区间树。

Answer 4

我不确定这是否有帮助，但它类似于多边形渲染中的问题，其中对于每条扫描线 Y，都有一个（X，标志）值对的数组，其中线与该扫描线交叉。

沿着形状中的每条曲线，以及它与每条扫描线 Y 相交的位置，记录 (X, flag)，其中如果向“北”行则 flag = 1，如果向“南”行则 flag = -1。

如果在每条扫描线上按 X 顺序考虑这些对，并保留标志值的运行总和，则如果曲线是顺时针方向，两个 X 值跨度之间的总和将为正值，如果曲线是逆时针方向，则两个 X 值跨度之间的总和将为负值。

如果所有跨度均为 +1 或所有跨度均为 -1，则曲线不会与自身相交。

编辑：这需要与图形穿过的扫描线数量成线性关系的时间。然后生成的数据结构可用于渲染图形。

Answer 5

这里有一些递归算法来自 教授的讲座。 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。