Доброго времени суток, читатели, зрители моего канала programmer's notes. Не забывайте подписываться и писать свои комментарии к моим статьям и видео.
Алгоритмы определения принадлежности точки отрезку и определения того, пересекаются ли отрезки на плокости на python
С отрезком дело сложнее чем с прямой линией, поскольку мы должны как-то учитывать ограниченность его длины.
В начале рассмотрим алгоритм определения того, что точка находится на отрезке (рисунок 1 фрагмент a)). Существуют разные подходы определить это, я рассмотрю самый, как мне кажется, простой алгоритм. Он основан на очевидно факте: если точка лежит на отрезке тот сумма расстояний от нее до концов отрезка равна длине отрезка. Что если есть две точки A(x1, y1) и B(x2, y2), то расстояние между ними вычисляется по известной формуле sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)).
Программа определения того, принадлежит точка отрезку или нет, представлена на рисунке 2. На этот раз (см. замечание из предыдущей статьи) мы проверяем не равенство, а близость значений: abs(d1 + d2 - dd) <= d, поскольку речь идёт о вещественных числах, полученных в результате вычисления.
Перейдём теперь ко второй задаче, пересечению отрезков. Чтобы излишне не раздувать текст программы отбросим случаи когда один или оба отрезка вырождаются в точки. На рисунке 1 представлены все случаи взаимного расположения отрезков: b) пересекаются, c) и d) не пересекаются, e) частично наложение отрезков, f) один отрезок внутри другого.
Алгоритм, который я хотел бы здесь представить, в общих чертах выглядит следующим образом. Определяем прямые, на которых лежат наши отрезки. Если отрезки пересекаются, то пересекаются и прямые. Обратное в общем случае не верно. Следовательно, во первых, определяем точку пересечения прямых (см. предыдущую статью), а потом определяем, принадлежит ли эта точка обоим отрезкам. Но есть ещё два варианта: прямые параллельны и прямые совпадают. Если прямые параллельны, то отрезки, очевидно, не пересекаются. А вот если прямые совпадают то отрезки могут налагаться друг на друга (см. рисунок 1 фрагменты e) и f)). Вот все эти варианты и должна проверить наша программа.
Уравнение прямой, соответствующее формату: ax+by = c для отрезка с концами (x1, y1) и (x2, y2) будет
(y1-y2)*x + (x2-x1)*y = x2*y1-x1*y2
т.е.
a = (y1-y2), b=(x2-x1), c=x2*y1-x1*y2
Надо учесть ещё два частных случая:
1. Если x1=x2, то a=1, b=0, c=x1
2. Если y1=y2, то a=0, b=1, c=y1
они соответствуют отрезкам, которые параллельны осям координат.
Функция inseg() (рисунок 3) проверяет принадлежит точка отрезку или нет. Переменная d определяет точность. Если разность значений меньше этой величины, считаем, что эти значения равны. Функция ln() определяет длину отрезка по его координатам.
- В начале определяем уравнения прямых, которым принадлежат данные отрезки (рисунок 4), т.е. коэффициенты a1, b1, c1, a2, b2, c2.
- Поскольку координаты точек мы вводим вручную, а не получаем в результате вычисления, то и сравнение их производится обычным способом: x1 != x2 and y1 != y2 и т.п.
- Если прямые пересекаются, то определяем принадлежит ли точка пересечения обоим отрезкам.
- Если прямые не пересекаются, то не пересекаются и отрезки.
- Но если прямые совпадают abs(dd) <= d and abs(dx) <= d and abs(dy) <= d, то здесь придётся проверять два вариант: отрезки частично перекрываются и один отрезок находится внутри другого. Также мы учитываем варианты, какой из отрезков длиннее.
Например 1
0 1 1 0
0 0 0.5 0.5
Результат
Пересекаются
1 1 5 5
2 2 6 6
Результат
Частичное перекрытие
Замечание
Кстати из текста программы видно, что мы находим и точку пересечения, просто не выводим её координаты.
Пока всё!
Пишите свои предложения и замечания, и занимайтесь программированием, а также проектированием баз данных, хотя бы для поддержания уровня интеллекта.
