Скачать 49.08 Kb.


Дата04.12.2017
Размер49.08 Kb.

Скачать 49.08 Kb.

Алгоритъм на Лян Барски за отсичане многоъгълник


Алгоритъм на Лян-Барски за отсичане многоъгълник спрямо изправен правоъгълник

Ако разделим равнината на 9 части спрямо границите на отсичащия правоъгълник, то тези части които са извън правоъгълника можем да определим като междинни ъглови(обхващащи външен ъгъл) или странични области.



ъглова

странична







Отсичащ правоъгълник

странична

ъглова







Ако разгледаме една от страните на Рi Pi+1 и приемем че тя не е хоризонтална или вертикална следва че правата която лежи на тази страна пресича и четирите прави определящи границите на отсичащия правоъгълник. Две от тези точки са потенциално входни и две са потенциално изходни.


Означаваме с tin1 и tin2 точките в които правата пресича първата хоризонтална и първата вертикална права а с tout1 и tout2 съответно вторите прави по посока на нарастване на параметъра(положителната посока на x и y във кординатната система)

Когато правата пресича междинна ъглова област е изпълнено tout1 in2 , а когато пресича прозореца tin2 <= tout1 и като вземем предвид че двата края на разглежданата страна се получават при стойности на параметъра t=0, t=1 можем да кажем, че тя ще има видима част само ако:

(І)

1: tin2 <= tout1 (правата пресича прозореца)



2 двата интервала [ tin2 ,tout1 ] и [0,1] да имат обща част

което означава, че началото на страната е преди носещата права да напусне прозореца и краят и е след като съответната права навлезе в прозореца


Изходният многоъгълник се получава като на всяка стъпка(за всяка страна) към него добавяме един или повече върхове, като редът по който ще добавяме върховете зависи от взаимното разположение на tin1 tin2 tout1 tout2 ;0 и 1 върху числовата ос.

Ако разглежданата страна има видима част(І) алгоритъма е следния:

1 Ако началото на страната е преди tin2 (т.е. 0< tin2 ) то трябва да се добави в списъка пресечната точка tin2 .В противен случай началото и вътрешно и е било добавено на предишната итерация(като крайна точка на предната страна)

2 Ако краят на страната е след tout1 (т.е. tout1 <1 ) то трябва да се добави пресечната точка . tout1 а иначе се добавя самият край на страната.


Освен това незвисимо дали разглежданата страна има или няма видима част, но преминава през ъглова област, то съответния ъгъл на прозореца трябва да се включи в списъка на изходния многоъгълник(алгоритмично включването се извършва или при влизане или при излизане на страната от ъгловата област – но не и в двата случая.)

Всяка страна може да навлезе във крайна и/или междинна ъглова област

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

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




Коьрта
Контакты

    Главная страница


Алгоритъм на Лян Барски за отсичане многоъгълник

Скачать 49.08 Kb.