Вычислительная геометрия

Cтраница 3

Пересечение выпуклых много - СОСТОИТ B бхОДе границы угольников. Р ребро за ребром, в. [31]

Нужно ли повторять, что уровень знаний в этой области при росте числа измерений отражает картину, знакомую сегодня во всей вычислительной геометрии. [32]

Поэтому детальный обзор материала этих превосходных книг, с которыми читатель, наверное, основательно знаком, останется за рамками нашей работы. Однако целесообразно - по крайней мере с точки зрения терминологии - привести краткий обзор основных компонент языка, который будет применяться для описания вычислительной геометрии. [33]

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

Этот краткий обзор показывает, что методы вычислительной геометрии основаны на достижениях целого ряда областей математики, которые обычно изучаются как самостоятельные математические дисциплины. Поэтому в первых четырех главах настоящей книги мы стремились связать воедино те разделы классической аналитической, алгебраической и дифференциальной геометрии, которые имеют прямое отношение к нашей основной теме, и дать краткий обзор векторной алгебры, ставшей общепринятым языком вычислительной геометрии. Материал этих глав поможет объединить и, мы надеемся, прояснить геометрические аспекты различных методов, применяемых при подгонке и проектировании кривых и поверхностей, которые рассматриваются в гл. [35]

В вычислительной геометрии имеется ряд открытых проблем, большинство из которых были упомянуты в статье. Концепция динамической вычислительной геометрии [15, 275], когда рассматриваемые объекты перемещаются с течением ( непрерывным изменением) времени, например, является одним из направлений исследований, заслуживающих дальнейшего изучения. В настоящее время главное внимание в вычислительной геометрии уделяется получению асимптотических оценок поведения алгоритмов. Более чем необходимо проводить сравнения временных характеристик различных алгоритмов, для которых имеется лишь асимптотическая оценка сложности, представленная с помощью 0-большое нотации. Эти сравнения должны проводиться для таких значений размеров исходных данных, какие встречаются в практических задачах. [36]

Так ли необходимо проверять все треугольники, определяемые множеством из N точек, чтобы узнать, лежит ли некоторая точка в каком-либо из них. Грэхем в одной из первых работ, специально посвященных вопросу разработки эффективных геометрических алгоритмов [ Graham ( 1972) ], показал, что, выполнив предварительно сортировку точек, крайние точки можно найти за линейное время. Использованный им метод стал очень мощным средством в области вычислительной геометрии. [37]

Задача триангуляции простого многоугольника с п вершинами состоит в выборе п - 3 непересекающихся диагоналей, разбивающих его внутренность на я - 2 треугольника. Тем самым показывается, что задача триангуляции не такая сложная, как задача сортировки. Полученный результат позволяет улучшить алгоритмы для решения некоторых других задач вычислительной геометрии, включая проверку многоугольника на простоту. [38]

Несомненно, следует задать вопрос, является ли эта процедура, имеющая сложность 0 ( N2), наилучшим из возможных алгоритмов. Вопрос о вычислительной сложности задач такого сорта является основным в вычислительной геометрии, который мы обязаны ставить даже в случае отсутствия в нем практической надобности. [39]

Наш алгоритм основывается на методе, который мы назвали непрерывный Дейкстра. Этот метод очень напоминает оригинальный алгоритм Дейкстры нахождения кратчайшего пути, но при этом включает новые понятия о распространяющемся волновом фронте и дискретных событиях. В некотором смысле получается сочетание алгоритма Дейкстры и принципа заметания, используемого в вычислительной геометрии. [40]

Основу программного обеспечения подсистемы хранения информации составляет ППП БАЗАД, разработанный в ВЦ СО АН СССР. Этот пакет отвечает большинству из перечисленных ранее требований к БД КИПР-ЕС и ориентирован в первую очередь на решение задач машинной графики и вычислительной геометрии. [41]

Инженерная графика относится к базовым общепнженерпым дисциплинам, хорошее освоение которой - необходимое условие углубленного овладения фундаментальными инженерными дисциплинами: прикладной механикой, процессами и аппаратами химической технологии, общей химической технологией и др. Без знания инженерно. Курников отмечал: Без графических построений изучение химических равновесных систем, особенно при большом числе компонентов, становится невозможным... Инженерная графика требуется при разработке и использовании систем автоматизированного проектирования, которое включает формирование библиотек графических образов, иллюстрации к разработкам и виде графиков, диаграмм, решение прикладных задач средствами инженерной графики и вычислительной геометрии, углубленное изучение инженерных графических задач. Знание предмета и методов инженерной графики способствует лучшему пониманию механизмов реакций, изучаемых и в биотехнологии, и наиохпмнп. [42]

Перспективы и методология вычислительной геометрии проясняется, как мы надеемся, при детальном изучении конкретных задач, представленных в данной книге. Одно из основных свойств этой дисциплины заключается в осознании того, что классические характеристики геометрических объектов часто не влияют на проектирование эффективных алгоритмов. Чтобы преодолеть этот недостаток, необходимо найти полезные понятия и установить их свойства, способствующие эффективности вычислений. Короче говоря, вычислительная геометрия должна преобразовать - там, где это необходимо, - классическую дисциплину в ее вычислительную форму. [43]

Прошло 3 года с момента выхода книги на английском языке, и теперь я с удовольствием приветствую ее перевод на русский язык. Ряд задач, которые оставались нерешенными почти десятилетие, были либо полностью решены, либо на пути к их решению были получены блестящие результаты. Сегодня исследования в вычислительной геометрии продолжаются так же энергично, как и прежде. [44]

При этом используются как параллельные аксонометрические и ортогональные проекции, так и центральные проекции ( перспективы) с одним или двумя центрами проецирования. Математическое описание технических объектов участвует в создании программ генерации изображений. Для создания реалистических изображений учитывают оптические законы прохождения, отражения и рассеивания света и передачи цвета. Параметры геометрической и физической информации в ЭВМ обрабатываются в основном методами вычислительной математики, в том числе - вычислительной геометрии. [45]

Страницы: 1 2 3 4