Convex Hull

1. INTRODUCERE

Tema propusă

În cadrul acestui proiect ne-am propus să abordăm o temă interesantă, diferită de cunoştinţele anterioare. De aceea am ales algoritmul convex hull, având ca şi temă „Determinarea înfăşurătoarei pentru un set de puncte”.

În decursul perioadei de practică am încercat să atingem următoarele obiective:

- Familiarizarea cu structurile de date specifice problemelor de geometrie analitică în plan.

- Implementarea algoritmului de ordine relativă a punctului în plan.

- Determinarea înfăşurătorii convexe a unei mulţimi de puncte.

2. FUNDAMENTAREA TEORETICĂ

Convex Hull-ul mulţimii P = { pi = (xi , yi) R2 / i = 0,n-1} este reprezentată de poligonul convex de arie minimă care încadrează toate punctele mulţimii P.

Figura 1. Poligonul convex

Primul algoritm liniar a fost propus de Sklansky în 1972. Era scurt şi elegant. Din nefericire era incorect. Primul algoritm corect a fost propus de McCallum şi Avis în 1979. Algoritmul considerat ca fiind cel mai bun a fost cel realizat de Melkman în 1987. Este puţin probabil să se realizeze un algoritm mai bun.

Algoritmul este folosit în foarte multe domenii:

a) Calculul drumului / traiectoriei razelor (ex. jocurile video)

b) Gasirea unui drum printre obstacole( path finding )

c) Modele de recunoastere vizuala

d) Sistemul Informatic Geografic

e) Geometrie (ex. estimarea geometrică).

Algoritmi şi Complexităţi

Există mai mulţi algoritmi de calcul al înfaşurătorii convexe. Majoritatea algoritmilor de complexitate O (n log n) necesită o presortare a punctelor, pentru un timp mai bun.

Algoritm Complexitate

Naive Bruteforce O ( n4 )

Better Bruteforce O ( n 3 )

Gift Wrapping (Jarvis March) O ( nh )

Quick Hull O ( nh )

Graham Scan O ( n log n)

Divide and Conquer O (n log n)

Monotone Chain O (n log n)

Incremental O (n log n)

Marriage before Conquest O (n log h)

Shatterhull O (n log h)

Chan’s O (n log h)

n – numărul de puncte

h – numărul de puncte din Convex Hull