Построяване на изпъкнала обвивка. Използва се алгоритъма Греъм. Този алгоритъм позволява построяването на изпъкнала обвивка около многоъгълник (фиг. 1).
Ако си представим забити върху плоскост гвоздеи и около тях опънем ластик, той ще образува форма, образувана от най-външните гвоздеи и съдържаща останалите. Формата се нарича – изпъкнала обвивка. Изпъкналата обвивка на множество от точки X в реално векторно пространство V е най-малката обвивка съдържаща X. Един обект е обвивка ако за всяка двойка от точки в този обект, всяка точка от свързващата ги отсечка принадлежи на обекта. Ако един полигон има ъгъл 180 или повече градуса, то той не е обвивка.
 |
| Фиг. 1. Алгоритъм Сканиране на Греъм |
В алгоритъма на Греъм точките се сортират по нарастване на техните y координати. При равенство по-малката x-координата се поставя първа. Останалите точки се сортират по нарастване на ъгъла спрямо x -оста, точката P и точката от оставащото множество. Следователно първи при сортирането ще са точките най-вдясно с най-малки ъгли, а точките най-вляво ще са последни.
