b> - P 1 ), ( p 2 - p 1 )] Г— [( p 4 - p 1 ), ( p 2 - P 1 )] ВЈ 0;
в) [( p 1 - P 3 ), ( p 4 - p 4 )] Г— [( p 2 - p 3 ), ( p 4 - P 3 )] ВЈ 0. br/>
Останні два умови означають, що кінці одного відрізка лежать по різні сторони від прямої, якій належить інший відрізок. Перше ж умова виключає зі спеціального розгляду випадок рівності нулю всіх чотирьох косих творів, при якому відрізки лежать на одній прямій і можуть як перетинатися, так і немає.
Площа трикутника (Задача 6.3) дорівнює половині модуля косого добутку двох векторів, утворених якими двома його сторонами.
Тоді відстань від точки C до прямої, заданої координатами точок A і B (задача 4.2), можна підрахувати як відношення модуля косого добутку векторів CA і CB до довжини відрізка AB (дана формула випливає з двох способів обчислення площі трикутника).
Площа довільного багатокутника з вершинами p 0 , p 1 , ..., p n -1 , перерахованими в порядку його обходу проти годинникової стрілки, (задача 6.4) можна обчислити як суму орієнтованих площ трикутників, утворених векторами p i і p i +1 , i = 0, ..., n - 1; i + 1 обчислюється за модулем n . p> Випуклість багатокутника (задача 6.2) з вершинами p 0 , p 1 , ..., P n -1 , перерахованими в порядку його обходу, легко перевірити за допомогою порівняння знаків косого твори пар векторів ( p i +1 - P i ) і ( p i +2 - p i +1 ), i = 0, ..., n - 1; i + 1 і i + 2 обчислюються за модулю n . У разі опуклого багатокутника знаки у всіх зазначених творів збігаються (якщо ми знаємо напрямок обходу, то знак косих творів для опуклого багатокутника визначений: при обході за годинниковою стрілкою твори негативні, а проти годинникової стрілки - позитивні).
На цьому способи корисного застосування косого твори аж ніяк не вичерпані.
Опукла оболонка множини N точок площини
Задача полягає в тому, щоб перерахувати всі точки, що належать кордоні опуклою оболонки заданої множини точок, в порядку її обходу, наприклад, проти годинникової стрілки (у деяких завданнях потрібно перерахувати тільки кутові точки). Для ефективного вирішення цього завдання існує кілька різних алгоритмів (див. [1] - [4]). Наведемо найбільш просту реалізацію одного з них - алгоритму Джарвіса.
{ наступний абзац проілюструвати малюнком з номера 16/2000, стор 11 }
Перерахування точок шуканої кордону опуклого багатокутника почнемо з правої нижньої точки, яка завідомо належить кордоні опуклої оболонки. Позначимо її координати ( X 0 , y 0 ). Наступною, при зазначеному порядку обходу, буде точка ( x 1 , y 1 ), для якої кут між віссю OX і вектором ( x 0 , y 0 ) - ( x 1 , y 1 ) мінімальний. Якщо таких точок декілька, то кутовий в многоугольнике стане точка, для якої довжина вектора ( x 0 , y 0 ) - ( x 1 , y 1 ) максимальна, а наступної точкою, що належить опуклою оболонці - та, довжина вектора у якої мінімальна (таким чином наш вибір буде залежати від конкретної постановки задачі). Для знаходження наступної точки значення кутів між векторами обчислювати необов'язково. Ми знову можемо скористатися поняттям знака векторного твори. Нехай, далі, ми вже знайшли i -у вершину опуклої оболонки ( x i , y i ). Тоді, ( i + 1)-а точка є така точка, ще не увійшла в опуклу оболонку, для якої кут між вектором ( x i -1 , y i -1 ) - ( x i , y < sub> i ) і вектором ( x i , y i ) - ( x i +1 , y i +1 ) мінімальний, при мінімальній довжині вектора ( x i , y i ) - ( x i +1 , y < sub> i +1 ) серед усіх векторів з таким кутом. Зауважимо, що для всіх інших точок ( x , y ), вектор ( x i ...
