Как проверить, пересекаются ли треугольники?
Моё почтение. Задача: Сгенерировать 2 рандомных треугольника в системе координат, и проверить, пересекаются ли они.
Решил всё делать через canvas(а как же иначе). Сгенерировать 2 раза по 3 отрезка (по координатам точек), проверить, что треугольник может получиться из них. Затем соединить все три отрезка, что бы получились треугольники.
Интересует, как именно можно проверить пересекаются ли они, или нет? Необходима формула с пояснением, где что. Благодарю.
- Вопрос задан более трёх лет назад
- 2406 просмотров
Оценить 1 комментарий
- Вконтакте
- Вконтакте
Варианты: не пересекаются, касаются снаружи, пересекаются, один касается другого изнутри, один полностью вложен во второй.
Пересекаются - какая-либо сторона одного треугольника пересекается с какой-нибудь стороной второго и стороны не параллельны, для каждой стороны первого треугольника проверяем каждую сторону второго.
Один полностью внутри другого - все вершины треугольника A расположены по одну сторону от сторон второго треугольника B, обходимого по контуру, то есть от отрезков B1B2, B2B3, B3B1.
Касание - вершина одного из треугольников лежит на стороне другого треугольника или сторона одного треугольника параллельна стороне второго и пересекается с ней.
- Вконтакте
Umid: Ок. Отрезки AB и CD на плоскости пересекаются если пересекаются их проекции на оси X и Y, точки A и B лежат по разные стороны от отрезка CD, точки C и D лежат по разные стороны от отрезка AB.
Точка С лежит слева от отрезка AB если векторное произведение AB*AC > 0, справа от отрезка если AB*AC < 0, на отрезке (или его продолжении) если AB*AC = 0. AB*AC = (xB-xA)*(yC-yA)-(yB-yA)*(xC-xA)
Umid: Нарисуйте отрезок AB в системе координат OXY. Теперь из концов отрезка проведите вертикальные линии до пересечения с осью OX. Две получившиеся точки на оси дают новый отрезок, который является проекцией AB на ось OX. Аналогично, горизонтальные линии дадут проекцию на ось OY.
Теперь нарисуйте отрезок AB, поставьте рядом с ним точку C. Дорисуйте ещё один отрезок AC. Направление угла поворота от AB к AC можно найти через знак векторного произведения AB*AC, формулу я привёл выше. Точка C лежит слева от отрезка AB, если поворачивать надо влево, а векторное произведение больше нуля.
" Направление угла поворота от AB к AC можно найти через знак векторного произведения AB*AC, формулу я привёл выше. "
Здесь вы имеете ввиду найти угол между двумя векторами AB и AC?
"Точка C лежит слева от отрезка AB, если поворачивать надо влево, а векторное произведение больше нуля."
Не понял это предложение, и зачем нам знать слева ли лежит точка C?
- Вконтакте
- Вконтакте
1. Получаете уравнения прямой для каждой из сторон каждого треугольника (y=kx+b и cоответствующее уравнение x=(y-b)/k) обоснование решения: аксиома 1. При пересечении фигур, хотя бы одна вершина одной из фигур будет лежать на другой фигуре. Далее при чтении см. Рисунок 2. Поочередно подставляете каждую координату каждой из вершин в получившиеся уравнения, красной линией показана геометрическая интерпретация подстановки X синей точки(предполагаемой вершины треугольника). При этом мы подставляем Х синей точки только в уравнения тех линий, у которых этот Х тоже присутствует. Геом. интерпретация - коричневые линии. То есть Х синей точки вне диапазона правой серой линии по Х, потому мы эту линию не проверяем. Когда будем подставлять У, мы не будем проверять нижнюю линию по этой же причине.Чтобы вершина, находилась внутри треугольника, вторая координата синей точки должна быть внутри интервала, полученного из уравнений (геом. интерпретация - зеленые линии - тот самый интервал, внутри которого должен быть Y синей точки). Таким образом, если хоть одна из вершин проходит проверку и по Х и по У, она находится внутри или на поверхности другого треугольника и треугольники пересекаются.
Если не совсем понятно, спрашивайте. А вообще лучше бы вам найти готовый велосипед и не парить себе мозги.
- Вконтакте
Совсем не понял. Велосипед не могу себе позволить. Задача на городской олимпиаде по информатике встретилась. Скоро будет битва за выход на республиканскую олимпиаду. Хочу подготовиться как следует.
Как получить уравнение прямой? С остальным тоже не понял. Если можно, было бы неплохо 1 пример разобрать, если вам не составит труда.