Разработка геометрических алгоритмов: различия между версиями

Преобразование теоретического геометрического алгоритма в эффективную компьютерную программу сопряжено с немалыми трудностями. Преодоление этих трудностей является задачей разработчиков геометрических алгоритмов, которые в более широком смысле занимаются проектированием и реализацией сертифицированных и эффективных решений алгоритмических задач, имеющих геометрическую природу. Типичными задачами этого семейства являются построение диаграмм Вороного, триангуляций, компоновки кривых и поверхностей (а именно – разбиений пространства), двух- и трехмерных поисковых структур, выпуклых оболочек и многого другого.

Прямолинейная реализация геометрических алгоритмов, описанная в учебнике, при помощи стандартной машинной арифметики, с огромной вероятностью окажется неудачной. Далее будут рассматриваться только сертифицированные решения – а именно такие решения, которые гарантированно строят точную желаемую структуру или ее хорошую аппроксимацию; такие решения нередко называются надежными.

Напротив, в реальном мире геометрические входные данные часто являются вырожденными, точность машинных вычислений ограничена, а стоимость операций на небольшом числе простых геометрических объектов при помощи одного и того же алгоритма (исчисляемая по времени выполнения) может различаться в сотни раз и более того (при ориентации на сертифицированные результаты). Обычной внимательной реализации алгоритма может оказаться недостаточно, и часто приходится прибегать к редизайну.