сканирование Грэма

Демонстрация сканирования Грэма для поиска выпуклой двумерной оболочки.

Сканирование Грэма — это метод поиска выпуклой оболочки конечного набора точек на плоскости с временной сложностью O ( n log n ). Он назван в честь Рональда Грэма , опубликовавшего оригинальный алгоритм в 1972 году. Алгоритм находит все вершины выпуклой оболочки, упорядоченные вдоль ее границы. Он использует стек для эффективного обнаружения и устранения вогнутостей на границе.

Алгоритм

Как видите, PAB и ABC вращаются против часовой стрелки, а BCD — нет. Алгоритм обнаруживает эту ситуацию и отбрасывает ранее выбранные сегменты до тех пор, пока поворот не будет сделан против часовой стрелки (в данном случае ABD).

Первым шагом в этом алгоритме является поиск точки с наименьшей координатой Y. Если наименьшая координата Y существует более чем в одной точке набора, следует выбрать точку с наименьшей координатой X из кандидатов. Назовем эту П. точку Этот шаг занимает O ( n ), где n — количество рассматриваемых точек.

Затем набор точек необходимо отсортировать в порядке возрастания угла, который они и точка P составляют с осью x. общего назначения Для этого подойдет любой алгоритм сортировки , например пирамидальная сортировка (то есть O( n log n )).

Сортировка по углу не требует вычисления угла. Можно использовать любую функцию угла, монотонную на интервале $[0,\pi ]$ . Косинус легко вычисляется с помощью скалярного произведения или можно использовать наклон линии. Если на карту поставлена ​​числовая точность, функция сравнения, используемая алгоритмом сортировки, может использовать знак векторного произведения для определения относительных углов.

Если несколько точек имеют одинаковый угол, либо разорвите связи, увеличив расстояние ( расстояния можно использовать расстояние Манхэттена или Чебышева вместо евклидова для упрощения вычислений, поскольку точки лежат на одном луче), либо удалите все точки, кроме самой дальней.

Алгоритм последовательно рассматривает каждую точку отсортированного массива. Для каждой точки сначала определяется, является ли движение из двух точек, непосредственно предшествующих этой точке, поворотом налево или поворотом направо. При повороте направо предпоследняя точка не является частью выпуклой оболочки, а находится «внутри» нее. Затем то же самое определение делается для набора последней точки и двух точек, которые непосредственно предшествуют точке, которая, как выяснилось, находилась внутри корпуса, и повторяется до тех пор, пока не встретится набор «поворот налево», после чего алгоритм переходит дальше. до следующей точки в наборе точек отсортированного массива за вычетом всех точек, оказавшихся внутри оболочки; нет необходимости рассматривать эти моменты еще раз. (Если на каком-либо этапе три точки лежат на одной прямой, можно либо отказаться от этого, либо сообщить об этом, поскольку в некоторых приложениях требуется найти все точки на границе выпуклой оболочки.)

Опять же, определение того, представляют ли три точки «поворот налево» или «поворот направо», не требует вычисления фактического угла между двумя сегментами линии и фактически может быть достигнуто только с помощью простой арифметики. За три очка $P_{1}=(x_{1},y_{1})$, $P_{2}=(x_{2},y_{2})$ и $P_{3}=(x_{3},y_{3})$, вычислите z координату векторного произведения двух векторов ${\overrightarrow {P_{1}P_{2}}}$ и ${\overrightarrow {P_{1}P_{3}}}$, что задается выражением $(x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})$. Если результат равен 0, точки лежат на одной прямой; если он положительный, три точки представляют собой «поворот влево» или ориентацию против часовой стрелки, в противном случае «поворот вправо» или ориентацию по часовой стрелке (для пронумерованных точек против часовой стрелки).

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

Временная сложность

Сортировка точек имеет временную сложность O( n log n ). Хотя может показаться, что временная сложность цикла равна O( n ² ), поскольку для каждой точки он возвращается, чтобы проверить, совершила ли какая-либо из предыдущих точек «поворот направо», на самом деле это O( n ), поскольку в некотором смысле каждая точка рассматривается не более двух раз. Каждая точка может появиться только один раз как точка. $(x_{2},y_{2})$ в «левом повороте» (потому что алгоритм переходит к следующей точке $(x_{3},y_{3})$ после этого), и как точка $(x_{2},y_{2})$ в «правом повороте» (потому что точка $(x_{2},y_{2})$ удаляется). Таким образом, общая временная сложность равна O( n log n ), поскольку время сортировки доминирует над временем фактического вычисления выпуклой оболочки.

Псевдокод

В приведенном ниже псевдокоде используется функция ccw: ccw > 0, если три точки поворачиваются против часовой стрелки, ccw < 0, если по часовой стрелке, и ccw = 0, если коллинеарно. (В реальных приложениях, если координаты представляют собой произвольные действительные числа, функция требует точного сравнения чисел с плавающей запятой, и нужно остерегаться числовых особенностей для «почти» коллинеарных точек.)

Затем сохраните результат в stack.

let points be the list of points
let stack = empty_stack()

find the lowest y-coordinate and leftmost point, called P0
sort points by polar angle with P0, if several points have the same polar angle then only keep the farthest

for point in points:
    # pop the last point from the stack if we turn clockwise to reach this point
    while count stack > 1 and ccw(next_to_top(stack), top(stack), point) <= 0:
        pop stack
    push point to stack
end

Теперь стек содержит выпуклую оболочку, точки которой ориентированы против часовой стрелки, а P0 — первая точка.

Здесь, next_to_top() — это функция для возврата элемента на одну запись ниже вершины стека, без изменения стека, и аналогично: top() для возврата самого верхнего элемента.

Этот псевдокод адаптирован из Введения в алгоритмы .

Примечания

Та же основная идея работает и в том случае, если входные данные сортируются по координате X, а не по углу, и оболочка вычисляется в два этапа, создавая верхнюю и нижнюю части оболочки соответственно. Эту модификацию разработал А.М. Андрей. Он имеет те же основные свойства, что и сканирование Грэма.

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

Метод стека, используемый при сканировании Грэма, очень похож на метод для задачи всех ближайших меньших значений , и параллельные алгоритмы для всех ближайших меньших значений также могут использоваться (например, сканирование Грэма) для эффективного вычисления выпуклых оболочек отсортированных последовательностей точек.

устойчивость

Численная устойчивость — это проблема, с которой приходится иметь дело в алгоритмах, использующих компьютерную арифметику с плавающей запятой конечной точности . В статье 2004 года проанализирована простая пошаговая стратегия, которую можно использовать, в частности, для реализации сканирования Грэма. Заявленная цель статьи заключалась не в конкретном анализе алгоритма, а в том, чтобы предоставить хрестоматийный пример того, что и как может потерпеть неудачу из-за вычислений с плавающей запятой в вычислительной геометрии . Позже Д. Цзян и Н. Ф. Стюарт. подробно остановился на этом вопросе и с помощью обратного анализа ошибок сделал два основных вывода. Во-первых, выпуклая оболочка — это хорошо обусловленная задача, и поэтому можно ожидать появления алгоритмов, дающих ответ с разумной погрешностью. Во-вторых, они демонстрируют, что модификация сканирования Грэма, которую они называют Грэмом-Фортуном (включающая идеи Стивена Форчуна для числовой стабильности ) преодолевает проблемы конечной точности и неточных данных «насколько это возможно».

См. также

• Алгоритмы выпуклой оболочки

Дальнейшее чтение

• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «33.3: Нахождение выпуклой оболочки». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 949–955. ISBN  0-262-03293-7 .