Тест столкновения между треугольником и прямоугольником (AABB) в 2D

Question

Я потратил много времени на то, чтобы пересечения правильно работали между различными 2D-фигурами (круг-круг, круг-три, круг-прямоугольник, прямоугольник-прямоугольник) - огромное спасибо тем, кто решил такие проблемы, из которыхЯ взял свои решения из) для простого проекта и сейчас пытаюсь реализовать тест пересечения треугольник-AABB.

Однако я немного застрял.Я пытался искать в Интернете и обдумывать это, однако я не смог получить какие-либо идеи.Самая большая проблема в данный момент - это проверка того, пересекаются ли ребра треугольника (который является равнобедренным), если в нем нет вершин.

Есть идеи, как мне это сделать??

РЕДАКТИРОВАТЬ: Чтобы немного лучше понять этапы, как я думаю, они должны происходить:

1 - Проверьте, не лежат ли какие-либо вершины в прямоугольнике (эта часть проста),Если да, столкновение, в противном случае продолжите.

2 - Проверьте, не пересекаются ли какие-либо ребра с прямоугольником.Вот где я застрял.Я понятия не имею, как это реализовать.

Answer 1

Я бы рассчитал набор уравнений, которые определяют 4 линии прямоугольника, а затем решил бы против набора уравнений, которые определяют линии треугольника.

Например, если дать прямоугольник с самой низкой точкой (x1, y1) и одной стороной с градиентом g, одна из линий прямоугольника будет y = gx + y1. Найти уравнения для представления других 3 сторон прямоугольника.

Линии, которые формируют стороны треугольника, будут рассчитаны аналогично. Уравнение для линии с двумя точками равно

y - y1 = (x - x1) * (y2 - y1)/(x2 - x1)

Если есть какие-либо возможные значения x & y, которые удовлетворяют всем 7 уравнениям, то у вас есть пересечение.

edit: я понимаю, что, хотя это простой алгоритм, его было бы сложно кодировать; Другой вариант - вычислить формулы для интервалов , которые образуют каждое ребро (по существу, линии с минимальным и максимальным значением) и решить их.