Сканирование Грэма - это метод поиска выпуклой оболочки конечного набора точек на плоскости с временной сложностью O ( n log n ). Он назван в честь Рональда Грэма , который опубликовал оригинальный алгоритм в 1972 году. [1] Алгоритм находит все вершины выпуклой оболочки, упорядоченные вдоль ее границы. Он использует стек для эффективного обнаружения и удаления вогнутостей на границе.
Алгоритм
Первый шаг в этом алгоритме - найти точку с наименьшей y-координатой. Если самая низкая координата y существует более чем в одной точке в наборе, следует выбрать точку с самой низкой координатой x из возможных. Назовем эту точку P . Этот шаг занимает O ( n ), где n - количество рассматриваемых точек.
Затем набор точек необходимо отсортировать в порядке возрастания угла, который они и точка P образуют с осью x. Для этого подходит любой универсальный алгоритм сортировки , например heapsort (который равен O ( n log n )).
Сортировка по углу не требует вычисления угла. Можно использовать любую функцию угла, которая монотонна в интервале . Косинус легко вычисляется с помощью скалярного произведения или может использоваться наклон линии. Если на карту поставлена числовая точность, функция сравнения, используемая алгоритмом сортировки, может использовать знак перекрестного произведения для определения относительных углов.
Алгоритм продолжается путем последовательного рассмотрения каждой точки в отсортированном массиве. Для каждой точки сначала определяется, составляет ли путешествие из двух точек, непосредственно предшествующих этой точке, поворот налево или направо. При повороте направо предпоследняя точка не является частью выпуклой оболочки, а лежит «внутри» ее. Затем такое же определение выполняется для набора последней точки и двух точек, которые непосредственно предшествуют точке, находящейся внутри корпуса, и повторяется до тех пор, пока не встретится набор «левый поворот», после чего алгоритм переходит к к следующей точке в наборе точек отсортированного массива за вычетом всех точек, которые были обнаружены внутри корпуса; нет необходимости снова рассматривать эти моменты. (Если на каком-либо этапе три точки коллинеарны, можно либо отбросить, либо сообщить об этом, поскольку в некоторых приложениях требуется найти все точки на границе выпуклой оболочки.)
Опять же, определение того, составляют ли три точки «левый поворот» или «правый поворот», не требует вычисления фактического угла между двумя линейными сегментами и фактически может быть достигнуто только с помощью простой арифметики. По трем очкам, а также , вычислить z- координату перекрестного произведения двух векторов а также , что дается выражением . Если результат равен 0, точки лежат на одной прямой; если он положительный, три точки образуют «левый поворот» или ориентацию против часовой стрелки, в противном случае - «правый поворот» или ориентацию по часовой стрелке (для точек, пронумерованных против часовой стрелки).
Этот процесс в конечном итоге вернется к точке, в которой он начался, на этом этапе алгоритм завершается, и теперь стек содержит точки на выпуклой оболочке в порядке против часовой стрелки.
Сложность времени
Сортировка точек имеет временную сложность O ( n log n ). Хотя может показаться, что временная сложность цикла составляет O ( n 2 ), потому что для каждой точки он возвращается, чтобы проверить, совершает ли какая-либо из предыдущих точек «поворот вправо», на самом деле это O ( n ), потому что каждая точка В некотором смысле точка считается не более двух раз. Каждая точка может появиться только один раз как точка в "левом повороте" (потому что алгоритм переходит к следующей точке после этого), и как точка в "поворот направо" (потому что точка устранен). Таким образом, общая временная сложность составляет O ( n log n ), поскольку время сортировки преобладает над временем фактического вычисления выпуклой оболочки.
Псевдокод
В приведенном ниже коде используется функция ccw: ccw> 0, если три точки совершают поворот против часовой стрелки, по часовой стрелке, если ccw <0, и коллинеарны, если ccw = 0. (В реальных приложениях, если координаты являются произвольными действительными числами, функция требует точное сравнение чисел с плавающей запятой, и нужно остерегаться числовых особенностей для "почти" коллинеарных точек.)
Затем пусть результат будет сохранен в stack
.
пусть точки будут списком точек let stack = empty_stack ()Найдите самую низкую координату y и крайнюю левую точку, называемую P0, отсортируйте точки по полярному углу с P0, если несколько точек имеют одинаковый полярный угол, тогда оставьте только самую дальнююдля точки в баллах: # вытаскиваем последнюю точку из стека, если мы поворачиваем по часовой стрелке, чтобы достичь этой точки в то время как счетчик стека> 1 и CCW (next_to_top (стек), верхний (стек), точка) <= 0: поп стек толчок точка для стека конца
Теперь стопка содержит выпуклую оболочку, точки которой ориентированы против часовой стрелки, а P0 - первая точка.
Вот next_to_top()
функция для возврата элемента на одну запись ниже вершины стека, без изменения стека, и аналогично top()
для возврата самого верхнего элемента.
Этот псевдокод адаптирован из Введение в алгоритмы .
Заметки
Та же основная идея работает также, если входные данные отсортированы по координате x, а не по углу, и корпус вычисляется в два этапа, создавая соответственно верхнюю и нижнюю части корпуса. Эта модификация была разработана AM Andrew [2] и известна как алгоритм монотонной цепи Эндрю . Он имеет те же основные свойства, что и скан Грэма. [3]
Техника стека, используемая в сканировании Грэма, очень похожа на метод для задачи всех ближайших меньших значений , и параллельные алгоритмы для всех ближайших меньших значений также могут использоваться (например, сканирование Грэма) для эффективного вычисления выпуклой оболочки отсортированных последовательностей точек. [4]
Числовая надежность
Числовая устойчивость - это проблема, с которой приходится иметь дело в алгоритмах, использующих компьютерную арифметику с плавающей запятой конечной точности . В статье 2004 года проанализирована простая инкрементная стратегия, которую можно использовать, в частности, для реализации сканирования Грэма. [5] Заявленная цель статьи заключалась не в конкретном анализе алгоритма, а в предоставлении учебного примера того, что и как может дать сбой из-за вычислений с плавающей запятой в вычислительной геометрии . [5] Позже Д. Цзян и Н. Ф. Стюарт [6] подробно остановились на этом и, используя обратный анализ ошибок, сделали два основных вывода. Во-первых, выпуклая оболочка - это хорошо обусловленная проблема, и поэтому можно ожидать алгоритмов, которые дадут ответ в пределах разумной погрешности. Во-вторых, они демонстрируют, что модификация сканирования Грэма, которую они называют Graham-Fortune (включающая идеи Стивена Фортуна о числовой стабильности [7] ), действительно преодолевает проблемы конечной точности и неточных данных «в той мере, в какой это возможно». .
Смотрите также
Рекомендации
- Перейти ↑ Graham, RL (1972). «Эффективный алгоритм для определения выпуклой оболочки конечного плоского множества» (PDF) . Письма об обработке информации . 1 (4): 132–133. DOI : 10.1016 / 0020-0190 (72) 90045-2 .
- ^ Эндрю AM (1979). «Еще один эффективный алгоритм для выпуклых оболочек в двух измерениях». Письма об обработке информации . 9 (5): 216–219. DOI : 10.1016 / 0020-0190 (79) 90072-3 .
- ^ Де Берг, Марк; Чеонг, Отфрид; Ван Кревельд, Марк; Овермарс, Марк (2008). Алгоритмы и приложения вычислительной геометрии . Берлин: Springer . стр. 2 -14. DOI : 10.1007 / 978-3-540-77974-2 . ISBN 978-3-540-77973-5.
- ^ Беркман, Омер; Шибер, Барух; Вишкин, Узи (1993). «Оптимальные двойные логарифмические параллельные алгоритмы, основанные на нахождении всех ближайших меньших значений». Журнал алгоритмов . 14 (3): 344–370. CiteSeerX 10.1.1.55.5669 . DOI : 10.1006 / jagm.1993.1018 ..
- ^ а б Кеттнер, Лутц; Мельхорн, Курт; Пион, Сильвен; Ширра, Стефан; Яп, Чи (2008). «Классные примеры задач устойчивости в геометрических вычислениях» (PDF) . Вычислительная геометрия . 40 (1): 61–78. DOI : 10.1016 / j.comgeo.2007.06.003 . (Более ранняя версия была представлена в 2004 году на ESA'2004)
- ^ Д. Цзян и Н. Ф. Стюарт, Обратный анализ ошибок в вычислительной геометрии. Архивировано 9 августа 2017 г. в Wayback Machine , Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series Lecture Notes in Computer Science , pp 50-59
- ^ Форчун, С. Стабильное поддержание триангуляции точек в двух измерениях. Труды 30-го ежегодного симпозиума IEEE по основам информатики Vol. 30, 494-499, 1989.
дальнейшее чтение
- Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990]. «33.3: Нахождение выпуклой оболочки». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 949–955. ISBN 0-262-03293-7.