БрзиОмотач
Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
БрзиОмотач је метод налажења конвексног омотача коначног скупа тачака у равни. Користи подели па владај приступ сличан оном који се који се користи у Квиксорт алгоритам, одакле и добија своје име. Просечна сложеност овог алгоритма је О(н * лог(н)), а у најгорем случају је О(н2) (квадратна).
Алгоритам
уредиПод просечним околностима алгоритам функционише прилично добро, али обрада се успорава у случајевима високе симетрије и уколико тачке леже на кружници. Алгоритам може да се растави на следеће кораке:
- Наћи тачке са минималном и максималном x координатом, оне морају бити део конвексног омотача;
- Формирати линију од те две тацке и искористити је да би се поделиле у два подскупа тацака које це се обрадити рекурзивно;
- Одредити тачку са једне стране линије са максималном раздаљином од линије. Две претходно одабране линије и ова нова сада формирају троугао;
- Тачке које се налазе у троуглу не могу бити део конвексног омотача те се игноришу у следећим корацима;
- Поновити претходна два корака над две линије које формирају троугао (не основном линијом);
- Наставити са тиме док не преостане висе тачака, рекурзија стигне до краја и тачке које смо одабирали не формирају конвексни омотач;
Референце
уреди- Барбер, C. Брадфорд; Добкин, Давид П.; Хухданпаа, Ханну (1. 12. 1996). „Тхе qуицкхулл алгоритхм фор цонвеx хуллс” (ПДФ). АЦМ Трансацтионс он Матхематицал Софтwаре. 22 (4): 469—483. дои:10.1145/235815.235821.