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

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

Увод[уреди | уреди извор]

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

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

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

Псеудокод[уреди | уреди извор]

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

Увијање поклона
`Улаз: p₁, p₂ , ...,p_n (скуп тачака у равни).` `Излаз: P (конвексни омотач тачака p₁, p₂ , ...,p_n 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 број тачака конвексног омотача. У најгорем случају, све тачке скупа могу да припадају омотачу и па је стога временска сложеност алгоритма увијања поклона О(n²).

Литература[уреди | уреди извор]

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „33.3: Finding the convex hull”. Introduction to Algorithms (2nd изд.). MIT Press and McGraw-Hill. стр. 955—956. ISBN 0-262-03293-7.
Jarvis, R. A. (1973). „On the identification of the convex hull of a finite set of points in the plane”. Information Processing Letters. 2: 18—21. doi:10.1016/0020-0190(73)90020-3.

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