10

3 次ベジエ曲線をつなぎ合わせて「ブロブ」形状を作成しました (下のスクリーンショット)。曲線がそれ自体または別の曲線を越えた状況を検出できるようにしたいのですが、これを行うための推奨されるアプローチまたは既知のアルゴリズムがあるかどうか疑問に思っていましたか?

私が持っていたアイデアの 1 つは、 a を使用しFlatteningPathIteratorて形状を直線セグメントに分解し、特定のセグメントが別のセグメントと交差するかどうかを検出することでしたが、より良いアプローチがあるかどうかに興味があります (これは 2 次パフォーマンスになるため)。この方法を追求する場合、2 つの線分が重なっているかどうかを検出する 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

あなたができることは、ベジエ曲線のベクトル関数を取ることです:

代替テキスト

そして、[0,1] に解があるかどうかを確認するために、曲線をペアで構成するさまざまなベジエ曲線を同等にします。もちろん、重なり合う部分が異なる曲線の一部である場合に役立ちます。1 つの曲線が交差する場合は役に立ちません...

編集 ：

二次曲線関数を引用したので、これは三次です。 代替テキスト

そして、方程式を解くのは確かに難しいです。別の方法として、より緩い方法を使用することを提案します。できることは、各曲線を n 個の点に「分割」し、上記の関数を使用してそれらの位置を計算することです。次に、これらの点のそれぞれについて、(曲線のサイズに応じて) 任意の半径の円盤を検討し、これらの円盤の交点を検索します。シーケンシャル ディスクの交点は無視する必要があります。交差するのは、それらが 1 つの曲線セグメント上で互いに近すぎるためだけです。

この方法は非常に高速ですが、「間違った」パラメータ (n サイズと半径) を選択すると精度が失われる可能性がありますが、実験することはできます。

于 2010-01-26T12:30:25.450 に答える
1

これが役立つかどうかはわかりませんが、ポリゴン レンダリングの問題に似ています。各スキャン ライン Y に対して、ラインがそのスキャン ラインと交差する (X, flag) 値ペアの配列があります。

形状の各曲線をたどり、各走査線 Y と交差する場所で (X, flag) を記録します。ここで、「北」に向かう場合は flag = 1、「南」に向かう場合は flag = -1 です。

各スキャン ラインでペアを X 順で考慮し、フラグ値の実行中の合計を保持する場合、2 つの X 値のスパン間の合計は、曲線が時計回りの場合は正になり、曲線が反時計回りの場合は負になります。

すべてのスパンが +1 またはすべてのスパンが -1 の場合、曲線は交差しません。

編集：これは、図が交差するスキャンラインの数に比例して時間がかかります。次に、結果のデータ構造を使用して Figure をレンダリングできます。

于 2010-01-26T14:40:48.210 に答える
1

私はあなたがまともな近似値を得ることができると思います

  • FlatteningPathIteratorブロブを近似するポリゴンを取得するために使用します。
  • ポリゴンの周りのパスを非減少yのサブパス(つまり、下向きのパス — 鉛筆の下向きのストロークのみを使用してポリゴンを描画することを想像してください) に分割します。
  • 下降経路を一斉に歩き、各線分を少なくともy次元で重なる線分のみと比較します。

これは非常に単純で、心配しているO( n 2 ) のパフォーマンスを回避します。図のような平均的な基本的なブロブには、下向きのパスが 2 つしかありません。

進むにつれて下向きのパスを水平にソートしておくことで、比較の数をさらに減らすことができます (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 に答える