Дано: у нас є трикутник, нам відомі тільки координати його вершин. У нас є точка, нам відомі її координати.
Що потрібно дізнатися: потрібно встановити приналежність точки трикутнику.
У даній статті розбирається кілька різних методів визначення приналежності точки трикутнику.
В даному методі спочатку знаходяться площі 3-х трикутників, які утворює дана точка з кожною стороною трикутника. У нашому випадку (рис. 1) це трикутники ABP, BCP, CAP і їх площі s1, s2, s3 відповідно.
Потім знаходиться площа самого трикутника ABC.
Знайдений площі порівнюються - якщо сума 3-х площ дорівнює площі всього трикутника, то значить точка належить трикутнику. При порівнянні, як правило, задається похибка.
Так як у нас відомі лише координати точок, то все площі, знаходяться за формулою Герона. від рясності операцій якої стає ясно, чому цей метод дуже трудомісткий.
Найпростіша реалізація алгоритму:
Все відносно!
Так ось, в разі малюнка 3 точка повинна лежати по ліву сторону векторів, щоб належати трикутнику.
Третій метод який я висвітлюю для мене найцікавіший.
Ідея його застосування зароджується якщо поглянути на трикутник як на половинку паралелограма ...
Даний метод я спочатку перевірив на папері. Після всіх оптимізацій формул, як все зійшлося, я реалізував його в коді, де він показав себе цілком успішним і результативним. Аж ефективніше 2-х попередніх методів:]
1) одну вершину трикутника поміщаємо в координати (0; 0);
2) дві сторони, що виходять з цієї вершини, представляємо як вектора.
Таким чином з усього цього з'являється система простих умов перебування точки P між векторами b і c. (Рис. 4)
За кодом можна побачити, що знаходяться нові координати точок B і C, які одночасно є векторами b і c (рис. 4.). А нові координати точки P є вектором (Px, Py). Далі йде формула, яку я попередньо звів до загального вигляду і спростив.
Кількість основних операцій виходить 13 (+4). Зовсім не погано:]
Це досить відомий метод, особливо коли визначається приналежність точки багатокутників. Часто даний метод називають «трасування променя», хоча це не зовсім правильно, тому що трасування променя - це розрахунок ходу світлових променів в 3D сцені.
Суть в тому, що з цієї точки пускається промінь з якої-небудь осі в будь-якому напрямку.
Потім перевіряються перетину зі сторонами багатокутника і ведеться підрахунок перетинів.
Таким чином якщо кількість перетинів парне, то значить точка лежить поза багатокутника, якщо ж кількість непарні, то значить точка лежить всередині.
На малюнку 5 зображено дві піддослідні точки P і K, у променя з точки P одне перетин зі сторонами трикутника, таким чином точка P належить фігурі, а точці K не пощастило - у неї два перетину.
Начебто нормально спростив (для трикутника маю на увазі), але щось мені здається, що може бути і по крутіше ...
А так, виходить приблизно 30 операцій.
Ну ось ми і підійшли до найцікавішого! Хто швидше і сильніше. ]
Я провів тест з наступними параметрами (хоча все залежить від процесора):
- кол-во повторень алгоритму за 1 імітацію = 4 мільйони.
- кол-во імітацій для кожного алгоритму = 1000.
Ну що сказати, векторний метод хороший)
З ним звичайно змагається другий спосіб відносності точки, але головна відмінність в тому, що для отн. точки необхідна сувора орієнтація сторін трикутника, а для векторного це не важливо, тому він крутіше)