Англ.: Geometric(al) algorithms)

Способы решения геометрических задач. В компьютерной графике широко используются такие Г.а. как рисования отрезка прямой Брозенхама (Bresenham s algorithm for incremental of segment) - пошаговый алгоритм рисования отрезка прямой на растровом устройстве отображения, например, на экране монитора. Прямая, построенная по этому алгоритму, представляет собой некоторое множество пикселов, через которые проходит отрезок математической прямой. Алгоритм определяет последовательность выбора точек растра; рисования дуги окружности Брозенхама (Bresenham`s algorithm for incremental of circular arcs) - пошаговый алгоритм рисования дуги окружности на растровом устройстве отображения. Окружность, построенная по этому алгоритму представляет собой некоторое множество закрашенных пикселов, через которые проходит математическая окружность. Алгоритм определяет последовательность выбора точек растра; триангуляции (triangulation) - Г.а. планарного разбиения, все конечные грани которого являются треугольниками. Среди алгоритмов триангуляции выделяют геометрические алгоритмы жадной триангуляции (greedy triangulation geometric(al) algorithm) - в которых результаты первоначальной триангуляции не уточняются. В жадных алгоритмах на каждом шаге делается все возможное, чтобы сразу подойти как можно ближе к решению, т.е. это методы, в которых возможные в перспективе преимущества приносятся в жертву немедленному приближению к цели. Геометрические алгоритмы локализации точки (point-location, point-in-polygon) решает задачу поиска области, содержащей запрошенную точку; геометрические алгоритмы отсечения (clipping geometric(al) algorithm), т.е. построения пересечения исходного геометрического объекта или совокупности объектов с заданной областью. Как правило в качестве области выбирается прямоугольник. Одной из основных частей алгоритма отсечения является геометрические алгоритмы отсечения отрезка (segment clipping geometric(al) algorithm). Среди Г.а. принято выделять динамические геометрические алгоритмы (dynamic geometric(al) algorithm), для которых допустима динамическая корректировка информации в процессе их выполнения и статические геометрические алгоритмы (static geometric(al) algorithm), для которых вся необходимая информация должна быть полностью известна до начала их работы, а также закрытые геометрические алгоритмы (off-line geometric(al) algorithm), обрабатывающие всю совокупность данных целиком и открытые геометрические алгоритмы (on-line geometric(al) algorithm), обрабатывающие данные по мере их поступления. Для обоснования выбора Г.а. используют их свойства, среди которых наиболее значимым является сложность (complexity), способы оценки которой разрабатываются в вычислительной геометрии. Обычно это количество элементарных операций необходимых для решения поставленной задачи. Например, сколько элементарных вычислительных операций необходимо выполнить, чтобы определить все точки пересечения всех отрезков нарисованных на плоскости. Имеются разновидности такого рода оценок: сложность для худшего случая (worst-case), сложность в среднем (average case).