Алгоритми за пресмятане на лице, принадлежност на точка към многоъгълник и окръжност

Знаеш ли кое ще е добре за тази статия? Малко картинки. Айде да сложиш нещо, а?

Проблем на художника

Доста често срещан проблем в компютърната графика е т.нар. "Проблем на художника". Например, нека да има два квадрата един върху друг. Първият е с долен ляв ъгъл в (5,5) и горен десен в (10,10). Вторият е върху него и е от (0,0) до (15,15). Пускаме си програмата. Тя рисува първия квадрат. След това рисува втория. Ама първият въобще не се вижда - 0%. Защо тогава въобще сме го рисували? Губи се време. Почти толкова време, колкото сме рисували видимата част, сме рисували и тази, която не се вижда. Няма смисъл. Ами ако не са два квадрата? Ако например е голямо, огромно ниво в Duke Nukem Forever? Ако има лабиринт от общо 250 коридорчета, всяко с четири стени, таван и под - в даден момент се виждат едно, две най-много четири-пет коридорчета (на някой кръстопът). Какво правим тогава? 99% от времето ще си го губим с неща, които никога няма да се видят. Можем да го губим с други работи, например по-качественото рисуване на това, което се вижда.
Това е голям проблем днес, но е било още по-голям проблем преди години. Тогава компютрите са имали около един процент от текущата си мощност и ефективността е била от наистина голямо значение. През годините е била извършена много научна работа по въпроса. Първият човек, който успешно го е приложил на практика се казва Джон Кармак. Той е създал DooM и съответно е променил света на компютърните игри, посоката на софтуерната индустрия и живота на майките на средна възраст завинаги. Така де, важен проблем. Трябва да се знае за какво става въпрос.

След като всичко това беше казано, днес ние… няма да решаваме този проблем.

Лице на многоъгълник, детерминанта

Не, спокойно. Скоро ще почнем и това да правим. Но с текущите знания по темата ще стигнем до, с една дума, никъде. Да започнем с по-лесните неща, които ще доведат дотам. Например, как да намерим лице на многоъгълник? А? Не е много лесно, мдам. Повечето алгоритми, отнасящи се към компютърната графика, работят на принципа "разделяй и владей".
По-малките задачи се решават по-лесно от по-големите.
Да, знам, звучи хипер мега очевидно. Но трябва да се каже. Има ли алгоритъм за намиране на лице на триъгълник? Има, сега ще го видим. Има ли алгоритъм за разделяне на многоъгълник на триъгълници? Има. Ами, разделяме го на триъгълници и намираме лицето на всеки от тях. Супер! Естествено, има малко частни случаи, но пак става лесно.

Лице на триъгълник

Ако имаме триъгълник в две измерения, много лесно може да му намерим лицето. Например, с детерминанта. Координатите му са $(x_0, y_0), (x_1, y_1), (x_2, y_2),$, тогава лицето му е:

(1)
\begin{align} S = \cfrac{1}{2} \begin{vmatrix} x_0 & y_0 & 1\\ x_1 & y_1 & 1\\ x_2 & y_2 & 1\\ \end{vmatrix} \end{align}

Защо това е така? С една дума: Алгебра.
Като се разпише, например, Хероновата формула за лице, използваща само страните на триъгълника, се получава някакво дъълго уравнение. След заместване с координатите, съкращване и ритуално жертвоприношение на два асистента по математика, се получава точно израза, даден от детерминантата. Тоест, това не е някаква безкрайна математическа истина. Няма гаранция, че в този вид ще работи за нещо различно от триъгълници в нещо различно от двуизмерно евклидово пространство. Който иска да разбере как стават по-сложните неща, да учи повече Аналитична геометрия, полезно е :)
Забележи, че това лице въобще не е казано, че е положително. Това е насочено лице. Дълга история. Като абсолютна стойност е толкова, колкото ни трябва, но може да е със знак минус. Това се използва после.

Лице на трапец

За момента ще разглеждаме лице на трапец с основи успоредни на една от координатните оси. Силно се надявам да няма човек, който чете това и да не знае как става. Но все пак, при основи a и b и височина h, лицето на трапеца е:

(2)
\begin{align} S = \cfrac{(a + b)h}{2} \end{align}

Ще го използваме.

И все пак, лице на многоъгълник

