10

我通过将三次贝塞尔曲线拼接在一起创建了一个“斑点”形状（下面的屏幕截图）。我希望能够检测到曲线越过自身或另一条曲线的情况，并且想知道是否有推荐的方法或已知的算法来执行此操作？

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

谢谢。

没有交叉

没有交叉 http://www.freeimagehosting.net/uploads/7ad585414d.png

交叉

跨界 http://www.freeimagehosting.net/uploads/823748f8bb.png

4

5 回答 5

4

我实际上找到了一个工作解决方案，它使用内置的 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);
}
}
于 2010-01-26T17:02:06.153 回答
2

您可以做的是采用Bezier 曲线的向量函数：

替代文字

并将构成曲线的不同贝塞尔曲线成对相等，以查看 [0,1] 中是否存在解。当然，这在重叠部分是不同曲线的一部分的情况下会有所帮助。在一条曲线与自身相交的情况下，它无济于事......

编辑 ：

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

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

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

于 2010-01-26T12:30:25.450 回答
1

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

沿着形状中的每条曲线，在它与每条扫描线 Y 相交的地方，记录 (X, flag) 如果去“北”，则 flag = 1，如果去“南”，则 flag = -1。

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

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

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

于 2010-01-26T14:40:48.210 回答
1

我认为你可以通过

  • FlatteningPathIterator用于获取近似于 blob 的多边形。
  • 将多边形周围的路径划分为不递减y的子路径（即向下路径——想象仅使用铅笔向下的笔划来绘制多边形）。
  • 一致地沿着向下的路径走，仅将每个线段与至少在y维度上重叠的线段进行比较。

这非常简单，并且避免了您担心的 O( n 2 ) 性能。对于您的平均基本 blob，就像您的插图中的那样，只有两条向下的路径。

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

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

于 2010-01-26T15:15:39.220 回答
0

这是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。

于 2010-01-27T09:59:01.253 回答