обхода против часовой
обхода против часовой стрелки на предмет того, образуют они или нет угол, больший или равный ?. Если угол q1q2q3 больше или равен ?, то считают, что q1q2q3 образуют «правый поворот», иначе они образуют «левый поворот».
Алгоритм.
• Найти внутреннюю точку t.
• Используя t как начало координат, отсортировать точки множества S по неубыванию в соответствии с полярным углом и расстоянием от t.
• Выполнить обход точек, исключая точки типа q2 (образующие «правый поворот»).
Известно, что сортировка N элементов может быть выполнена за время O(NlogN) (методы Хоара, слияния). Это самая трудоемкая (по времени) часть алгоритма. Обход может быть выполнен за время, пропорциональное N. Значит, выпуклую оболочку можно построить за время, пропорциональное NlogN.
При организации данных (отсортированных точек) в виде двухсвязного списка с указателями СЛЕД и ПРЕД и указателем НАЧАЛО на первую точку логика обхода точек имеет вид:
Begin
v:=НАЧАЛО;w:=ПРЕД[v];f:=false;
while (СЛЕД[v]<>НАЧАЛО)or
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
