Алгоритам увијања поклона

Из Википедије, слободне енциклопедије

Увијање поклона је алгоритам рачунарске геометрије за проналажење конвексног омотача датог скупа тачака.

Увод[уреди]

Алгоритам увијања поклона са одабиром крајње десне тачке као почетне

У случају равни алгоритам увијања поклона се назива још и Џарвисов марш, по Р. А. Џарвису који га је објавио 1973 године. Алгоритам увијања поклона је добио назив по начину на који се проналазе тачке конвексног омотача. Ако замислимо да су на местима тачака забодене усправне чиоде, алгоритам се може објаснити помоћу конца (омотача) који завежемо за почетну чиоду затегнемо га на напоље а затим обмотамо око скупа тачака, односно чиода, обухвативши тиме цео скуп унутар конца. Алгоритам увијања поклона је настао као оптимизација директног геометријског приступа за одређивање конвексног омотача. У случају тродимензионалног скупа тачака уместо конца бисмо користили користили папир за увијање, одакле долази и назив.


Алгоритам[уреди]

Овај алгоритам се заснива на постепеном проширивању пута конвексног омотача. Основа алгоритма је изабирање екстремне тачке датог скупа, која засигурно припада конвексном омотачу. Узмимо за екстремну тачку ону са најмањом x-координатом, а уколико има више таквих ону са најмањом y-координатом. Означимо почетну тачку са p1. Пролазећи кроз све тачке скупа, проналазимо ону која заједно са почетном тачком заклапа најмањи угао са x-осом. Нова тачка добија вредност p2. Поступак се затим понавља за нову тачку омотача. Проналажење следеће тачке омотача захтева n-k корака, где је n укупан број тачака а k број пронађених тачака омотача, што захтева временску сложеност од О(n).

Псеудокод[уреди]

У наредном псеудокоду претпоставићемо да је изабрана почетна тачка она са највећом х координатом, односно најдеснија тачка скупа. Уколико има две или више тачака са највећом х коориднатом изабраћемо међу њима ону са најмањом у координатом.

Увијање поклона

Улаз: p1, p2 , ...,pn (скуп тачака у равни).

Излаз: P (конвексни омотач тачака p1, p2 , ...,pn
begin

Нека је P празан скуп;
Нека је p тачка са највећом x-координатом;
(и са најмањом y-коориднатом, ako има више тачака са највећом x-координатом);
Укључи p у скуп P ;
Нека је L права паралелна са x-осом;
while омотач P није завршен do
Нека је q тачка за коју је најмањи угао између L и –p–q–;
Укључи q у скуп P ;
L := права –p–q– ;
p := q;

end


Индуктивна хипотеза[уреди]

Математичка основа за примену алгоритма за увијање поклона је геометријски метод за одређивање конвексног омотача скупа тачака. Оба метода се доказују индукцијом. АУП је директна последица примене следеће индуктивне хипотезе:

За дати скуп од n тачака у равни, умемо да пронађемо конвексни пут дужине k < n који је део конвексног омотача скупа.

Временска сложеност[уреди]

За сваку тачку треба израчунати углове између правих ка свим преосталим теменима и x-осе и затим пронаћи минимални угао у скупу од n-k правих. Временска сложеност у општем случају је О(nh) где је h број тачака конвексног омотача. У најгорем случају, све тачке скупа могу да припадају омотачу и па је стога временска сложеност алгоритма увијања поклона О(n2).

Спољашње везе[уреди]