Алгоритм построения выпуклой оболочки методом сканирования Грэхема

Введение

Алгоритм вычисления выпуклых оболочек для набора точек

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

Алгоритм

Первый шаг в этом алгоритме — найти точку с самой низкой координатой y. Если наименьшая координата y присутствует более чем в одной точке набора, следует выбрать точку с наименьшей координатой x среди кандидатов. Назовем эту точку P. Этот шаг занимает O(n), где n — количество рассматриваемых точек. Далее набор точек необходимо отсортировать в порядке возрастания угла, который они и точка P образуют с осью x. Для этого подойдет любой алгоритм сортировки общего назначения, например, heapsort (который имеет сложность O(n log n)). Сортировка по углу не требует вычисления самого угла. Можно использовать любую монотонную функцию угла в заданном интервале. Косинус легко вычисляется с помощью скалярного произведения, или можно использовать наклон прямой. Если важна числовая точность, функция сравнения, используемая алгоритмом сортировки, может использовать знак векторного произведения для определения относительных углов. Если несколько точек имеют одинаковый угол, можно либо упорядочить их по возрастанию расстояния (для упрощения вычислений вместо евклидова расстояния можно использовать расстояние Манхэттена или Чебышева, поскольку точки лежат на одном луче), либо удалить все точки, кроме самой удаленной. Алгоритм последовательно рассматривает каждую точку в отсортированном массиве. Для каждой точки сначала определяется, является ли переход от двух непосредственно предшествующих точек левым или правым поворотом. Если переход представляет собой правый поворот, то предпоследняя точка не является частью выпуклой оболочки и лежит «внутри» нее. Затем то же определение применяется к набору, состоящему из последней точки и двух точек, непосредственно предшествующих точке, обнаруженной внутри оболочки, и повторяется до тех пор, пока не будет обнаружен набор, представляющий собой «левый поворот». В этот момент алгоритм переходит к следующей точке в отсортированном массиве, исключив из рассмотрения все точки, которые были обнаружены внутри оболочки; повторное рассмотрение этих точек не требуется. (Если на каком-либо этапе три точки оказываются коллинеарными, можно либо отбросить их, либо сообщить о них, поскольку в некоторых приложениях требуется найти все точки на границе выпуклой оболочки.) Опять же, определение того, представляют ли три точки «левый поворот» или «правый поворот», не требует вычисления фактического угла между двумя отрезками прямой и может быть выполнено только с помощью простых арифметических операций. Для трех точек A, B и C вычислите z-координату векторного произведения двух векторов AB и AC, которая задается выражением: (By - Ay) * (Cx - Bx) - (Bx - Ax) * (Cy - By). Если результат равен 0, точки коллинеарны; если он положителен, то три точки образуют «левый поворот» или ориентированы против часовой стрелки, иначе — «правый поворот» или ориентированы по часовой стрелке (для точек, пронумерованных против часовой стрелки). Этот процесс в конечном итоге вернется к точке, с которой он начался, после чего алгоритм завершится, и стек будет содержать точки на выпуклой оболочке в порядке против часовой стрелки.

The first step in this algorithm is to find the point with the lowest y coordinate. If the lowest y coordinate exists in more than one point in the set, the point with the lowest x coordinate out of the candidates should be chosen. Call this point P. This step takes O(n), where n is the number of points in question. Next, the set of points must be sorted in increasing order of the angle they and the point P make with the x axis. Any general purpose sorting algorithm is appropriate for this, for example heapsort (which is O(n log n)). Sorting in order of angle does not require computing the angle. It is possible to use any function of the angle which is monotonic in the interval The cosine is easily computed using the dot product, or the slope of the line may be used. If numeric precision is at stake, the comparison function used by the sorting algorithm can use the sign of the cross product to determine relative angles. If several points are of the same angle, either break ties by increasing distance (Manhattan or Chebyshev distance may be used instead of Euclidean for easier computation, since the points lie on the same ray), or delete all but the furthest point. The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is first determined whether traveling from the two points immediately preceding this point constitutes making a left turn or a right turn. If a right turn, the second to last point is not part of the convex hull, and lies 'inside' it. The same determination is then made for the set of the latest point and the two points that immediately precede the point found to have been inside the hull, and is repeated until a "left turn" set is encountered, at which point the algorithm moves on to the next point in the set of points in the sorted array minus any points that were found to be inside the hull; there is no need to consider these points again. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.) Again, determining whether three points constitute a "left turn" or a "right turn" does not require computing the actual angle between the two line segments, and can actually be achieved with simple arithmetic only. For three points , and , compute the z coordinate of the cross product of the two vectors and , which is given by the expression If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn" or counter clockwise orientation, otherwise a "right turn" or clockwise orientation (for counter clockwise numbered points). This process will eventually return to the point at which it started, at which point the algorithm is completed and the stack now contains the points on the convex hull in counterclockwise order.

Численная прочность

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