Polygon one-way paths

How fast can be that, which we call slow today!

Goal of the document:

Целта на този документ е да съхранява знанието натрупано за намиране еднопосочните пътища в полигон.

Author

Daniel Sapundjiev

Please, don't copy this content across the web, put links to it, cause its often revised! Thanks!

Date

01 January 2025

Introduction

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

Наблюдават се някои характеристики:

• Всяка точка може да бъде точка на обръщане.
• Лява и дясна точка могат да бъдат съседни точки.
• Може всички точки от полигона да бъдат точки на обръщане на посоката (леви и десни)

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

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

• винаги към нарастващи пътища
• винаги към намаляващи пътища
• винаги в края на пътя
• винаги да са в началото

Друга особеност е, че първия връх може да е крайна точка, а може и да е между 2 крайни върха. Алгоритъмът може да обходи върховете само в една посока. Като първоначално няма да е сигурно дали първата точка е крайна или не. Но може да се определи дали пътя е нарастващ или намаляващ. В края когато се приключи итерирането се гледа дали последния път съвпада с посоката на началния. Ако съвпада то те са един път, ако не то първия връх ще е крайна точка.

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

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

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

При итерацията се итерират 2 последователни точки. Когато се сравнят Х координатите им се знае дали са част от нарастващ или намаляващ път. Когато се промени посоката предходната точка е тази, която е крайна точка за пътя. Създава се елемент за крайна точка. Но вече е ясно и каква е посоката на следващия път, тъй като те се редуват, той е нарастващ, ако до момента е бил намаляващ, и обратно намаляващ, ако до момента е би нарастващ. Освен, че се знае посоката, се знае първата му точка и следващата от пътя. Преместват се напред и ако се променя посоката, то пътя е само от две точки, които са последователни. Ако не е се продължава докато не се промени посоката. !!! Хубавото е, че при започване на новия път вече е в позиция в която първия елемент, който е задължителен вече е отметнат и се преминава към следваща позиция, когато може да има обръщане на посоката на пътя. Затова се създава елемент за крайна точка и се преместват точките на следваща позиция

За всяка крайна точка се създава елемент за крайна точка.

При създаване на крайна точка е необходимо да се посочи коя е предходната крайна точка. Затова се пази предходната. Но ако се пази като последно добавена lastAdded то всеки път ще трябва да се присвоява примерно dirPoint := TChangeDirectionPoint.Create; dirPoint.Prev := lastAdded; lastAdded.Next := dirPoint; lastAdded := dirPoint; // Това присвояване може да бъде спестено, без да се ползва повече памет. вместо lastAdded се именоват променливите dirLeftPoint, dirRightPoint - по този начин винаги едната ще е предишна на другата. Това е така, защото се редуват леви и десни точки, нарастващи и намаляващи пътища.

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

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

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

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

Абстрактен Алгоритъм

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

Алгоритъм

1. Вземат се първата и втората точка. Докато първата и втората точка имат еднакъв Х на мястото на втората се слага следващата точка. Така накрая се стига до Точка 1 и Точка 2 които са с различен Х. 2. Проверява се дали Точка 2 има по-голям Х, в случай, че е - по-голям - то пътя е нарастващ. - по-малък - то пътя е намаляващ Когато пътя е намаляващ се правят проверки до достигане на нарастващ път. 3. След което се определи пътя, се търси крайната точка, където пътя се обръща след което се търси крайната точка където пътя се обръща отново.

За размисъл

- Може първоначално да се връща назад за определяне на началото на първия път. За да не се трие накрая.

Back to main menu