Всем доброго времени суток. Давно я тут не появлялся
Сразу хочу извиниться:
- вопрос скорее относится к алгоритмам и математике, чем к программированию (т.е. за то, что не на тот форум)
- вопрос довольно примитивный(по форуму бегло поискал не нашел)
Итак, сам вопрос: Как определить пересекаются ли 2 отрезка. Но прежде чем меня закидают помидорами, отмечу: я уже решал эту задачу и меня интересует нахождение
наиболее эффективного решения.
Сейчас у меня есть только одна мысль по этому поводу:
Возьмем 2 отрезка a и b.
Проверяем лежат ли концы отрезка b в разных полуплоскостях, которые - результат деления плоскости прямой, содержащей отрезок a. (не знаю, как написать это более адекватно)
И наоборот.
Если оба условия выполнены - то отрезки пересекаются.
Что бы проверить лежат ли отрезки в разных полуплоскостях я составлял уравнение прямой и проделывал некоторые другие несложные манипуляции.
Если я ошибся и таким образом нельзя определить пересечение отрезков - просьба сообщить мне об этом.
Собственно вопрос заключается в следующем :
Какие есть еще способы определения пересечения отрезков? Хотелось бы увидеть менее ресурсоемкие (содержащие меньшее количиство операций) способы. Код необязателен, т.к. все равно будет переписан с нуля. Мне нужен принцип\алгоритм.