Как определить пересечение треугольника и прямоугольника?

Я разрабатываю игру для Android, и мне хотелось бы знать, как обнаружить столкновение прямоугольника, зная его положение (x и y), ширину и высоту, а также треугольник, зная x, y, ширину и высоту. Треугольники всегда являются прямоугольными в результате деления прямоугольника по его диагонали, поэтому параметр (x, y) будет положением в гипотенузе, а не центром треугольника. Любая помощь будет оценена по достоинству!


collision 2d-games
person Barbara PM    schedule 23.01.2013    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Я наконец сделал это, используя функцию пересечения для двух линий. Линии определены с начальной точкой (x, y) и конечной точкой (x, y)

// a1 is line1 start, a2 is line1 end, b1 is line2 start, b2 is line2 end
 static boolean intersects(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2)
{
    Vector2 intersection = Vector2.Zero();

    Vector2 b = Vector2.Subtract(a2,a1);
    Vector2 d = Vector2.Subtract(b2,b1);
    float bDotDPerp = b.getX() * d.getY() - b.getY() * d.getX();

    // if b dot d == 0, it means the lines are parallel so have infinite intersection points
    if (bDotDPerp == 0)
        return false;

    Vector2 c = Vector2.Subtract(b1,a1);
    float t = (c.getX() * d.getY() - c.getY() * d.getX()) / bDotDPerp;
    if (t < 0 || t > 1)
        return false;

    float u = (c.getX() * b.getY() - c.getY() * b.getX()) / bDotDPerp;
    if (u < 0 || u > 1)
        return false;

    intersection = Vector2.Sum(a1,Vector2.Multiply(b,t));

    return true;
}

Чтобы узнать, пересекает ли треугольник прямоугольник, вы проверяете пересечение каждой линии треугольника с каждой линией прямоугольника с функцией выше.

person Barbara PM    schedule 28.01.2013
comment
что, если прямоугольник полностью внутри треугольника? (или наоборот) - person urraka; 22.10.2013
comment
Чтобы обрабатывать полностью внутри, вы можете проверить, находится ли какая-либо точка (например, первая) одной формы внутри другой (2 дополнительные проверки). - person NateS; 14.11.2013
comment
Вы также можете использовать теорему SAT (теорема о разделяющей оси). - person szablica; 28.02.2014

arrow_upward
0
arrow_downward

Взгляните на отличную библиотеку пересечений многоугольников. Существует версия C ++, которую вы можете использовать на Android.

Другая возможность - растрировать изображение прямоугольника и другое изображение с треугольником и, наконец, проверить пиксель за пикселем, есть ли какое-либо пересечение между двумя изображениями.

person Dov Grobgeld    schedule 23.01.2013
comment
Растеризация в пиксели - это буквально самый медленный способ решить эту проблему. - person frodo2975; 07.02.2019