Лекциите на ФМИ

За да изглеждаме умни пред другите

Начало

Начална страница

Членове на
сайта

Присъедини
се

За автори

Препоръки за писане на
статии

Формат на статиите

Форум

Новини от
форума

Последни
промени

Списък със
задачи

Първи курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

За
администратори

Create account or Sign in

Начало

Начална страница

Членове на сайта

Присъедини се

За автори

Препоръки за писане на
статии

Формат на статиите

Последни
промени

Панел за
администратори

Лекции

Първи Курс

Анализ

ЕАИ

Геометрия

ООП

Втори курс

Структури от Данни

Компютърни Архитектури

КАрх - Практикум

Основи на компютърната
графика

Функционално програмиране

ФП - Практикум

Трети курс

Логическо програмиранеУпражнения

Числени методиУпражнения

Системно
програмиранеУпражнения

Мрежово
програмиранеУпражнения

Избираеми дисциплини

Математическа Логика

Дискретна Оптимизация

Теория на Множествата

Теория на Графите

Избрани Глави от
Анализа

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

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

foldunfold

Table of Contents

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

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

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

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

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

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

Теорема 1

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

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

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

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

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

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

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

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

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

Ако имаме триъгълник в две измерения, много лесно може да му намерим лицето.
Например, с детерминанта. Координатите му са ,
тогава лицето му е:
(1)

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

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

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

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

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

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

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

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

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

Теорема 1

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

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

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

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

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

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

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

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

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

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

Също толкова лесно се вижда, че мин. изп. обв. на един многоъгълник с точки

е същата като мин. изпъкнала обвивка на всеки друг многоъгълник със същите точки
.
Тоест, обвивката не е на даден многоъгълник, а на точките от
този многоъгълник. Помисли малко върху тази част.

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

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

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

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

Покажи

Скрий

Ако имаме дадена права (например хоризонтална права с уравнение x =
0), лесно можем да сравним две точки по ъгъла между тях и правата. Как
става това? Просто в случай, че някой не помни какво се учи по Анализ 1, можем да използваме
тангенси.
Ако тангенсът на ъгъла между точка и права е по-голям, то
ъгълът е по-голям.
Това важи в интервала ,
в който функцията тангенс е строго растяща. Не ни върши твърде много работа. Ако
си харесаме някаква хоризонтална права и вземем произволни две точки от нея,
примерно
и
какво гарантира, че ъгъла между всяка точка
от многоъгълника ще образува ъгъл в
с тези точки? Нищо. Затова, няма да вземаме случайни точки.
Ще вземем
най-лявата от всички точки в многоъгълника. С най-малка x
координата. Ако има няколко най-леви - най-долната от тях. Да я кръстим Спас. Да я кръстим
A.
По този начин всички точки са надясно от A. И ъглите им
са в нужния интервал. Изключение правят точките, които имат същата
x координата като A. Тангенсът не е дефиниран
за ъгъл равен на 90 градуса. Да, ама ние вече сме се подсигурили - всички такива
точки са по-високо от A. Значи са преди A в подредба обратно на
часовниковата стрелка.

Знам, сложно беше. Другото е по-лесно. Ето малко код, който илюстрира идеята.
Само да кажа. Това не е пълната програма (стана много дълга), нито е красив код
:) Тези неща са за час по програмиране.

int sort(const void *a, const void *b);

int main()
{
//Търсим началната точка
for(int x = 0; x < MAX; x++)
{
points.add(rand() % 5, rand() % 5);
//cout<<points[x].x<<" "<<points[x].y<<endl;
minPoint = getMinPoint(minPoint, points[x]);
}
//Началната точка винаги е първа в списъка
cout<<minPoint.x<<" "<<minPoint.y<<endl;
//Алгоритъмът няма да работи за началната точка
//(там не е дефиниран ъгъл), затова я махаме
points.remove(minPoint);

//Сортиране по ъгъл
qsort(points, MAX-1, sizeof(points[0]), sort);
for(int x = 0; x < MAX-1; x++)
{
//И воала:
cout<<points[x].x<<" "<<points[x].y<<endl;
}
return 0;
}

int sort(const void *a, const void *b)
{
point pa = *(point *)a;
point pb = *(point *)b;
//Следващият ред е грешен, защото (pa.x - minPoint.x)
//може да стане нула. Не искаме да делим с 0.
//return (pa.y - minPoint.y)/(pa.x - minPoint.x)
// < (pb.y - minPoint.y)/(pb.x - minPoint.x);
//Така е по-добре:
return (pa.y - minPoint.y)*(pb.x - minPoint.x) - (pb.y - minPoint.y)*(pa.x - minPoint.x);
}

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

page_revision: 14, last_edited: 1229090363|%e %b %Y, %H:%M %Z (%O ago)

EditRate
(0)TagsDiscuss History Files
Print Site tools+ Options

Edit sections Append Edit meta Watchers Backlinks Page source Parent Lock
page Rename Delete

Help | Terms
of Service | Privacy | Report a bug | Flag as objectionable
Powered by Wikidot.com

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

Click here to edit contents of this page.

Click here to toggle editing of individual
sections of the page (if possible). Watch headings for an "edit" link when
available.

Append content without editing the whole
page source.

Check out how this page has evolved in the past.

If you want to discuss contents of this page -
this is the easiest way to do it.

View and manage file attachments for this page.

A few useful tools to manage this Site.

See pages that link to and include this page.

Change the name (also URL address, possibly
the category) of the page.

View wiki source for this page without
editing.

View/set parent page (used for creating
breadcrumbs and structured layout).

Notify administrators if there is
objectionable content in this page.

Something does not work as expected? Find out
what you can do.

General Wikidot.com documentation and help
section.

Wikidot.com Terms of Service - what you can,
what you should not etc.

Wikidot.com Privacy Policy.