java - 線と形状の交点を取得する

Question

画像に示すように、カスタム形状があります。イメージ内の形状を覆う青い長方形が、その形状の境界ボックスを表しているとします。

外接する四角形の対角線の 1 つに線を引くと、交点を取得するにはどうすればよいですか (画像では緑色を使用して描かれています)。

私は Java2D を使用しています。画面上に形状を描画するすべての座標を含む GeneralPath があります。

Answer 1

考え

getPathIterator() メソッドを使用して、GenenralPath をそのセグメント (move-to、line-to、quad-to、cubic-to、close) に分解できます。ラインとの交点をセグメントごとに検索できるようになりました。

public static Point[] getIntersections(Path path, Line line) {
    List<Point> intersections = new ArrayList<Point>();
    PathIterator it = path.getPathIterator();
    double[] coords = new double[6];
    double[] pos = new double[2];
    while (!it.isDone()) {
        int type = it.currentSegment(coords);
        switch (type) {
        case PathIterator.SEG_MOVETO:
            pos[0] = coords[0];
            pos[1] = coords[1];
            break;
        case PathIterator.SEG_LINETO:
            Line l = new Line(pos[0], pos[1], coords[0], coords[1]);
            pos[0] = coords[0];
            pos[1] = coords[1];
            Point intersection = getIntersection(line, l);
            if (intersection != null)
                intersections.add(intersection);
            break;
        //...
        default:
            throw new IllegalStateException("unknown PathIterator segment type: " + type);
        }
        it.next();
    }
    return intersections.toArray(new Point[] {});
}

線・交点

線/線の交点は、たとえばベクトル代数を使用して直接計算できます。

• 2 次元の点/線は 3 次元のベクトル (x, y, w) で表されます
• 点 (x, y) は (x, y, 1) で表されます
• 点 p1 と p2 を通る直線は、p1 x p2 (外積) で与えられます。
• 2 つの直線 l1 = (a, b, c) と l2 = (d, e, f) の場合、交点は l1 x l2 (外積) で与えられます。
• 交差点を 2D に投影するには、x 座標と y 座標を w で割る必要があります。
• w = 0 の場合、単一の交点はありません

ライン/ベジエ交点

Path には、2 次および 3 次のベジエ曲線を含めることができます。直線とベジエ曲線の交点を見つけるには、いくつかのアルゴリズムを使用できます。次に例を示します。

• de Casteljau サブディビジョン
• ベジエ クリッピング
• ニュートン法
• 多項式の求根

De Casteljau サブディビジョンは実装が簡単ですが、比較的まれなケースでいくつかの問題があります。交差を計算できる数学ライブラリを使用したくない場合は、de Casteljau サブディビジョンを実装することをお勧めします。

編集: 別の方法として、パスのベジエ曲線セグメントを多数の線分で近似することもできます。次に、線/線の交点を見つけるだけです。

Answer 2

形状を定義する点のリストを反復処理します。(x,y) を直線の方程式に入れ、「解ける」かどうかを確認します。疑似コード -

int threshold = 0.01
for point in points: 
  if (point.y - m * point.x + c)^2 < threshold : 
    print "solution found"