Выпуклая оболочка

Об этом калькуляторе

Калькулятор выпуклой оболочки находит наименьший выпуклый многоугольник, содержащий набор точек на плоскости, с помощью алгоритма монотонной цепи Эндрю. Он перечисляет угловые вершины оболочки против часовой стрелки, подсчитывает, сколько точек лежит на оболочке и сколько внутри, и показывает точные площадь и периметр, а диаграмма рассеяния очерчивает результат. Повторяющиеся точки и точки на одной прямой обрабатываются корректно.

Как найти выпуклую оболочку

1. Введите точки парами x,y через запятую — порядок не важен.
2. Калькулятор объединяет повторяющиеся точки и сортирует их слева направо.
3. Он проходит по отсортированным точкам, строя нижнюю и верхнюю границы и оставляя только угловые вершины, в которых контур поворачивает влево.
4. Посмотрите вершины оболочки, площадь и периметр, а также контур, нарисованный поверх ваших точек.

Типичные примеры

• Вершины квадрата 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 вершин оболочки, так как пик выступает над верхней стороной