Python
Алгоритм пересечения полигонов в 2D.
Есть два полигона у каждого по четыре вершины, углы между рёбрами прямые (квадраты, прямоугольники), нужен алгоритм пересечения.
ПРИНОШУ ВСЕМ (И АВТОРУ ВОПРОСА) ГЛУБОЧАЙШИЕ ИЗВИНЕНИЯ!!!
Я давно начал писать ответ, но неожиданно затупил. (((?
К сожалению, до сих пор туплю, продолжение не получается.
ВОТ ТО, ЧТО УСПЕЛ ОБМОЗГОВАТЬ ↓↓↓
✓ В первую очередь требуются входные данные. Учтём следующее:
• Фигуры могут располагаться на плоскости произвольно.
• Каждая фигура имеет произвольные размеры (габариты).
• Любая фигура может быть ориентирована произвольно.
Именно это и будет входными данными.
I. Расположение фигуры задаётся координатами одной из вершин (2 числа).
II. Габариты прямоугольника — длина + ширина (2 числа).
III. Ориентация — угол поворота (одно число).
ИТОГО: 5 чисел.
*Другой способ задания прямоугольника — по координатам диагонали (4 числа) и ориентации (1 число).
✓ Задача о пересечении n-угольников сводится к задаче о пересечении отрезков.
ПЕРВАЯ ПОДЗАДАЧА.
Важное утверждение: НА ПЛОСКОСТИ НЕ ПЕРЕСЕКАЮТСЯ ТОЛЬКО ПАРАЛЛЕЛЬНЫЕ (и совпадающие) ПРЯМЫЕ .
Коэффициенты наклона параллельных прямых равны.
Коэффициент наклона отрезка прямой равен отношению проекций: К = Δy/Δx.
Допустим, концы первого отрезка: (a,b) и (c,d), концы второго отрезка: (e,f) и (g,h). Тогда для первого отрезка К1 = (d–b)/(c–a), для второго отрезка К2 = (h–f)/(g–e). Если К1 = К2, то отрезки либо параллельны, либо лежат на одной прямой. В противном случае подозрение на пересечение установлено.
Если подозрение опровергнуто, то переходим к следующей паре отрезков и решаем первую подзадачу для них.
ВТОРАЯ ПОДЗАДАЧА.
Обозначим предполагаемую точку пересечения как (xx,yy). От каждого отрезка возьмем по одной точке, например (a,b) и (e,f). Тогда:
К1 = (yy–b)/(xx–a)
К2 = (yy–f)/(xx–e)
Решаем систему относительно неизвестных xx и yy.
К1xx–K1a+b = K2xx–K2e+f => xx = (K1a–K2e+f–b)/(K1–K2). В правой части всё — константы. yy находится подстановкой xx.
Проверяем, принадлежит ли точка (xx,yy) отрезкам. Если точка (xx,yy) находится за пределами хотя бы одного из отрезков, то отрезки НЕ ПЕРЕСЕКАЮТСЯ, иначе пересечение отрезков доказано.
✓ Пересечение фигур можно считать доказанным, если установлено пересечение хотя бы двух сторон, принадлежащих разным фигурам.
• • •
Увы! ((((((
Голова как „с бодуна”. Хотя я вообще не „закладываю”.
Я давно начал писать ответ, но неожиданно затупил. (((?
К сожалению, до сих пор туплю, продолжение не получается.
ВОТ ТО, ЧТО УСПЕЛ ОБМОЗГОВАТЬ ↓↓↓
✓ В первую очередь требуются входные данные. Учтём следующее:
• Фигуры могут располагаться на плоскости произвольно.
• Каждая фигура имеет произвольные размеры (габариты).
• Любая фигура может быть ориентирована произвольно.
Именно это и будет входными данными.
I. Расположение фигуры задаётся координатами одной из вершин (2 числа).
II. Габариты прямоугольника — длина + ширина (2 числа).
III. Ориентация — угол поворота (одно число).
ИТОГО: 5 чисел.
*Другой способ задания прямоугольника — по координатам диагонали (4 числа) и ориентации (1 число).
✓ Задача о пересечении n-угольников сводится к задаче о пересечении отрезков.
ПЕРВАЯ ПОДЗАДАЧА.
Важное утверждение: НА ПЛОСКОСТИ НЕ ПЕРЕСЕКАЮТСЯ ТОЛЬКО ПАРАЛЛЕЛЬНЫЕ (и совпадающие) ПРЯМЫЕ .
Коэффициенты наклона параллельных прямых равны.
Коэффициент наклона отрезка прямой равен отношению проекций: К = Δy/Δx.
Допустим, концы первого отрезка: (a,b) и (c,d), концы второго отрезка: (e,f) и (g,h). Тогда для первого отрезка К1 = (d–b)/(c–a), для второго отрезка К2 = (h–f)/(g–e). Если К1 = К2, то отрезки либо параллельны, либо лежат на одной прямой. В противном случае подозрение на пересечение установлено.
Если подозрение опровергнуто, то переходим к следующей паре отрезков и решаем первую подзадачу для них.
ВТОРАЯ ПОДЗАДАЧА.
Обозначим предполагаемую точку пересечения как (xx,yy). От каждого отрезка возьмем по одной точке, например (a,b) и (e,f). Тогда:
К1 = (yy–b)/(xx–a)
К2 = (yy–f)/(xx–e)
Решаем систему относительно неизвестных xx и yy.
К1xx–K1a+b = K2xx–K2e+f => xx = (K1a–K2e+f–b)/(K1–K2). В правой части всё — константы. yy находится подстановкой xx.
Проверяем, принадлежит ли точка (xx,yy) отрезкам. Если точка (xx,yy) находится за пределами хотя бы одного из отрезков, то отрезки НЕ ПЕРЕСЕКАЮТСЯ, иначе пересечение отрезков доказано.
✓ Пересечение фигур можно считать доказанным, если установлено пересечение хотя бы двух сторон, принадлежащих разным фигурам.
• • •
Увы! ((((((
Голова как „с бодуна”. Хотя я вообще не „закладываю”.
Похожие вопросы
- Алгоритмы на Питоне? Не смешите, даже самый отстойный алгоритм на C++ будет быстрее работать более экономного на Питоне.
- Выяснить, сколько точек пересечения имеют прямая
- Алгоритмы и структуры данных. Нужно ли все понимать? Просто там такие математические действия.
- Бинарный поиск. Алгоритм.
- Алгоритмическая задача. Ускорить алгоритм
- Помогите разобрать "прочитать" код. Объяснить алгоритм, как от работает
- Торговля акциями. Линейные алгоритмы. Python.
- Есть способ без ста грамм разобраться в этом алгоритме?
- Заданы 2 нат. числа a и b - границы диапазона. Используя алгоритм решета Эратосфена, вывести все простые числа на [a, b]
- Не понимаю как выявить у кода (алгоритма ) сложность кто поможет с решением и объяснит как получил (выявил) Python
Если что, длина отрезка определяется как КОРЕНЬ ИЗ СУММЫ КВАДРАТОВ ПРОЕКЦИЙ ОТРЕЗКА НА О́СИ. |АВ| = √((Δx)²+(Δy)²+(Δz)²), где любая «дельта» — это разность соответствующих координат концов отрезка.
Судя из правой картинки, тут пересечением считается не только когда стороны пересекаются, но и когда, одна из фигур лежит внутри другой. То есть не только взаимодействие периметров, но и площадей.