Вычислительная геометрия — это математическая область, которая включает в себя разработку, анализ и реализацию эффективных алгоритмов для решения геометрических задач ввода и вывода. Иногда она используется для обозначения распознавания образов и описания алгоритмов твердотельного моделирования, используемых для манипулирования кривыми и поверхностями.
Краткая история вычислительной геометрии
Эта область была создана в конце 1970-х годов и быстро развивалась в течение 1990-х годов до сегодняшнего дня. С исторической точки зрения геометрия, основанная на вычислениях, развивалась благодаря изучению алгоритмов сортировки и поиска, используемых в одномерных пространствах для решения задач, связанных с многомерными входными данными. Ее разработка также способствовала пониманию вычислительных теорий графов, применяемых к естественным геометрическим установкам. Вначале эта область в основном была сосредоточена на проблемах в двумерном пространстве, а иногда и в трехмерном пространстве.
Когда математические задачи рассматриваются в многомерных пространствах, большинство практиков предполагают, что размерность пространства является небольшой константой. Однако эта область была создана исследователями, которые сосредоточились на дискретных алгоритмах, а не на численном анализе. Они также сосредоточились на природе геометрических задач вместо традиционных непрерывных задач. Это в основном относится к плоским и прямым объектам, таким как плоскости, линии, многоугольники и отрезки линий, но иногда и к изогнутым объектам, таким как круги. Однако вычислительная геометрия избегает фокусировки на задачах твердотельного моделирования со сложными кривыми и поверхностями.
Вычислительная геометрия как инструмент для решения проблем
Эта уникальная область может похвастаться замечательной историей решения интересных проблем. В 1980-х годах вычислительная геометрия внесла много полезных методов для разработки эффективных геометрических алгоритмов, таких как динамическое программирование и модель «разделяй и властвуй». За это время были созданы дополнительные новые методы, такие как дробное каскадирование, развертка по плоскости, дуальные преобразования и рандомизированные инкрементные построения. В качестве дополнительного преимущества исследователи смогли создать технические рамки для разработки эффективных геометрических алгоритмов.
В течение 1990-х годов борьба между теориями и практикой разработки геометрических алгоритмов продолжалась, поскольку исследователи пытались реализовать алгоритмы, которые были загружены сложными формулами и необходимыми структурами данных. Успешные реализации по-прежнему зависели от чувствительных геометрических вырождений, которые иногда приводили к ложным выводам или неожиданным завершениям. Большая часть недавних работ в этой области была посвящена тому, чтобы сделать теоретические выводы более доступными для практиков. Это было достигнуто путем решения геометрических вырождений, упрощения существующих алгоритмов и создания геометрических библиотек.
Ограничения вычислительной геометрии
Существует несколько веских причин, по которым геометрия, основанная на вычислениях, никогда не сможет полностью удовлетворить потребности практиков и их областей применения. Например, отстраненный характер вычислительной геометрии не всегда может справиться с непрерывным явлением. Многие природные объекты, такие как дорожные сети и географические информационные системы, могут быть успешно дискретизированы в коллекции линейных сегментов. Поскольку геометрия, основанная на вычислениях, в основном имеет дело с плоскими и прямыми объектами, она с трудом удовлетворяет потребности инженеров и дизайнеров, занимающихся робототехникой, гидродинамикой и моделированием твердого тела.
Хорошей новостью является то, что технология позволяет вычислительным геометрам иметь дело с искривленными объектами с многоугольниками или многогранниками. На самом деле именно поэтому геометрия, основанная на вычислениях, становится все более популярной, потому что теперь она требует меньше аналитической и дифференциальной геометрии и больше компьютерных и технических навыков. Область в основном сосредоточена на двумерных задачах, которые легко визуализировать и понять, но это ограничивает возможности решения самых сложных трехмерных прикладных задач и пространств более высокой размерности.
Заключение
Существует множество областей информатики, которые занимаются проблемами вычислительной геометрии. К ним относятся компьютерное зрение, графика, робототехника, обработка изображений и автоматизированное проектирование и производство.