Как проверить, пересекаются ли треугольники?

Question

[Umid]

Моё почтение.
Задача: Сгенерировать 2 рандомных треугольника в системе координат, и проверить, пересекаются ли они.

Решил всё делать через canvas(а как же иначе).
Сгенерировать 2 раза по 3 отрезка (по координатам точек), проверить, что треугольник может получиться из них.
Затем соединить все три отрезка, что бы получились треугольники.

Интересует, как именно можно проверить пересекаются ли они, или нет?
Необходима формула с пояснением, где что.
Благодарю.

Comments

[Денис Загаевский]

Решил всё делать через canvas(а как же иначе).

о_О

Answer 1

[Кирилл]

Просто ищите пересекающиеся стороны у треугольников.

Answer 2

[Rsa97]

Варианты: не пересекаются, касаются снаружи, пересекаются, один касается другого изнутри, один полностью вложен во второй.

Пересекаются - какая-либо сторона одного треугольника пересекается с какой-нибудь стороной второго и стороны не параллельны, для каждой стороны первого треугольника проверяем каждую сторону второго.

Один полностью внутри другого - все вершины треугольника A расположены по одну сторону от сторон второго треугольника B, обходимого по контуру, то есть от отрезков B₁B₂, B₂B₃, B₃B₁.

Касание - вершина одного из треугольников лежит на стороне другого треугольника или сторона одного треугольника параллельна стороне второго и пересекается с ней.

Comments

[Umid]

"Один полностью внутри другого - все вершины треугольника A расположены по одну сторону от сторон второго треугольника B, обходимого по контуру, то есть от отрезков B1B2, B2B3, B3B1."
Про это ничего не понял.
Где можно об этом почитать на доступном языке?
Что бы вы понимали мои знания по математике:
Алгебра-прохожу Прогрессии (уравнения, неравенства и т.д. уже позади).
Геометрия - заканчиваю стериометрию, сейчас на векторах.

[Rsa97]

Umid: Ок.
Отрезки AB и CD на плоскости пересекаются если пересекаются их проекции на оси X и Y, точки A и B лежат по разные стороны от отрезка CD, точки C и D лежат по разные стороны от отрезка AB.

Проверка пересечения проекций: min(x_A, x_B) <= max(x_C, x_D) && min(x_C, x_D) <= max(x_A, x_B). Аналогично для оси Y.

Точка С лежит слева от отрезка AB если векторное произведение AB*AC > 0, справа от отрезка если AB*AC < 0, на отрезке (или его продолжении) если AB*AC = 0.
AB*AC = (x_B-x_A)*(y_C-y_A)-(y_B-y_A)*(x_C-x_A)

[Umid]

Первый абзац вроде бы понял.
На втором застрял. Откуда проекции?
А последний абзац совсем не понял.

[Rsa97]

Umid: Нарисуйте отрезок AB в системе координат OXY. Теперь из концов отрезка проведите вертикальные линии до пересечения с осью OX. Две получившиеся точки на оси дают новый отрезок, который является проекцией AB на ось OX. Аналогично, горизонтальные линии дадут проекцию на ось OY.

Теперь нарисуйте отрезок AB, поставьте рядом с ним точку C. Дорисуйте ещё один отрезок AC. Направление угла поворота от AB к AC можно найти через знак векторного произведения AB*AC, формулу я привёл выше. Точка C лежит слева от отрезка AB, если поворачивать надо влево, а векторное произведение больше нуля.

[Umid]

" Направление угла поворота от AB к AC можно найти через знак векторного произведения AB*AC, формулу я привёл выше. "

Здесь вы имеете ввиду найти угол между двумя векторами AB и AC?

"Точка C лежит слева от отрезка AB, если поворачивать надо влево, а векторное произведение больше нуля."

Не понял это предложение, и зачем нам знать слева ли лежит точка C?

[Rsa97]

