Что такое компьютерная геометрия
Компьютерная геометрия — Вычислительная геометрия раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного… … Википедия
Компьютерная графика — (также машинная графика) область деятельности, в которой компьютеры используются как инструмент для синтеза (создания) изображений, так и для обработки визуальной информации, полученной из реального мира. Также компьютерной графикой… … Википедия
Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их… … Википедия
N-мерная евклидова геометрия — N мерная евклидова геометрия обобщение евклидовой геометрии на пространство большего числа измерений. Хотя физическое пространство является трёхмерным[1], и человеческие органы чувств рассчитаны на восприятие трёх измерений[2], N мерная… … Википедия
Периметр (компьютерная игра) — Периметр: Геометрия Войны[1] Разработчик К Д ЛАБ … Википедия
Фоменко, Анатолий Тимофеевич — В Википедии есть статьи о других людях с такой фамилией, см. Фоменко. Анатолий Тимофеевич Фоменко Дата рождения: 13 марта 1945(1945 03 13) (67 лет) Место рождения: Сталино, УССР, СССР Страна … Википедия
Фоменко, Анатолий — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко А. — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко А. Т. — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко А.Т. — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко Анатолий Тимофеевич — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Немного истории
Я являюсь студентом уже 4 курса математического факультета, и до того как я начал заниматься программированием, я считал себя математиком на 100 процентов.
В конце первого курса мой преподаватель по информатике, который занимается олимпиадным программированием, обратил на меня внимание. Им как раз не хватало одного математика в команду. Так потихоньку меня начали приучать к олимпиадному программированию. Скажу честно, для меня это было очень сложно: для человека, который узнал слово Delphi на первом курсе. Однако мой преподаватель оказался очень грамотным специалистом и нашел хороший подход ко мне. Он начал давать мне математические задачи, который я сначала решал чисто математически, а уже потом писал код (с грехом пополам).
Мне очень нравится подход моего преподавателя: «разберись с этой темой, а потом расскажи нам, да так чтоб мы все поняли».
Итак, первой на самом деле важной задачей, с которой мне поручили разобраться, было именно вычислительная геометрия, необходимо было разобраться в типичных задач этого раздела информатики. И я решил подойти к этой задаче со всей ответственностью.
Я помню, как долго мучился с этими задачами, чтобы они прошли все тесты на сайте informatics.mccme. Зато теперь я очень рад, что прошел через все испытания и знаю, что же такое задачи вычислительной геометрии.
Вступление
«Вычислительная геометрия – это раздел информатики, изучающий алгоритмы решения геометрических задач. Такие задачи возникают в компьютерной графике, проектировании интегральных схем, технических устройств и др. Исходными данными в такого рода задачах могут быть множество точек, набор отрезков, многоугольники и т.п. Результатом может быть либо ответ на какой-то вопрос, либо какой-то геометрический объект».
Поскольку статья является достаточно большой я решил разбить ее на две части: первая часть посвящена многоугольникам, вторая – взаимному расположению различных геометрических объектов.
Немного теории о векторах
Отрезок, для которого указано, какой из его концов считается началом, а какой — концом, называется вектором. Любая точка пространства также может рассматриваться как вектор. Такой вектор называется нулевым. Начало и конец нулевого вектора совпадают, и он не имеет какого-либо определенного направления.
Длиной ненулевого вектора AB называется длина отрезка AB. Длина нулевого вектора считается равной нулю.
Два ненулевых вектора называются коллинеарными, если они лежат на одной прямой или на параллельных прямых. Если два ненулевых вектора AB и CD коллинеарны и если при этом лучи AB и CD сонаправлены, то векторы AB и CD называются сонаправленными, а если эти лучи не являются сонаправленными, то векторы AB и CD называются противоположно направленными. Нулевой вектор принято считать сонаправленным с любым вектором.
Скалярное произведение векторов
Скалярное произведение векторов — это число, равное произведению длин этих векторов на косинус угла между ними.
(a, b) = |a||b|cos∠(a, b)
Если векторы заданы своими координатами a(x1, y1), b(x2, y2) то скалярное произведение (a, b) = x1x2 + y1y2.
Косое произведение векторов
Псевдоскалярным или косым произведением векторов на плоскости называется число
[a, b] = |a||b|sinθ
где — угол вращения (против часовой стрелки) от a к b. Если хотя бы один из векторов a и b нулевой, то полагают [a, b] = 0.
Если векторы заданы своими координатами a(x1, y1), b(x2, y2) то косое произведение [a, b] = x1y2 — x2y1.
Геометрически косое произведение векторов представляет собой ориентированную площадь параллелограмма, натянутого на эти вектора.
Косое произведение векторов в задачах вычислительной геометрии занимает такое же почетное место, как рекурсии в комбинаторике. Это своего рода жемчужина вычислительной геометрии. Практически каждая задача вычислительной геометрии имеет более простое решение с помощью косового произведение вместо лобового решения.
А теперь займемся практикой
Начнем с треугольников
Задача №1
Задача очень простая, а именно: по введенным трем числам a, b, c определить существует ли треугольник с такими сторонами.
Решение
Понятно, что здесь нужно только проверить неравенство треугольника: a + b > c, a + c > b, b + c > a. Интересно, при изучении неравенства треугольника только ли у меня возник вопрос: не могут ли отрицательные числа тоже удовлетворять этим трем неравенствам? Оказывается, нет! Если мы сложим каждое неравенство, то получим a > 0, b > 0, c > 0. Поэтому неравенство треугольника является необходимым и достаточным условием существования треугольника.
Задача №2
Задача является очень похожей на предыдущую с той разницей, что треугольник задан не сторонами, а координатами вершин.
Решение
С первого взгляда решение кажется очевидным: вычислить стороны треугольника и свести задачу к предыдущей. Однако поскольку расстояние между двумя точками A(x1, y1), B(x2, y2) вычисляется по формуле √(x1-x2) 2 +(y1-y2) 2 то при извлечении корня возможна потеря точности, что плохо скажется на проверке неравенства треугольника. Оказывается, что если треугольник задан координатами своих вершин, то вычислять длины его сторон и проверять неравенство треугольника не требуется. В этом случае треугольника не существует тогда и только тогда, когда данные три точки лежат на одной прямой. А это легко проверяется через косое произведение векторов. Если оно равно нулю, то векторы коллинеарные, то есть все три точки лежат на одной прямой.
Во всех следующих задачах будем считать, что треугольник существует, поскольку процедуру проверки существования треугольника мы только что рассмотрели.
Задача №3
Треугольник задан своими сторонами. Определить тип треугольника: тупоугольный, прямоугольный или остроугольный.
Решение
Вспомним, что представляют собой каждый вид треугольника.
- Угол больше 90° – треугольник тупоугольный
- Угол меньше 90°– треугольник остроугольный
- Угол равен 90°– треугольник прямоугольный
- Если cosα > 0, то a 2 < b 2 + c 2 – треугольник остроугольный
- Если cosα = 0, то a 2 = b 2 + c 2 – треугольник прямоугольный
- Если cosα < 0, то a 2 >b 2 + c 2 – треугольник тупоугольный
Задача №4
Задача аналогична предыдущей задаче, только треугольник задан не своими сторонами, а координатами вершин.
Решение
Аналогично задаче 2 можно сказать, что эта задача полностью сводится к предыдущей задаче (так оно и есть). Однако, как и во второй задаче, решение можно упростить. Вообще, если треугольник задан координатами своих вершин, то всегда легче работать с ним через вектора, нежели вычислять стороны. Аналогично предыдущей задаче, необходимо определить каким является наибольший из углов треугольника. Вид угла легко определяется по знаку скалярного произведения образующих его векторов: оно положительно для острого угла, равно нулю для прямого угла и отрицательно для тупого угла. Поэтому необходимо посчитать все три скалярных произведения и перемножить их и по знаку данного числа можно судить о типе треугольника.
Задача №5
По данным сторонам треугольника найти его площадь.
Решение
Очевидно решение, заключается в применение формулы Герона.
Кстати, никого не интересовало доказательство этой формулы?
Вот и все!
Задача №6
Вычислить площадь треугольника заданного координатами своих вершин.
Решение
Не будем говорить о решении, которое сводится к предыдущей задачи, а попробуем воспользоваться геометрическим смыслом косового произведения. Геометрически косое произведение двух векторов определяет ориентированную площадь параллелограмма натянутого на эти вектора. Поскольку диагональ параллелограмма разбивает его на два равновеликих треугольника, то можем найти площадь нашего треугольника, как половину площади параллелограмма.
Для векторов a(x1, y1), b(x2, y2)
S = (x1y2 — x2y1) / 2 — ориентированная площадь треугольника
Задача №7
Дана точка и треугольник заданный координатами своих вершин. Определить лежит ли точка внутри, на границе или вне этого треугольника.
Решение
У этой задачи есть два принципиально разных решения. Начнем с наименее привлекательного.
Метод площадей
Если сумма площадей треугольников AKB, AKC, BKC (не ориентированных, а «обычных») больше площади треугольника ABC точка лежит вне треугольника. Если же сумма первых трех площадей равна четвертой, то нужно проверить, не равна ли нулю одна из трех площадей. Если равна, то точка лежит на границе треугольника, иначе – внутри.
Вычислять площади треугольников, естественно, надо через косое произведение векторов. Этот метод не очень хороший. Поскольку здесь используются сравнение чисел с плавающей точкой, а это в свою очередь может привести к принятию неверного решения при сравнении. Второй метод опять таки опирается на вектора, он намного эффективнее во всех отношениях.
Проверка полуплоскостей
Если хотя бы одна из сторон треугольника «разводит» противолежащую ей вершину и точку по разным полуплоскостям, то точка лежит вне треугольника. Иначе, если точка принадлежит хотя бы одной из прямых, содержащих стороны треугольника, то она находится на границе треугольника. Иначе точка лежит внутри треугольника.
В первом примере сторона AB разводит вершину C и точку K по разным полуплоскостям, поэтому точка лежит снаружи.
Задача №8
Вычисление площади многоугольника заданного координатами своих вершин.
Решение
Под многоугольником будем подразумевать простой многоугольник, то есть без самопересечений. При этом он может быть как выпуклым, так и не выпуклым.
Данную задачу можно решить двумя способами: вычисляя ориентированные площади трапеций и треугольников.
Метод трапеций
Для того чтобы посчитать площадь многоугольника нужно разбить его на трапеции, так как это показано на рисунке, а затем сложить ориентированные площади полученных трапеций это будет ориентированной площадью исходного многоугольника.
S = SA1 A2 B2 B1 + SA2 A3 B3 B2 + SA3 A4 B5 B3 + SA4 A5 B6 B5 + SA5 A6 B4 B6 + SA6 A1 B1 B4
Площади трапеций считаем по известной формуле: полусумма оснований на высоту
SA1 A2 B2 B1 = 0.5 * (A1B1 + A2B2) *(B2 — B1)
Поскольку полученная площадь является ориентированной, необходимо вычислить ее модуль.
Метод треугольников
Как вы видите задача вычисления площади многоугольника достаточна проста. Не знаю, почему, но мне больше нравится решать эту задачу методом разбиения на трапеции (наверно потому, что на всех олимпиадах я ее так решал). Тем более, что при втором решении площади треугольников надо вычислять через косое произведение. О формуле Герона надо забыть.
Задача №9
Многоугольник задан координатами своих вершин в порядке его обхода. Необходимо проверить является ли многоугольник выпуклым.
Решение
Напомню, что многоугольник называется выпуклым, если он лежит в одной полуплоскости относительно любой прямой, содержащей его сторону.
Задача опять сводится к вычислению косового произведения векторов, а именно у выпуклого многоугольника знаки косых произведений [Ai Ai+1, Ai+1 Ai+2] либо положительны, либо отрицательны. Поэтому если мы знаем направление обхода, то знак косых произведений для выпуклого многоугольника одинаков: он неотрицателен при обходе против часовой стрелки и неположителен при обходе по часовой стрелки.
Задача №10
Многоугольник (не обязательно выпуклый) на плоскости задан координатами своих вершин. Требуется подсчитать количество точек с целочисленными координатами, лежащих внутри него (но не на его границе).
Решение
Для решения этой задачи рассмотрим вспомогательную задачу: отрезок задан координатами своих концов, являющихся целыми числами. Необходимо посчитать количество целочисленных точек лежащих на отрезке. Понятно, что если отрезок вертикальный или горизонтальный, то необходимо вычесть координаты концов и добавить единицу. Интерес представляет случай, когда отрезок не является вертикальным или горизонтальным. Оказывается в этом случае необходимо достроить отрезок до прямоугольного треугольника и ответом будет число равное наибольшему общему делителю длин катетов этого треугольника плюс единица.
Для любого многоугольника с целочисленными координатами вершин справедлива формула Пика: S = n + m/2 — 1, где S – площадь многоугольника, n – количество целых точек лежащих строго внутри многоугольника, m – количество целых точек лежащих на границе многоугольника. Поскольку площадь многоугольника мы знаем как вычислять, то S известно. Так же мы можем вычислить количество целых точек лежащих на границе многоугольника, поэтому в формуле Пика остается лишь одна искомая неизвестная которую мы можем найти.
Рассмотрим пример:
S = 16 + 4 + 4,5 + 6 + 1 + 2 = 33,5
m = 15
n = 33,5 – 7,5 +1 = 27 — точек лежит строго внутри многоугольника
Вот так вот решается эта задачка!
В предыдущих статьях о геометрическом ядре C3D мы разбирали его внутреннее устройство (структура ядра, модуль визуализации) и объясняли, чем оно отличается от API CAD-системы (статья). Проявить свои качества ядро, как инструмент разработчика САПР, может только в продуктах, написанных на его основе.
Сейчас на нашем ядре выпущено более 20 коммерческих и внутрикорпоративных САПР. В обзоре мы расскажем, что это за продукты, какую роль в них выполняет ядро и в чем особенности его применения. Многие продукты, упомянутые в обзоре, уже засветились на Хабре. Мы будем давать ссылки на статьи о них.
Первым мы всегда называем КОМПАС-3D, с которого, собственно, и началась история ядра. Сегодня с системой работают более 520 000 пользователей (с учетом коммерческих, домашних, учебных лицензий). В течение 12 лет ядро развивалось как внутренний компонент КОМПАС-3D и свою начальную функциональность получило из требований его разработчиков. Трехмерное моделирование было реализовано инструментами C3D Toolkit (геометрическое ядро, параметрический решатель, конвертеры), за исключением визуализации – 3D-движок появился у нас только два года назад. Сейчас КОМПАС-3D продолжает влиять на ядро: самые насущные задачи – это моделирование сложных форм и рост производительности.
В последней версии ядра C3D Modeler мы добавили новые частные случаи построения скругления и скругление трех граней. Вообще скругления остаются одной из самых сложных задач для геометрических ядер, т.к. охватить все варианты их построения невозможно.
Частные случаи построения скругления
Скругление трех граней (или полное скругление)
Напрямую с геометрическим ядром работают и некоторые приложения КОМПАС-3D. В статье приведен пример приложения «Валы и механические передачи 3D», где с помощью ядра создаются точные модели элементов механических передач (конических, гипоидных и др.).
Еще одна хорошо известная САПР, в которой с недавних пор присутствует ядро C3D Modeler, это nanoCAD. В статье о новой платформе nanoCAD Plus 10 dows описал, как работает модуль 3D-моделирования: подключение геометрического ядра – C3D или ACIS – происходит по выбору пользователя, при этом наше ядро установлено по умолчанию.
nanoCAD Plus с модулем 3D-моделирования на C3D
Чтобы перевести на C3D операции, которые раньше выполнялись на ACIS, потребовалось преодолеть не один барьер. Смена 3D-ядра влечет за собой изменение данных ассоциативных ссылок, изменение ориентации граней и ребер, изменение типа геометрии ребер, изменение топологии тела при построении, изменение топологии тела при смене формата 3D-модели, отклонения геометрии сложных поверхностей. Все это разработчики «Нанософт» сумели победить.
Если механические САПР перешли к парадигме трехмерного проектирования довольно давно, то для САПР электронных устройств 3D становится мейнстримом только сейчас. Мировые и российские разработчики находятся здесь примерно в равных позициях с точки зрения возможностей своих продуктов. И что приятно для нас – и те, и другие работают с нашим ядром.
Год назад компания Altium, разработчик популярного во всем мире Altium Designer (преемника P-CAD), лицензировала C3D Toolkit, и в ближайшее время должна выйти новая версия Altium Designer, в которой 3D-моделирование выполнено уже нашими инструментами.
Параллельно с Altium российская компания «Эремекс» разрабатывает систему проектирования печатных плат Delta Design, опираясь на геометрическое ядро C3D Modeler.
Модель печатной платы в Delta Design
Для Delta Design нам пришлось решать проблему визуализации печатных плат с большим количеством слоев и компонентов – ускорять в ядре операции с регионами.
Инженерам-проектировщикам промышленных объектов хорошо знакома компания «НТП Трубопровод» и ее продукты СТАРТ, ПАССАТ, Штуцер-МКЭ. С 2014 года в программе ПАССАТ, выполняющей прочностные расчеты сосудов и аппаратов, на ядре C3D Modeler создаются все элементы 3D-модели, а это довольно большой список: цилиндрические обечайки и конические переходы, приварные днища и отъемные крышки, укрепление отверстий, врезки в обечайки и выпуклые днища, фланцевые соединения и т.д.
Ядро также отвечает за расчет геометрических характеристик (объем, площадь поверхности, центр тяжести, момент инерции), а конвертеры C3D Converter – за экспорт моделей в форматы ACIS, IGES, Parasolid и STEP.
ПАССАТ
В этом году «НТП Трубопровод» подключил ядро к своему второму продукту Штуцер-МКЭ (расчеты на прочность узлов врезки в оборудование), но пока не для всех геометрических операций. Из-за особенностей моделей возникли сложности с булевыми операциями и проекцией кривых на поверхность. В основном, в нашем ядре Штуцер-МКЭ хранит кривые и строит скругления.
Штуцер-МКЭ
В разработке расчетного ПО использует ядро C3D и ядерный центр РФЯЦ-ВНИИТФ Госкорпорации «Росатом». О назначении продукта мы рассказывать не имеем права, но несколько скриншотов показать можно.
Сначала наши компоненты использовались в этом продукте только для моделирования геометрии и импорта\экспорта готовой геометрии через обменные форматы, а визуализацию разработчики делали на собственных компонентах. Но год назад они перешли на наш движок C3D Vision. По их оценке, улучшилось качество и возросла скорость вывода элементов сцены. Теперь от нас ждут инструментов для создания, вывода и работы с 2D-сценой.
Несмотря на внешние различия, с точки зрения геометрического ядра архитектура мало чем отличается от машиностроения. Поэтому когда команда Renga Software Rengabim выбирала, на каком ядре писать свой BIM, наш C3D показал себя весьма достойно.
Сейчас разработчики используют ядро, решатель и конвертеры в трех продуктах: Renga Architecture, Renga Structure и Renga MEP. Инструменты C3D отвечают за создание геометрии архитектурных и конструктивных объектов, преобразование геометрии, получение разрезов и фасадов зданий, редактирование трасс и подключенного к ним оборудования, расчет масс и площадей, импорт твердотельных моделей.
Проект здания детского сада в г. Геленджике в Renga Architecture
Renga Structure
К этой группе относятся приложения, которые в России привыкли называть мебельными САПР. Компания БАЗИС-Центр первой начала использовать ядро C3D, когда у нас еще не было ни документации, ни официального прайса на лицензию, ни самого названия C3D. Свой опыт выбора и внедрения ядра в проект подробно описал x512 в статье «Ядерные технологии в CAD.
Выделим в статье один момент, связанный со спецификой проектирования мебели – моделированием гнутых фасадов. По запросу «БАЗИС-Центра» мы добавили в C3D Modeler гибку нелистовых тел. Чтобы согнуть любое тело, достаточно задать режущую плоскость, количество и толщину кусков, на которые будет разбито тело, и для каждого куска задать расположение оси сгиба и его радиус нейтрального слоя. Из кусков тела будут сформированы цилиндрические сгибы, у которых слой, отстоящий на расстояние нейтрального радиуса от оси, не будет испытывать сжатия или растяжения. Теперь в САПР Базис можно моделировать гнутые фасады с фрезеровками.
Гибка нелистовых тел
Программный комплекс К3-Мебель для проектирования, производства и продажи корпусной мебели разрабатывает нижегородский «Центр ГеоС». Это единственный наш заказчик, который использует только параметрический решатель C3D Solver, без геометрического ядра. С его помощью программируется визуализация кинематики различных мебельных механизмов, например, подъемных лифтов.
К3-Мебель
Среди наших заказчиков пока мало приверженцев облачных технологий, но если они решатся зайти на эту дорогу, то такой опыт у нас тоже есть.
Например, на ядре C3D Modeler реализован КОМПАС:24, Android-просмотрщик моделей КОМПАС-3D (статья ).
Новосибирская компания ЛЕДАС интегрировала ядро со своей облачной платформой LEDAS Cloud Platform (LCP). Платформа переносит САПР-приложения в web-среду и предоставляет в браузере функции хранения и управления данными, визуализации, навигации, коммуникации и совместной работы.
По запросу одного американского заказчика мы сделали параметрический решатель C3D Solver для JavaScript. Продукт, написанный на его основе, может не только функционировать в браузере, но и производить геометрические расчеты на стороне клиента. Насколько мы знаем, подобного решения нет ни у одного разработчика в мире.
Для удобства работы и обмена информацией в PDM-системах формируется вторичное представление документов (копия в нейтральном формате). Для этого могут использоваться VRML, eDrawings, 3D PDF. Разработчики ЛОЦМАН:PLM за 15 лет попробовали разные варианты и в прошлом году остановились на нашем просмотрщике C3D Viewer (статья). Он позволяет просматривать 3D-модели и выполнять аннотирование. Кстати функционал аннотирования был разработан по заказу команды ЛОЦМАН:PLM и входит в платную Enterprise-версию продукта. Базовый C3D Viewer остается бесплатным (скачать его можно здесь).
Вторичное представление в ЛОЦМАН:PLM
Обычно в системах подготовки управляющих программ для станков с ЧПУ геометрическое ядро играет важную, но не ключевую роль: оно работает в препроцессоре, обеспечивая импорт геометрической модели из CAD-систем и доработку геометрии перед программированием обработки. По сути, ядро нужно для насыщения CAM-систем CAD-функционалом, востребованным технологами. Не обойтись без 3D-ядра и разработчикам интегрированных CAD/CAM решений.
В Мордовском государственном университете давно сложилась команда по CAM-направлению. Сначала они написали «Модуль ЧПУ. Токарная обработка» на API КОМПАС, а позднее – «Модуль ЧПУ. Фрезерная обработка» для 2,5 и 3-координатной обработки непосредственно на ядре C3D. Их путь отличается от традиционного подхода CAM-разработчиков к ядру.
Приложение интегрировано в рабочее пространство КОМПАС-3D и использует CAD-модель, созданную в КОМПАС, в качестве источника геометрической информации. С помощью функций C3D моделируются пространственные области удаления материала, их вычитание из заготовки, построение трехмерных траекторий. Специфика применения C3D для задач CAM состоит в том, что такие сложные операции геометрического моделирования, как построение оболочек, нахождение кривых пересечения, булевы операции, не являются конечными объектами моделирования (как в системах CAD), а являются элементарными кирпичиками для реализации высокоуровневых алгоритмов, специфичных для области CAM. Это накладывает дополнительные требования к согласованию точности результатов, полученных через ядро, с общей точностью вычислений в рамках высокоуровневых задач.
Модуль ЧПУ. Фрезерная обработка
Заинтересованные разработчики могут самостоятельно протестировать C3D Toolkit. Все компоненты предоставляются бесплатно на три месяца, с документацией, по заявке на нашем сайте.
Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач.
В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их пересечения и т. п. Оперируют с такими геометрическими объектами как: точка, отрезок, многоугольник, окружность.
Вычислительная геометрия используется в распознавании образов, машинной графике, инженерном проектировании и т. д.
Алгоритмы
Алгоритмы
-
— трудоёмкость O(nlogn) . — трудоёмкость O(n 2 ) , O(nlogn) — в среднем. — построение выпуклой оболочки набора точек на плоскости методом «разделяй и властвуй» через мосты. Трудоёмкость O(nlogn) . (Джарвиса) — трудоёмкость O(nh) , h — количество точек в выпуклой оболочке. — трудоёмкость O(nlogh) , h — количество точек в выпуклой оболочке. — проверка принадлежности данной точки простому многоугольнику O(n) . — принадлежность точки простому многоугольнику O(n) . — (алгоритм Бентли-Оттманна) поиск всех точек пересечения отрезков на плоскости O((n + k)logn) , k — количество точек пересечения.
Относительное положение точки и прямой
Векторная арифметика
Здесь рассмотрим случай обычной декартовой системы координат.
Длина вектора обозначается " width="" height="" />
.
Для двух векторов и =(x_2,y_2,z_2)" width="" height="" />
их сложение определяется как =(x_1+x_2,y_1+y_2,z_1+z_2)" width="" height="" />
.
Умножение вектора на скаляр k определяется как =k\overrightarrow=(k x, k y, kz)" width="" height="" />
. При этом длина вектора меняется в | k | раз. Если k < 0, то направление вектора меняется на противоположное.
Скалярное произведение векторов и =(x_2,y_2,z_2)" width="" height="" />
равно x1x2 + y1y2 + z1z2 .
Векторное произведение векторов и =(x_2,y_2)" width="" height="" />
равно " width="" height="" />
. Это единственная операция, где уменьшение размерности пространства не сводится к простому отбрасыванию третьей координаты (замене её нулём). Обычно для двумерных векторов значением векторного произведения берут третью координату соответствующих трёхмерных векторов: x1y2 − x2y1 .
Литература
- Препарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. — М .: Мир, 1989. — 478 с.
- Ласло М. Вычислительная геометрия и компьютерная графика на C++. — М .: БИНОМ, 1997. — 304 с.
- Скворцов А.В. Триангуляция Делоне и ее применение. — Томск: Издательство Томского университета, 2002. — 128 с.
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд.Глава 33. Вычислительная геометрия // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М .: «Вильямс», 2005. — С. 1047 — 1084. — ISBN 5-8459-0857-4
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. — Springer, 2000. — 368 с.
- David M. Mount. Computional Geometry. — University of Maryland, 2002. — 122 с.
- Elmar Langetepe, Gabriel Zachmann. Geometric Data Structures for Computer Graphics. — A K Peters, 2006. — 362 с. — ISBN 1568812353
- Hormoz Pirzadeh. Computational Geometry with the Rotating Calipers. — McGill University, 1999. — 118 с.
- Jacob E. Goodman, Joseph O'Rourke. Handbook of Discrete and Computational Geometry. — CRC Press LLC, 1997. — 956 с.
- Jianer Chen. Computational Geometry: Methods and Applications. — Texas A&M University, 1996. — 228 с.
- Joseph O'Rourke. Computational Geometry in C. — Cambridge University Press, 1998. — 362 с.
- Дискретная математика
- Вычислительная геометрия
- Алгоритмы
Wikimedia Foundation . 2010 .
Смотреть что такое "Вычислительная геометрия" в других словарях:
Вычислительная математика — Имеется викиучебник по теме «Вычислительная математика» … Википедия
Вычислительная гидродинамика — Вычислительная гидродинамика (англ. Computational fluid dynamics, CFD) подраздел механики сплошных сред, включающий совокупность физических, математических и численных методов, предназначенных для вычисления характеристик потоковых… … Википедия
Компьютерная геометрия — Вычислительная геометрия раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного… … Википедия
Список академических дисциплин — Эта статья содержит незавершённый перевод с иностранного языка. Вы можете помочь проекту, переведя её до конца. Если вы знаете, на каком языке написан фрагмент, укажите его в этом шаблоне … Википедия
Алгоритм Бентли — Оттмана (1979) позволяет найти все точки пересечений прямолинейных отрезков на плоскости. В нем применяется метод выметающей прямой[1] (заметающей прямой[2], движущейся прямой[3], сканирующей линии[4]; англ. sweeping line). В методе… … Википедия
Выпуклая оболочка — Выпуклой оболочкой множества называется наименьшее выпуклое множество, содержащее . «Наименьшее множество» здесь означает наименьший элемент по отношению к вложению множеств, то есть такое выпуклое множество, содержащее данную фигуру, что оно… … Википедия
Диаграмма Вороного — случайного множества точек на плоскости Диаграмма Вороного конечного множества точек S на плоскости представляет такое разбиение плоскости, при котором ка … Википедия
Алгоритм точки в многоугольнике — Проверка принадлежности данной точки данному многоугольнику На плоскости даны многоугольник и точка. Многоугольник может быть как выпуклым, так и невыпуклым. Требуется решить вопрос о принадлежности точки многоугольнику. Благодаря тому, что… … Википедия
Дискретная математика — Дискретная математика область математики, занимающаяся изучением дискретных структур, которые возникают как в пределах самой математики, так и в её приложениях. К числу таких структур могут быть отнесены конечные группы, конечные графы, а… … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач.
В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их пересечения и т. п. Оперируют с такими геометрическими объектами как: точка, отрезок, многоугольник, окружность.
Вычислительная геометрия используется в распознавании образов, машинной графике, инженерном проектировании и т. д.
См. также
Смотреть что такое "Компьютерная геометрия" в других словарях:
Компьютерная графика — (также машинная графика) область деятельности, в которой компьютеры используются как инструмент для синтеза (создания) изображений, так и для обработки визуальной информации, полученной из реального мира. Также компьютерной графикой… … Википедия
Вычислительная геометрия — раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач. В ней рассматриваются такие задачи как триангуляция, построение выпуклой оболочки, определение принадлежности одного объекта другому, поиск их… … Википедия
N-мерная евклидова геометрия — N мерная евклидова геометрия обобщение евклидовой геометрии на пространство большего числа измерений. Хотя физическое пространство является трёхмерным[1], и человеческие органы чувств рассчитаны на восприятие трёх измерений[2], N мерная… … Википедия
Периметр (компьютерная игра) — Периметр: Геометрия Войны[1] Разработчик К Д ЛАБ … Википедия
Фоменко, Анатолий Тимофеевич — В Википедии есть статьи о других людях с такой фамилией, см. Фоменко. Анатолий Тимофеевич Фоменко Дата рождения: 13 марта 1945(1945 03 13) (67 лет) Место рождения: Сталино, УССР, СССР Страна … Википедия
Фоменко, Анатолий — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко А. — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко А. Т. — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко А.Т. — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Фоменко Анатолий Тимофеевич — Анатолий Тимофеевич Фоменко математик, специалист по геометрии, топологии, дифференциальным уравнениям, академик РАН с 1994 года. Создатель Новой хронологии Дата рождения: 13 марта 1945 (64 года) Место рождения: Донецк, УССР … Википедия
Виды многоугольников (полигонов)
Многоугольник - замкнутая кривая на плоскости, состоящая из отрезков прямых линий. Отрезки называются сторонами многоугольника, а их концы - вершинами многоугольника.
Многоугольник называется простым, если он не пересекается сам с собой.
Многоугольник называется выпуклым, если все его внутренние углы меньше или равны 180 градусам.
Цепочка вершин называется монотонной, если любая вертикальная линия пересекает ее не более одного раза. Многоугольник, составленный из двух таких цепочек называется монотонным.
Содержание
Полезное
Виды многоугольников (полигонов)
Многоугольник - замкнутая кривая на плоскости, состоящая из отрезков прямых линий. Отрезки называются сторонами многоугольника, а их концы - вершинами многоугольника.
Многоугольник называется простым, если он не пересекается сам с собой.
Многоугольник называется выпуклым, если все его внутренние углы меньше или равны 180 градусам.
Цепочка вершин называется монотонной, если любая вертикальная линия пересекает ее не более одного раза. Многоугольник, составленный из двух таких цепочек называется монотонным.
Полезное
Содержание
См. также
Полярные координаты
Литература
- Прапарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. — М.: Мир, 1989. — С. 478.
- Ласло М. Вычислительная геометрия и компьютерная графика на C++. — М.: БИНОМ, 1997. — С. 304.
- Скворцов А.В. Триангуляция Делоне и ее применение. — Томск: Издательство Томского университета, 2002. — С. 128.
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд.Глава 33. Вычислительная геометрия // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-e издание. — М.: «Вильямс», 2005. — ISBN 5-8459-0857-4
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. — Springer, 2000. — С. 368.
- David M. Mount. Computional Geometry. — University of Maryland, 2002. — С. 122.
- Elmar Langetepe, Gabriel Zachmann. Geometric Data Structures for Computer Graphics. — A K Peters, 2006. — С. 362. — ISBN 1568812353
- Hormoz Pirzadeh. Computational Geometry with the Rotating Calipers. — McGill University, 1999. — С. 118.
- Jacob E. Goodman, Joseph O'Rourke. Handbook of Discrete and Computational Geometry. — CRC Press LLC, 1997. — С. 956.
- Jianer Chen. Computational Geometry: Methods and Applications. — Texas A&M University, 1996. — С. 228.
- Joseph O'Rourke. Computational Geometry in C. — Cambridge University Press, 1998. — С. 362.
Wikimedia Foundation . 2010 .
Читайте также: