Урок із серії «Геометричні алгоритми»
Привіт, дорогий читачу. Напишемо ще три нові функції.
Функція LinesCross () буде визначати, чи перетинаються два відрізка. У ній взаємне розташування відрізків визначається за допомогою векторних творів. Для обчислення векторних творів напишемо функцію - VektorMulti ().
Функція RealLess () буде використовуватися для реалізації операції порівняння "<” (строго меньше) для вещественных чисел.
Задача1. Два відрізка задані своїми координатами. Скласти програму, яка визначає, чи перетинаються ці відрізки. не знаходячи точку перетину.
Рішення
Нехай дано два відрізки. Перший заданий точками. Другий заданий точками.
Взаємне розташування відрізків можна перевірити за допомогою векторних творів:
Розглянемо відрізок і точки і.
Точка розташована праворуч від прямої, для неї векторний добуток <0, так как векторы отрицательно ориентированы.
Для того щоб точки і, лежали по різні боки від прямої, досить, щоб виконувалася умова <0 ( векторные произведения имели противоположные знаки).
Аналогічні міркування можна провести для відрізка і точок і.
Отже, якщо, то відрізки перетинаються.
Для перевірки цієї умови використовується функцію LinesCross (), а для обчислення векторних творів - функція VektorMulti ().
Векторний добуток двох векторів обчислюється за формулою:
ax, ay - координати першого вектора,
bx, by - координати другого вектора.
Результати виконання програми:
Введіть координати відрізків: -1 1 2 2.52 2 1 -1 3
Так.
Ми написали програму, що визначає, чи перетинаються відрізки, задані своїми координатами.
На наступному уроці ми складемо алгоритм, за допомогою якого можна буде визначити, чи лежить точка всередині трикутника.
Шановний читач. Ви вже познайомилися з кількома уроками з серії «Геометричні алгоритми». Чи всі доступно написано? Я буду Вам дуже вдячна, якщо Ви залишите відгук про ці уроках. Можливо, щось потрібно ще доопрацювати.
З повагою, Віра Господарець.