Umid: Не сам угол, а только его направление. Знать надо, чтобы определить, что точки C и D (концы отрезка CD) лежат по разные стороны от отрезка AB. В этом случае знаки векторных произведений AB*AC и AB*AD будут разными, одна величина будет положительная, другая отрицательная. Для простоты проверки можно два полученных значения перемножить, если произведение отрицательное - то знаки были разные, если положительное - то одинаковые.

Answer 3

[Vitaliy Orlov]

забей на треугольники, проверь пересекаются ли прямые (из которых состоят треугольники). Если хотя бы одна прямая имеет пересечение, значит и фигуры пересекаются

Comments

[lvv85]

Не прямые а отрезки (из которых состоят треугольники)
"Алгоритмы. Построение и анализ" Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн
33.2 Определение наличия пересекающихся отрезков

Answer 4

[evgeniy_lm]

Проверь пресечение сторон треугольника. Нужно найти точки пересечения прямых проходящих через стороны и убедится что эти точки лежат на сторонах треугольника

Answer 5

[x67]

1. Получаете уравнения прямой для каждой из сторон каждого треугольника (y=kx+b и cоответствующее уравнение x=(y-b)/k)
обоснование решения: аксиома 1. При пересечении фигур, хотя бы одна вершина одной из фигур будет лежать на другой фигуре.
Далее при чтении см. Рисунок
2. Поочередно подставляете каждую координату каждой из вершин в получившиеся уравнения, красной линией показана геометрическая интерпретация подстановки X синей точки(предполагаемой вершины треугольника). При этом мы подставляем Х синей точки только в уравнения тех линий, у которых этот Х тоже присутствует. Геом. интерпретация - коричневые линии. То есть Х синей точки вне диапазона правой серой линии по Х, потому мы эту линию не проверяем.
Когда будем подставлять У, мы не будем проверять нижнюю линию по этой же причине.
Чтобы вершина, находилась внутри треугольника, вторая координата синей точки должна быть внутри интервала, полученного из уравнений (геом. интерпретация - зеленые линии - тот самый интервал, внутри которого должен быть Y синей точки).
Таким образом, если хоть одна из вершин проходит проверку и по Х и по У, она находится внутри или на поверхности другого треугольника и треугольники пересекаются.


Если не совсем понятно, спрашивайте. А вообще лучше бы вам найти готовый велосипед и не парить себе мозги.

Comments

[Umid]

Совсем не понял. Велосипед не могу себе позволить. Задача на городской олимпиаде по информатике встретилась. Скоро будет битва за выход на республиканскую олимпиаду. Хочу подготовиться как следует.

Как получить уравнение прямой?
С остальным тоже не понял.
Если можно, было бы неплохо 1 пример разобрать, если вам не составит труда.

[x67]

Umid: Уравнение прямой получаете по двум точкам - вершинам треугольника. Уравнение вида y=kx+b вполне подойдет.
Уравнений должно быть 6, так как всего 6 отрезков. Теперь предположим у нас есть вершина А(x;y) треугольника АBC и отрезки DE,EF,FD треугольника DEF, также заданные координатами, а также уравнения их прямых.
1. Проверка по X:
DEx1=

[Umid]

Из уравнения y=kx+b , что означает k и b?
На сколько я могу догадаться, k и x некие постоянные, которые генерируются в самом начале. Далее генерируем значение x и подставляем в уравнение, находим y.
А вот дальше не понял.
Или же может у нас уже есть значения x и y, и мы узнаём значения k и b?

[x67]

Umid: да, это постоянные коэффициенты. вывести их можно из системы уравнений прямой, имея хотя бы две точки https://znanija.com/task/661788 . В школе должны были это проходить.
А ты программировать умеешь? Предлагаю делать все последовательно. Напиши класс треугольника, у которого будут три точки, заданные координатами х и у, хранящимися желательно в виде двумерного массива. Потом напиши метод, у которого на входе будет индекс линии(1 - 3) и координата х, а выдавать он должен у по уравнению этой линии.