Построение выпуклой оболочки

Постановка задачи

Пусть задано некоторое множество точек на плоскости. Выпуклая оболочка — наименьший выпуклый многоугольник, содержащий данные точки.

Вообразим, что плоскость — это деревянная доска, утыканная гвоздями в каждой точке из данного множества.Выпуклая оболочка Теперь натянем вокруг гвоздей резиновое кольцо. Оно стянется и образует выпуклую оболочку, как показано на рисунке.

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

Алгоритм решения данной задачи чрезвычайно прост:

  1. Находим нижнюю-правую точку. Пусть это – i(0). i=i(0).
  2. Повторять :
    1. Для каждого j≠i вычисляем точку с наименьшим углом от предыдущей стороны (для второй точки – от горизонтали). Если есть две таких – берем ту, до которой расстояние больше. Пусть ее номер – k.
    2. Выводим сторону из точек с номерами i и k. i = k. пока i не станет равно i(0).
Шаг 1 Шаг 2 Шаг 3 Шаг 4

Решение задачи


Оставить комментарий