Polygon clipping

How to clip polygons

Intro

Sometimes it is needed to perform some operations on polygons such as Union, Intersection, Difference. This operations leads to generation of new polygons depending on the way the given polygons overlap. We can make analogy to binary operations such as OR (Union), AND (Intersection), XOR.

Входни данни

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

Изходни данни

Списък с полигони, като всеки полигон може да има и полигони дупки в него.

Инфо

Еднопосочните пътища могат да затварят полигона както от лявата страна, така и от дясната. Но за конкретен еднопосочен път, той винаги затваря полигона от едната си страна. Не може половината път да затваря отляво, а другата отдясно.

Крайните точки на пътищата могат да отварят полигона, а могат и да го затварят след тях. Може да се отбележат какви са предварително и да се подава тази информация на алгоритъма.

Алгоритъм

Резултата се състои от определени точки от входните полигони, както и пресечени точки от ребрата им. Разбира се те трябва да са и в правилната последователност- Кои в кой полигон са, кои са в дупки и каква е последователността им в полигона или дупката.

Може да се раздели всеки полигон на еднопосочни пътища - наляво и надясно. След което да се започне едновременно прохождане на пътищата отляво надясно. По време на прохождането се изграждат резултатните полигони.

Обединение

Най-лявата от всички точки е винаги част от резултатния полигон, затова може да се започне изграждането на път с нея. След което се придвижва сканиращата линия надясно, до достигане на: - друга най-лява точка от път - вътрешна точка от път - крайна точка от път - пресечена точка от път.

Започване на път

В зависимост дали се обединяват полигони, или се изваждат или друго, пътищата започват от различни места. Примерно при обединение пътищата започват от най-левите точки. Но не от всяка най-лява. А също така могат да започват и от пресечени точки.

Завършване на път

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

Надбягване на пътишата

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

Сканираща линия

Може да се пази информация за това, кои пътища са в момента обхождани и кои определят резултатен полигон, като се ползва сканираща линия. Сканиращата линия може да се придвижи през всички точки от пътищата, но това ще са много повторения. Тъй като точките са безкрайно много, може и да е безкрайно много повторения. Затова се ползват върховете на пътищата. Когато започва обхождането на пътища в лява точка се определя далие вътре или вън от полигон. Това може да се определи като се пресече сканиращата линия с пътищата, които се прохождат в момента. Като се знае всеки път дали отваря или затваря полигон ще се разбере дали точката е вътре или вън. Необходимо ли е да се пресичат всички пътища, не може ли да се определи по-бързо дали точката е извън или вътре в полигон. Примерно, като знаем в момента кои са граничните пътища, където се отваря и затваря полигон, може само те да се проверят къде се пресичат.

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

Тъй като се ползват еднопосочните пътища в полигона, тези пътища могат да се подават като допълнителна преизчислена информация. Може да се подават паралелно в списък и от там да се вземат по индекс. А може да се подават и като списък от обекти, които държат в себе си освен полигона и дупките му така и предварително изчислените данни.

Back to main menu