Пересечение полигонов не выполнено, слишком большой размер столкновения - PullRequest
Новая
       19

Пересечение полигонов не выполнено, слишком большой размер столкновения

5 голосов
/ 27 октября 2009

ОК, поэтому я пытаюсь сделать простой клон астероидов. Все отлично работает, кроме обнаружения столкновений.

У меня есть две разные версии, первая использует 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();

Это работает как шарм ... если вас не волнует 40% CPU только для 120 астероидов: (

Поэтому я искал в сети известную теорему о разделяющей оси, так как я не очень хорош в математике, я взял реализацию из здесь и преобразовал ее в соответствии со своими потребностями 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 раза больше размера астероида. И я понятия не имею, почему.

Вот две картинки для сравнения:
http://www.spielecast.de/stuff/asteroids1.png
http://www.spielecast.de/stuff/asteroids2.png

Как вы можете надеяться, астероиды на рисунке 1 намного плотнее, чем на рисунке 2, где используется код SAT.

Так есть идеи? Или кто-нибудь знает реализацию Polygon для Java с тестами пересечений, которые я мог бы использовать?

1 Ответ

4 голосов
/ 27 октября 2009

Похоже, что ваш второй результат заключается в обнаружении столкновений, как если бы полигоны были кругами с радиусом, установленным в самой отдаленной точке полигона от центра. Большинство обнаруженных столкновений создает простой ограничивающий прямоугольник (или круг, или прямоугольник), в который может поместиться многоугольник. Только если два ограничивающих прямоугольника пересекаются (гораздо более простой расчет), вы переходите к более детальному обнаружению. Возможно, соответствующий алгоритм предназначен только для калькулятора ограничивающего прямоугольника?

EDIT: Также из википедии

Теорема неприменима, если одно из тел не является выпуклым.

Многие астероиды на вашем изображении имеют вогнутые поверхности.

...