5

よし、簡単な小惑星のクローンを作ろうとしている。衝突検出を除いて、すべて正常に動作します。

私は2つの異なるバージョンを持っています.最初のものはjava.awt.geom.Areaを使用しています:

// polygon is a java.awt.Polygon and p is the other one
final Area intersect = new Area();
intersect.add(new Area(polygon));
intersect.intersect(new Area(p.polygon));
return !intersect.isEmpty();

これは魅力のように機能します...たった120個の小惑星に対して40％のCPUを気にしないなら:(

そこで、有名な分離軸定理をネットで検索しました。数学が苦手なので、ここから実装を取得し、Java のニーズに合わせて変換しました。

public double dotProduct(double x, double y, double dx, double dy) {
        return x * dx + y * dy;
    }

    public double IntervalDistance(double minA, double maxA, double minB,
            double maxB) {
        if (minA < minB) {
            return minB - maxA;
        } else {
            return minA - maxB;
        }
    }

    public double[] ProjectPolygon(double ax, double ay, int p, int[] x, int[] y) {
        double dotProduct = dotProduct(ax, ay, x[0], y[0]);
        double min = dotProduct;
        double max = dotProduct;
        for (int i = 0; i < p; i++) {
            dotProduct = dotProduct(x[i], y[i], ax, ay);
            if (dotProduct < min) {
                min = dotProduct;
            } else if (dotProduct > max) {
                max = dotProduct;
            }
        }
        return new double[] { min, max };
    }

    public boolean PolygonCollision(Asteroid ast) {
        int edgeCountA = points;
        int edgeCountB = ast.points;
        double edgeX;
        double edgeY;

        for (int edgeIndex = 0; edgeIndex < edgeCountA + edgeCountB; edgeIndex++) {
            if (edgeIndex < edgeCountA) {
                edgeX = xp[edgeIndex] * 0.9;
                edgeY = yp[edgeIndex] * 0.9;
            } else {
                edgeX = ast.xp[edgeIndex - edgeCountA] * 0.9;
                edgeY = ast.yp[edgeIndex - edgeCountA] * 0.9;
            }

            final double x = -edgeY;
            final double y = edgeX;
            final double len = Math.sqrt(x * x + y * y);
            final double axisX = x / len;
            final double axisY = y / len;

            final double[] minMaxA = ProjectPolygon(axisX, axisY, points, xp,
                    yp);
            final double[] minMaxB = ProjectPolygon(axisX, axisY, ast.points,
                    ast.xp, ast.yp);

            if (IntervalDistance(minMaxA[0], minMaxA[1], minMaxB[0], minMaxB[1]) > 0) {
                return false;
            }
        }
        return true;
    }

それは動作します...ちょっと。実際、このコードを使用すると、小惑星の「衝突船体」が大きすぎて、小惑星の 1.2 倍のサイズになるようです。そして、私には理由がわかりません。

比較のための 2 つの写真を次に示し
ます
。

うまくいけばわかるように、写真 1 の小惑星は、SAT コードを使用している写真 2 の小惑星よりもはるかに密度が高いです。

アイデアはありますか？または、私が使用できる交差テストを備えた Java の Polygon 実装を知っている人はいますか?

4

1 に答える 1

4

2番目の結果は、ポリゴンが中心からポリゴンの最も遠い点に半径が設定された円であるかのように、衝突検出を行っているようです。私が見たほとんどの衝突検出は、ポリゴンが収まる単純な境界ボックス (円または長方形) を作成します。2 つのバウンディング ボックスが交差する場合 (はるかに単純な計算) のみ、より詳細な検出に進みます。おそらく、割り当てられたアルゴリズムは、境界ボックスの計算のみを目的としていますか?

編集：また、ウィキペディアから

ボディの 1 つが凸でない場合、定理は適用されません。

画像内の小惑星の多くは、凹面を持っています。

于 2009-10-26T22:56:25.347 に答える