Материал: 252_337
|
|
Лхл |
y2) |
|
|
|
(x;ja' /' |
^< ( |
\ |
(*» yt) '(XjY) |
(x';Y) |
Хх^у~^\У\7(Xі; Y) |
||
(Xv'yJ (x4;yj |
|
(x6;ya) (x4;j/4) |
|
|
(0;0) |
x |
(0; 0) |
|
|
; Уі) (x6; VbhsA**! У*)
(*i; yd
(X';Y)
(X;Y) (х6;ув) (*»Уд
(0;0)
в)
Мал. 150
таким чином: перетинає вершину (хх; ух), повністю проходить стороною з вершинами (хх; г/х) і (х7; у7), дотикається до верши ни (х5; у5), перетинає вершину (х3; г/3). Як визначено вище, оз накою розміщення точки (X; Y) поза межами багатокутника є парна кількість зафіксованих перетинів його сторін. Як про аналізувати цю ситуацію у даному випадку? Пропонується та кий хід міркувань. Прохід побудованого відрізка через верши ну (хх; г/х) характеризує перетин зразу двох сторін багатокутни ка з вершинами (хх; ух), (х2; у2) і {хх; ух), (х7; у7). Фіксуємо по точний стан кількості перетинів 1. Оскільки сторона багатокут ника (хгі ух), (х7; у7) вже врахована, навіть якщо, як у нашому випадку, по ній проходить побудований відрізок, то переходи мо до наступної критичної точки. Нею є вершина (х5; у5). Але в ній не відбувається явного перетину сторін, а лише дотик до вершини багатокутника. Оскільки нас цікавить перетин, тому логічно цей факт не враховувати. У вершині (х3; у3), як і на ма люнку 150, а, відбувається перетин двох сторін у їх спільній вершині, тому необхідно врахувати цей перетин, збільшивши їх загальну кількість на 1. Таким чином, підраховано 2 явних перетини сторін заданого багатокутника і можна зробити вис новок, що точка (X; Y) лежить поза його межами.
Розглянемо малюнок 150, в. Побудований відрізок двічі до тикається до вершин (х6; г/6), (х4; у4). Але оскільки дотики не враховуються, то кількість перетинів становитиме 0, а це озна чає, що точка (X; У) лежить зовні заданого багатокутника.
262
Можна зробити попередній підсумок:
-якщо відрізок з кінцями у точках (X; У), (х'; У) перетинає сторону багатокутника не у вершинах, що їй належать, то не обхідно враховувати один перетин;
-якщо відрізок з кінцями у точках (X; У), (х'; У) перетинає дві суміжні сторони багатокутника у їх спільній вершині, то необхідно враховувати один перетин;
-якщо відрізок з кінцями у точках (X; У), (х'; У) дотикаєть ся до спільної вершини двох суміжних сторін багатокутника, то перетин не враховується.
Цікавим є випадок, коли задана точка (X; У) збігається з вер шиною багатокутника (мал. 150, г). У такому випадку подаль ший перегляд сторін багатокутника беззмістовний, його можна припинити і дати позитивну відповідь щодо належності точки (X; У) заданому багатокутнику.
Перейдемо до формулювання алгоритму визначення поло ження точки (X; У) відносно заданого багатокутника. Але попе редньо введемо деякі домовленості щодо запису умов перетину відрізків. Для побудованого відрізка з кінцями у точках (X; У), (х'; у) завжди дивитимемося із додатково побудованої точки (х'; У) у задану точку (X; У). Розглядаючи сторони багатокут
ника з кінцями у вершинах (х;; у.), (xt + 1; уі + j), дивитимемося із вершини (хг; yt) у вершину (х; + 1; у1 + г ). Для спрощення запи су виразів точки позначатимемо так: р, р', pv р2, • ••,рп-
Попередньо перераховано досить багато різних умов, які дають змогу дослідити цей факт. Спробуємо визначити їх пріоритетність, що дасть змогу скоротити кількість виконува них перевірок. Розглянемо деякий поточний крок, на якому досліджується можливий перетин відрізка з кінцями у точках р' ір та сторони багатокутника з вершинами у точках pt тарі + 1.
1. Оскільки відсоток сторін, з якими відбувається перетин побудованого відрізка, найчастіше значно менший, ніж тих, з якими такого перетину немає, то на першому місці повинно бу ти визначення можливості перетину. Таку інформацію дає пе ревірка умови перетину обмежуючих прямокутників зі сторо нами, паралельними осям координат, для досліджуваних відрізків. Для побудованого нами відрізка з кінцями у точках р' ір, що паралельний осі Ох, таким обмежувальним прямокут ником буде сам цей відрізок, а для сторони багатокутника з вершинами у точках pt т&рі + 1 лівою нижньою вершиною буде точка з координатами (х/; у/), правою верхньою - (х'і + 1; у'і + 1)-
На малюнку 151, а зображено випадок, коли одна зі сторін багатокутника ptpi +1 явно перетинає відрізок з кінцями у точках р' і р. Інший випадок, зображений на малюнку 151, б, є сумнівним щодо їх перетину: перетин обмежуючого прямокутника сторони рірі + j і відрізкадо' існує, однак перетину самих відрізків немає.
263
(х,і у) |
(x'i+1; y'i+1) |
(ХГ>УІ) |
« » 5 УІ+і) |
|||
|
|
|
|
\№Л |
|
(x1; Y) |
(*.';»,') |
|
(x';Y) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(xi+1; yi+l) |
(x[; y[) |
'•"-i+i! У1+1) |
||||
a) |
|
|
6) |
|
|
|
|
|
Мал. 151 |
|
|
|
|
Для запису умови можливого перетину відрізків з кінцями у точках р', р і pt, рі+1 необхідно врахувати такі дві обставини: відрізок з кінцями у точках р', р паралельний осі Ох; значення х' за побудовою більше від значення абсцис будь-яких вершин багатокутника. Отже, з урахуванням зазначених особливостей умова наявності можливого перетину виглядатиме так:
(х'і+і > = х ) a n d (У > = УD a n d (У'і+і >= У)-
2. На другому кроці у разі підозри на перетин поточної сто рони і побудованого відрізка необхідно перевірити одночасне виконання умов:
[(р -р') х (р. -р')\ • [(р-р') х (р1+1 -р')] < 0; [(Рі+і -Pt) х W -РіУ\ • {(Ріп ~РІ)Х(Р ~Рі)] < о.
За наявності їх виконання можна зробити висновок, що досліджувані відрізки перетинаються у точці, яка не збігається
зїх кінцями.
3.До третього кроку переходимо для перевірки можливого проходу побудованого відрізка через вершину багатокутника.
Уразі коли такий прохід матиме місце, то перегляд наступної сторони багатокутника можна опустити, оскільки прохід відбувається через спільну вершину двох суміжних сторін.
Перш ніж записати умову наявності проходу побудованого відрізка через вершину багатокутника, проаналізуємо, через
яку саме вершину -pt чир і + 1 - він пройде.
На кожному кроці виконання алгоритму розглядається по
точна сторона багатокутника, вершинами якої є точки р; ір і + 1 . Якщо перетин відбувався б у точці pt, яка належить і поперед ній стороні у порядку перегляду багатокутника, то такий факт був би зафіксований на попередньому кроці. Тому якщо і є пе ретин в одній із вершин, що належать поточній стороні, то цією
вершиною буде вершина рі+1. Виникає запитання щодо аналізу вершини р х : чи не буде вона пропущена при такому перегляді? Ні, оскільки вершина р1 одночасно належить як першій у по рядку перегляду стороні багатокутника, так і останній, при дослідженні якої вона буде проаналізована як вершина з поточ ним значенням рі + 1 .
264
Отже, перетин відрізка з кінцями у точках р ір' з вершиною р.+1 поточної сторони багатокутника визначатиметься такими умовами:
[(Р - Р') х (РІ - Р')] • ІІР ~ Р') х (Рі+1 - Р'П = 0; tiPi+l -РІ) х ІР' 'Рі)] • [(РІ+І ~РІ)Х(Р -Рі)] < 0.
Однак лишається відкритим питання, якого типу відбувся прохід через вершину - перетин чи дотик. Відповідь на нього можна отримати, перевіривши, як розміщені вершиниpt_t ipt+1 відносно прямої, що проведена через відрізок з кінцями у точ ках р' ір. Якщо вони знаходяться у різних півплощинах, то це є ознакою того, що має місце перетин у вершині рі і необхідно збільшити кількість перетинів на 1. Якщо вершини р1_1 і рі+1 знаходяться в одній півплощині, то це означає, що має місце дотик побудованого відрізка до вершини pt і при цьому кіль кість перетинів залишається незмінною.
4. На четвертому і на останньому кроці необхідно перевіри ти збіг точки р з однією з вершин багатокутника або його сторо ною. Якщо такий збіг матиме місце, то виконання алгоритму необхідно завершити, оскільки це означає, що точка р нале жить заданому багатокутнику.
Розглянемо випадок, коли у наявності збіг точки з поточною стороною багатокутника. Така ситуація характеризуватиметь ся виконанням умов:
[(Р - Р') х (РІ ~ Р')] • ІІР - Р') х (Рі+і - Р')] < 0;
[(РІ+І ~РІ) х (Р'-Рі)] • [(РІ+І -РІ) х (Р-Рі)] = 0.
В іншому випадку не виключений збіг з вершиною багато кутника. У такому разі виконуватимуться умови:
[(Р - Р') х (pt - р')] • [(р - р') х (рі+1 - р')] = 0;
[(Рі+і -РІ) х (Р'-РІ)] • [(РІ+І ~РІ)Х(Р -РІ)] = 0.
Варто пояснити, чому перевірка збігу точки р з вершиною багатокутника або його стороною винесена на останнє місце. Причиною цього є те, що, по-перше, якщо дана ситуація і буде мати місце, то лише один раз, а по-друге, вірогідність її, порів няно з перетином сторін багатокутника, значно менша.
5. І наостанок слід зазначити: у разі невиконання всіх опи саних вище умов можна зробити висновок, що відрізок, утворе ний точкамир' ір, і поточна сторона багатокутника з вершина ми у точках рі ірі+1 не перетинаються. У такому разі, якщо ще не всі сторони багатокутника розглянуто, необхідно переходи ти до аналізу наступної сторони.
Тепер уже можна розглянути представлення описаного ал
горитму у вигляді фрагмента Pascal-програми: |
|
х_0 := х т а х + 1; у_0 := у_1; count := 0; |
{Блок ініціалізації.} |
і := 1; flag := false; |
|
265
r e p e at |
{Перегляд ребер заданого багатокутника.} |
if і < П then |
{Якщо не досягнуто останньої вершини, то визначення вершин} |
begin |
{охоплюючого прямокутника для поточного ребра.} |
х_3 := тах(х[і], х[і + 1]); |
|
у_2 := min(y[i], у[і + 1]); у_3 := тах(у[і], у[і + 1]); |
|
end |
|
else |
{Визначення вершин охоплюючого прямокутника для ребра} |
begin |
{з останньою вершиною багатокутника.} |
х_3 := тах(х[і], х[1]); |
|
у_2 := тіп(у[і], у[1]); у_3 := тах(у[і], у[1]); |
|
end; |
{Якщо охоплюючі прямокутники перетинаються,} |
if (х_3 >= х_1) and (у_1 >= у_2) and (у_3 >= у_1) |
|
then |
{то визначення параметрів для умови перетину відрізків:} |
begin |
|
р_0_12 := (х_1 - х_0) * (у[і - у_0) - (х[і] - х_0) * (у_1 - у_0); |
|
if і < п |
|
then |
{якщо не досягнута остання вершина багатокутника;} |
begin
р_0_13 ; (x_1 - x_0) * (y[i + 1 ] - y_0) - (x[i + 1 ] - x_0) * (y_1 - y_0);
р_2_30 |
: |
(x[i + |
1] - x[i]) * (y_0 - y[i]) - (x_0 - x[i]) |
* |
(y[i + |
1] |
- y[i]); |
|
р_2_31 |
: |
(x[i + |
1 ] - x[i]) * (y_i - y[i]) - (x_1 - x[i]) * |
(y[i + |
1 ] |
- y[i]); |
||
end |
|
|
|
|
|
|
|
|
else |
|
|
{якщо досягнута остання вершина багатокутника.} |
|||||
begin |
|
|
|
|
|
|
|
|
Р_0_13 |
= (х_1 |
- х_0) |
(У[1] - У_0) - (х[1] - х_0) * (у_1 |
- у_0); |
||||
Р_2_30 |
= (х[1] - х[і]) |
(У_0 - у[і]) - (х_0 - х[і]) * |
(у[1 ] |
- у[і]); |
||||
Р_2_31 |
= (х[1] - х[і]) |
' ( у _ і - у [ і ] ) - ( х _ і - х [ і ] ) * ( у [ і ] - у [ і ] ) ; |
||||||
end; |
|
|
|
|
|
|
|
|
if (Р_0_12 * р_0_13 < 0) and (р_2_30 * р_2_31 < 0) |
|
{Якщо відрізки} |
||||||
then inc(count) {перетинаються в одній точці, то збільшити лічильник на 1,}
else |
{у протилежному випадку} |
begin |
|
if І < П - 1 |
{обчислення параметрів ознаки для вершини: перетин чи дотик.} |
then |
|
begin |
{Якщо не досягнуто останнього ребра багатокутника.} |
а := (х[і] - х_1 )*(у_0 - у_1) - (у[і] - у_1 )*(х_0 - х_1);
b := (х[і + 2] - х_1 )*(у_0 - у_1) - (у[і + 2] - у_1 )*(х_0 - х_1);
end |
|
else |
{Якщо досягнуто останнього ребра багатокутника.} |
begin |
|
а:= (х[і] - х_1) * (у_0 - у_1) - (у[і] - у_1) * (х_0 - х_1);
Ь:= (х[1] - х_1) * (у_0 - у_1) - (у[1] - у_1) * (х_0 - х_1); end;
{Якщо є перетин,} if (р_0_12 * р_0_13 = 0) and (р_2_30 * р_2_31 < 0) and (а * b < 0)
then inc(count) |
{то збільшити лічильник на 1,} |
|
|
{інакше якщо точка збігається з вершиною,} |
|
else if (р_0_12 * р_0_13 <= 0) and (р_2_30 * р_2_31= |
0) |
|
then flag := true; |
{то завершення |
пошуку.} |
end;
end;
266