Как става?
Трябват ни точките от многоъгълника. За всеки две съседни от тях (т.е. за $(p_1,p_2), (p_2, p_3) \cdots (p_n,p_1)$) намираме лицето на трапеца образуван от двете точки и техните проекции върху оста Ox.
Тоест, ако точките са (3,5) и (5,7), основите на трапеца са 3 и 5, а височината му е 7-5 = 2. Лицето е $\dfrac{(3+5)*2}{2} = 8$. Важно е да се забележи нещо. Абсолютно Нищо не ограничава лицето тук да е по-малко от 0. В една част от случаите то ще е по-малко от 0 и това е добре. Там е работата, че всеки трапец все едно "слага" или "маха" към и от цялата фигура. Ако лицето е > 0, то слагаме този трапец, иначе го махаме. В крайна сметка лицето е точно толкова, колкото ни трябва. Трудно се обяснява. Една картина казва толкова, колкото хиляда думи. Не че в момента има картинка, де - нарисувай си го :)

Впрочем, формулата в крайна сметка се получава:

(3)
\begin{align} S = \cfrac{1}{2} \sum_{i = 0}^{n - 1}( x_i y_{i + 1} - x_{i + 1} y_i) \end{align}

Проверка дали две отсечки се пресичат

Насоченото лице на триъгълник, т.е. детерминантата на точките му зависи от реда, в който са взети точките. Т.е. насоченото лице на точките $p_1, p_2, p_3$ е същото по големина, но различно по знак от насоченото лице на $p_1, p_3, p_2$. Това е защото има значение дали вземаме точките по часовниковата стрелка или обратно. Свойство на детерминантите, какво да се прави. Като следствие може да се изведе следната теорема:

Теорема 1

Дадена е отсечка (a,b), която разделя равнината на две полуравнини
Две точки $p_1$ и $p_2$ са в различни полуравнини тогава и само тогава, когато детерминантите $(a,b,p_1)$ и $(a,b,p_2)$ са с различен знак.
Доказателството следва директно.

Оттук може да се изведе лесен критерий дали две отсечки се пресичат. С $det(a,b,c)$ означаваме насоченото лице на триъгълника определен от точките a, b и c.
Дадени са две отсечки, [a,b] и [c,d]. Те се пресичат, когато са изпълнени следните
условия:

(4)
\begin{array} {}det(a,b,c) * det(a,b,d) \le 0 \\ det(c,d,a) * det(c,d,b) \le 0 \\ \end{array}

Или, изказано с думи - двата края на (a,b) са от различни страни на (c,d) и двата края на (c,d) са от различни страни на (a,b).
За домашно - изведи условие, при което една права/отсечка пресича отсечка точно в нейния край. Почти същото както досега е.

Проверка дали точка принадлежи на многоъгълник

Алгоритъмът се нарича Монте Карло.
Това е много лесно. Да кажем, че търсим дали точката A е в многоъгълника M или не. Основното, което трябва да се забележи е, че многоъгълникът е затворена крива. Т.е. разделя цялата равнина на две части - вътре и вън. Разликата между вътре и вън е от коя страна на линията си. Лесна работа, особено за изпъкнали многоъгълници. Обаче има и още! Това важи и за всякакви други многоъгълници. Така де, ако си вътре и пресечеш линията, значи вече си вън. Ако си вън и пресечеш, влизаш вътре. Ако си вътре и пресечеш линията четен брой пъти, оставаш вътре. Тук вече се заражда алгоритъм.

Вземаме произволна права, минаваща през точката. Гледаме дали правата минава през някой от върховете на многоъгълника. Ако е така, вземаме нова права. След малко ще стане ясно защо алгоритъмът не работи когато правата минава през ъгли. Ако не е някаква много важна работа и не ти пука за 1/10000 шанса за грешка, карай с текущата права. Ама все пак ще е по-хубаво да не минава през върхове. Грозно е.

Така, като казах произволна права имах предвид произволен лъч. Т.е. от едната страна е безкраен, от другата страна свършва в A. И гледаме колко пъти пресича някоя от страните на многоъгълника. Как става това? Пробвай с всички страни и виж колко от тях пресича. Ако сборът е четно число, значи тръгвайки от A когато отидем в безкрайността, сме пресекли линията на многоъгълника четен брой пъти. Тъй като в безкрайността няма многоъгълник, то значи и в началото сме тръгнали извън него.Ако е нечетен брой пъти, например 1 (но може и 3, даже 5) това означава, че сме били вътре и сме излезли вън.

