Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Алгоритм вычисления выпуклых оболочек для набора точек
Algorithm for computing convex hulls in a set of points
В вычислительной геометрии алгоритм обхода по контуру (или метод "заворачивания подарка") — это алгоритм для вычисления выпуклой оболочки заданного набора точек.
In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.
Плоскость
В двухмерном случае алгоритм также известен как алгоритм Джарвиса, названный в честь Р. А. Джарвиса, опубликовавшего его в 1973 году; его временная сложность составляет O(nh), где n — количество точек, а h — количество точек на выпуклой оболочке. Его практическая производительность по сравнению с другими алгоритмами построения выпуклой оболочки благоприятна, когда n мало или ожидается, что h будет очень малым по отношению к n. В общем случае алгоритм уступает многим другим (см. Алгоритмы построения выпуклой оболочки).
In the two dimensional case the algorithm is also known as Jarvis march, after R. A. Jarvis, who published it in 1973; it has O(nh) time complexity, where n is the number of points and h is the number of points on the convex hull. Its real life performance compared with other convex hull algorithms is favorable when n is small or h is expected to be very small with respect to n. In general cases, the algorithm is outperformed by many others ( See Convex hull algorithms).
Алгоритм
Для упрощения описание ниже предполагает, что точки находятся в общем положении, то есть никакие три точки не лежат на одной прямой. Алгоритм может быть легко модифицирован для обработки коллинеарности, включая выбор, сообщать ли только об экстремальных точках (вершинах выпуклой оболочки) или обо всех точках, лежащих на выпуклой оболочке. Кроме того, полная реализация должна учитывать вырожденные случаи, когда выпуклая оболочка содержит только 1 или 2 вершины, а также вопросы ограниченной арифметической точности, как при компьютерных вычислениях, так и во входных данных. Алгоритм "обёртывания подарком" начинается с i=0 и точки p0, заведомо лежащей на выпуклой оболочке, например, самой левой точки, и выбирает точку pi+1 таким образом, чтобы все остальные точки лежали справа от прямой pi pi+1. Эту точку можно найти за время O(n), сравнивая полярные углы всех точек относительно точки pi, принятой за центр полярной системы координат. Увеличивая i на 1 и повторяя процесс до тех пор, пока не будет достигнута точка ph=p0, получим выпуклую оболочку за h шагов. В двух измерениях алгоритм "обёртывания подарком" аналогичен процессу наматывания нитки (или обёрточной бумаги) вокруг набора точек. Этот подход можно обобщить на более высокие размерности.
For the sake of simplicity, the description below assumes that the points are in general position, i. e., no three points are collinear. The algorithm may be easily modified to deal with collinearity, including the choice whether it should report only extreme points (vertices of the convex hull) or all points that lie on the convex hull. Also, the complete implementation must deal with degenerate cases when the convex hull has only 1 or 2 vertices, as well as with the issues of limited arithmetic precision, both of computer computations and input data. The gift wrapping algorithm begins with i=0 and a point p0 known to be on the convex hull, e. g., the leftmost point, and selects the point pi+1 such that all points are to the right of the line pi pi+1. This point may be found in O(n) time by comparing polar angles of all points with respect to point pi taken for the center of polar coordinates. Letting i=i+1, and repeating with until one reaches ph=p0 again yields the convex hull in h steps. In two dimensions, the gift wrapping algorithm is similar to the process of winding a string (or wrapping paper) around the set of points. The approach can be extended to higher dimensions.
Сложность
Внутренняя петля проверяет каждую точку в наборе S, а внешняя петля повторяется для каждой точки на оболочке. Следовательно, общее время работы определяется размером выходных данных, поэтому алгоритм «марш Джарвиса» является алгоритмом, чувствительным к объему выходных данных. Однако, поскольку время работы зависит линейно от числа вершин оболочки, он быстрее, чем алгоритмы, такие как сканирование Грэма, только когда число h вершин оболочки меньше log n. Алгоритм Чана, другой алгоритм построения выпуклой оболочки, сочетает в себе логарифмическую зависимость сканирования Грэма с чувствительностью к объему выходных данных алгоритма «заворачивания подарков», достигая асимптотического времени работы, которое превосходит как сканирование Грэма, так и «заворачивание подарков».
The inner loop checks every point in the set S, and the outer loop repeats for each point on the hull. Hence the total run time is The run time depends on the size of the output, so Jarvis's march is an output sensitive algorithm. However, because the running time depends linearly on the number of hull vertices, it is only faster than algorithms such as Graham scan when the number h of hull vertices is smaller than log n. Chan's algorithm, another convex hull algorithm, combines the logarithmic dependence of Graham scan with the output sensitivity of the gift wrapping algorithm, achieving an asymptotic running time that improves on both Graham scan and gift wrapping.