Опукла оболонка
Опукла оболонка набору точок
Про цей калькулятор
Калькулятор опуклої оболонки знаходить найменший опуклий многокутник, що охоплює набір точок на площині, за алгоритмом монотонного ланцюга Ендрю. Він перелічує кутові вершини оболонки проти годинникової стрілки, рахує, скільки точок лежить на оболонці, а скільки всередині, і показує точні площу й периметр разом із діаграмою розсіювання з обрисом результату. Точки-дублікати й точки на одній прямій обробляються правильно.
Як знайти опуклу оболонку
- Введіть точки як пари x,y через кому — порядок не важливий.
- Калькулятор об’єднує дублікати й сортує точки зліва направо.
- Він проходить відсортованими точками, будуючи нижню й верхню межі та залишаючи лише кутові вершини, де обрис повертає ліворуч.
- Перегляньте вершини оболонки, площу й периметр, а також обрис, намальований поверх ваших точок.
Типові приклади
- Вершини квадрата 0,0 6,0 6,4 0,4 із внутрішніми точками 3,2 і 2,1 → 4 вершини оболонки, площа 24, периметр 20
- Трикутник 0,0 4,0 0,3 → 3 вершини оболонки, площа 6, периметр 12
- Точки на одній прямій 0,0 1,1 2,2 3,3 → вироджена оболонка (відрізок), площа 0
- Квадрат 0,0 4,0 4,4 0,4 плюс вершина 2,5 → 5 вершин оболонки, бо пік виступає над верхньою стороною
Поширені запитання
Що таке опукла оболонка?
Опукла оболонка набору точок — це найменший опуклий многокутник, що містить їх усі, — ніби натягнути гумку навколо крайніх точок і відпустити, щоб вона щільно їх обхопила.
Які точки стають вершинами оболонки?
На оболонці лежать лише крайні кутові точки. Точки строго всередині фігури та точки, що лежать точно на ребрі оболонки, не вважаються вершинами.
Як обробляються точки-дублікати й точки на одній прямій?
Спочатку однакові точки об’єднуються. Якщо всі точки лежать на одній прямій, оболонка вироджується у відрізок із нульовою площею, і калькулятор позначає її як вироджену.
Скільки точок потрібно?
Щоб утворити оболонку з додатною площею, потрібно щонайменше три різні точки, що не лежать на одній прямій.