БрзиОмотач

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

БрзиОмотач је метод налажења конвексног омотача коначног скупа тачака у равни. Користи подели па владај приступ сличан оном који се који се користи у Квиксорт алгоритам, одакле и добија своје име. Просечна сложеност овог алгоритма је О(н * лог(н)), а у најгорем случају је О(н²) (квадратна).

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

Под просечним околностима алгоритам функционише прилично добро, али обрада се успорава у случајевима високе симетрије и уколико тачке леже на кружници. Алгоритам може да се растави на следеће кораке:

Наћи тачке са минималном и максималном x координатом, оне морају бити део конвексног омотача;
Формирати линију од те две тацке и искористити је да би се поделиле у два подскупа тацака које це се обрадити рекурзивно;
Одредити тачку са једне стране линије са максималном раздаљином од линије. Две претходно одабране линије и ова нова сада формирају троугао;
Тачке које се налазе у троуглу не могу бити део конвексног омотача те се игноришу у следећим корацима;
Поновити претходна два корака над две линије које формирају троугао (не основном линијом);
Наставити са тиме док не преостане висе тачака, рекурзија стигне до краја и тачке које смо одабирали не формирају конвексни омотач;

Референце[уреди | уреди извор]

Барбер, C. Брадфорд; Добкин, Давид П.; Хухданпаа, Ханну (1. 12. 1996). „Тхе qуицкхулл алгоритхм фор цонвеx хуллс” (ПДФ). АЦМ Трансацтионс он Матхематицал Софтwаре. 22 (4): 469—483. дои:10.1145/235815.235821.