Супер, алгоритъмът работи и даже получава верния отговор.
Освен когато правата минава през връх. Тогава излиза, че пресича две отсечки, а всъщност минава през линията само веднъж. Затова избираме да не минава през връх. Друго решение е да се гледа отсечката $[a,b)$, вместо $[a,b]$. Но, в крайна сметка, идеята е тази.

Изпъкнала обвивка на многоъгълник

Изпъкналата обвивка на множество от точки е такъв многоъгълник, който е изпъкнал и съдържа в себе си оригиналния многоъгълник. Минималната изпъкнала обвивка е тази с най-малко лице.
Намира се по един заплетен, но не много сложен алгоритъм.
Нарича се Сканиране на Греъм (Graham Scan).
Лесно се вижда, че минималната обвивка е подмножество на върховете на многоъгълника. Мисли си за цялата операция като за опаковане на многоъгълника. За да опаковаш един кашон здраво, не ти трябва първо да го слагаш в друг, по-голям кашон, нали? Освен ако не е пълен с полу-вкиснали праскови, тогава може да е добра идея. За целите на компютърната геометрия, обаче, приемаме, че разглежданите многоъгълници не са пълни с полу-вкиснали праскови.

Също толкова лесно се вижда, че мин. изп. обв. на един многоъгълник с точки $p_1, p_2, \cdots p_n$ е същата като мин. изпъкнала обвивка на всеки друг многоъгълник със същите точки $p_1, p_2, \cdots p_n$. Тоест, обвивката не е на даден многоъгълник, а на точките от този многоъгълник. Помисли малко върху тази част.

Това означава, че можем да си нагласяме точките както си искаме. Това и ще направим. Ще си ги нагласим така, че да са ни удобни.
Да приемем за момент, че точките на многоъгълника са сортирани по часовниковата стрелка.
Какво означава това? Виж долу, там е обяснено. Та, приемаме го.
Какъв е критерият за изпъкнал многоъгълник? В него няма ъгъл по-голям от 180 градуса. Т.е. всички ъгли са изпъкнали (да, оттам идва името). Т.е. ако вземем кои да е три поредни точки от изпъкналата обвивка, ъгълът образуван от тях е по-малък или равен на 180 градуса. Ако това не е така, то значи точката на върха на ъгъла просто не принадлежи на обвивката (защото ако я махнем, този ъгъл изчезва). И вече започва да става ясно накъде отива работата.
Вземаме точките подред, започвайки от първата и вървим напред. Ако в някой красив момент се окаже, че ъгълът $p_{k-2}, p_{k-1}, p_{k}$ е по-голям от 180 градуса, то махаме точката $p_{k-1}$ и пак проверяваме за $p_{k-3}, p_{k-2}, p_{k}$, защото този ъгъл вече може да е станал и той по-голям от 180. Ако е така, махаме още една точка и така дотогава, докато условието продължава да е изпълнено. След това пак вървим напред.
Така проверяваме докато стигнем и минем $p_n$, или докато останат само 3 върха (всеки триъгълник е изпъкнал).
Това, което остане, е изпъкнал многоъгълник, като освен това е и минимална изпъкнала обвивка на началния многоъгълник.
Може би е трудно да се разбере от първия път. С практика всичко се получава. Вярвам в теб!

Сортиране на точките на многоъгълник

Да бъдат сортирани точките по часовниковата стрелка - това е често срещан термин в графиката.
Това означава, че точките са сортирани по нарастващ ъгъл спрямо някаква основна права. Например, в часовника, точките са номерирани по нарастващ ъгъл спрямо вертикалната права, минаваща през центъра на цифреблата (т.е. минаваща и през "12").
В случая сортирането става по един от многото добре известни алгоритми за сортиране, като просто трябва да се даде някакъв критерий за сравнение на две точки.
Впрочем, в математиката под права посока се разбира това, което нормалните хора наричат обратно на часовниковата стрелка. Ще работим с правата посока.
По и обратно на стрелката се изчислява по един и същи начин, о каква изненада.

Ако не те интересува как точно се пише алгоритъмът за тази работа, можеш спокойно да продължиш нататък.

Приятно рисуване :)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License