Cтраница 2
Полярная система координат задается выбором точки О ( полюса), луча О А, исходящего из точки О ( полярной оси), и масштаба для измерения длин. Полярный угол считают положительным, если он отсчитывается от полярной оси в направлении против движения часовой стрелки, и отрицательным - в противном случае. Для полюса О значение полярного угла не определено. Любой другой точке плоскости ( е 0) соответствует единственная пара полярных координат и обратно: по заданной паре полярных координат можно указать единственную соответствующую ей точку плоскости. [16]
Трудоемкость такого упорядочения оценивается как O ( nlnn) арифметических операций. Тогда последовательные вершины выпуклой оболочки располагаются в порядке, соответствующем возрастанию значений полярного угла относительно любой внутренней точки. Просмотр начинается с точки с минимальным значением ординаты. Точка является внутренней точкой оболочки, если она есть внутренняя точка треугольника Орд, где р и q - последовательные вершины выпуклой оболочки, 0 - начало координат. [17]