Треугольник — квадратное испытание пересечения в 2d
Как я могу проверить, пересекаются ли треугольник и квадрат друг с другом?
Есть ли способ оптимизировать это, когда мы знаем, что это квадрат вместо прямоугольника? Кроме того, квадрат выровнен по оси, так что это должно повысить производительность?
Или я должен просто разбить квадрат на треугольники и дважды проверить треугольник на пересечении?
Редактировать: Чтобы уточнить: я пытаюсь проверить, не перекрывают ли эти две фигуры каким-либо образом. Таким образом, треугольник может быть внутри квадрата, а квадрат может быть внутри треугольника, и он должен возвращать true для этого тоже.
Решение
Сравните свой прямоугольник (или квадрат) с каждым ребром треугольника, взяв его вершины и построив уравнение линии для каждого ребра, с последовательным упорядочением (по часовой стрелке или против часовой стрелки вокруг треугольника).
Если прямоугольник находится полностью за пределами треугольника на любом ребре, он не пересекается.
Проверьте снова с краями прямоугольника против треугольника.
Потенциально повышается производительность, зная, что прямоугольник выровнен по оси, так как вы можете определить, какой угол с наибольшей вероятностью будет находиться внутри треугольника, и протестировать только этот, а не тестировать все четыре угла.
Является ли это победой или нет, зависит от реализации. Иногда бывает проще проверить вслепую четыре координаты, чем вычислять лучшую.
Проверка треугольника по отношению к прямоугольнику должна быть проще, так как линейные уравнения — это простые тесты по x или y, когда прямоугольник выровнен по оси.
Это обобщенная форма теста с разделительной осью — поиск линии или плоскости, которая разделяет два объекта, доказывая тем самым, что они не могут пересекаться. Если вы хотите большей производительности, вы можете найти ближайшие функции двух объектов, чтобы определить наиболее подходящую линию / плоскость, а не пробовать все из них.
Другие решения
Это классическая проблема обнаружения столкновений. Формы пересекаются, если выполняется любое из следующих условий:
- По крайней мере, одна вершина в треугольнике содержится в прямоугольнике.
- По крайней мере, одна вершина прямоугольника содержится в треугольнике.
- Любое ребро треугольника пересекает любое ребро прямоугольника.
Первые два условия охватывают возможности того, что одна из фигур полностью содержится в другой (в этом случае края не пересекаются).
Возможны некоторые оптимизации.
-
Вычислить описанные круги фигур. Столкновения могут быть исключены, если расстояние между центральными точками двух фигур больше, чем сумма радиусов описанных окружностей. Обратите внимание, что центральная точка окружности, которая ограничивает прямоугольник, является средней точкой его диагонали. Центральная точка описывающей окружности для треугольника может быть получена путем нахождения пересечения перпендикулярных биссектрис любых двух ребер. Два способа найти пессимистические оценки окружностей, которые будут полностью содержать треугольник: (1) использовать самый длинный край в качестве диаметра окружности и (2) создать ограничивающий прямоугольник с углами в (mintx, мятный), (mintx, maxty), (maxtx, maxty) а также (maxtx, мятный) где maxtx максимальная координата X любого угла треугольника, mintx минимальная координата X любого угла треугольника и т. д.
-
Формы можно перевести и повернуть так, чтобы одна из вершин прямоугольника находилась в начале координат, а основание прямоугольника находилось вдоль положительной оси X. Это упрощает поиск того, содержится ли вершина в треугольнике внутри прямоугольника.
Перемещение, вращение и пересечение линий — это очень хорошо понятные проблемы, и у вас не должно возникнуть проблем с поиском подходящий код здесь на stackoverflow, здесь на стеке потока, или в другом месте в Интернете.
подсказки:
- Перевод прост — добавьте или вычтите одно и то же значение из каждой координаты X или Y.
-
Концептуально вращение легко — для каждой точки преобразуйте в полярные координаты, добавьте или вычтите угол поворота, а затем верните обратно в декартовы координаты. Поскольку преобразование в / из полярных координат является вычислительно дорогим, вы можете сделать вращение, используя формулы:
Xrot = X * cos (тета) — Y * sin (тета)
Yrot = X * sin (тета) + Y * cos (тета) -
Вы можете найти угол тета взяв сторону прямоугольника, и заметив, что
тета = atan2 (deltaX, deltaY)
В качестве уточнения ответа Джея Элстона вы можете разделить квадрат / четырехугольник на два треугольника и затем использовать Меллер-Trumbore алгоритм пересечения для сравнения включения вершин. Если вы читаете бумага опубликовано, есть реализация C алгоритма в конце.
Это позволит вам проверить наличие вершин. Тогда используйте одну из ссылок Джея для пересечений.