Описание тега computational-geometry

Описание тега Вопросы с тегом
None Это раздел информатики, посвященный изучению алгоритмов, которые могут быть сформулированы в терминах геометрии.
25 ответов

Как определить, находится ли список точек многоугольника по часовой стрелке?

Имея список точек, как мне найти, если они расположены по часовой стрелке? Например: point[0] = (5,0) point[1] = (6,4) point[2] = (4,5) point[3] = (1,5) point[4] = (1,0) сказал бы, что это против часовой стрелки (или против часовой стрелки, для неко…
22 июл '09 в 14:24
0 ответов

Алгоритм геометрической упаковки в 2D

Я хочу упаковать N кругов в определенных шаблонах упаковки (гексагональной и квадратной) в больший круг с радиусом r, а с номером N я хочу определить минимально необходимый радиус r. Это возможно в альфе Вольфрама ( https://www.wolframalpha.com/inpu…
02 дек '15 в 10:42
3 ответа

Алгоритм плоской развертки: Как упорядочить отрезки после точки пересечения

Я пытаюсь реализовать в коде C++ алгоритм плоской развертки для пересечений сегментов, основанный на этой книге: http://www.cs.uu.nl/geobook/. Они предлагают реализовать структуру состояния развертки плоскости с использованием сбалансированного бина…
14 окт '16 в 07:09
1 ответ

Функция для плотной упаковки сферы внутри сферы

Я пытаюсь написать функцию для самой плотной упаковки идентичных сфер внутри сферической границы. Я думаю, что это будет что-то вроде сферического пакета (c, r, n), где: c - центр граничной сферы (координаты x,y,z) r - радиус граничной сферы n - кол…
20 апр '16 в 22:45
1 ответ

Деформация локального пространства

Представьте, что у нас есть правильная плоскость, определенная в трехмерном евклидовом пространстве ("мировое пространство"). На этой плоскости мы прослеживаем дугу из точки A в точку B, подобно траектории пули, в пространстве плоскости ("локальное …
10 ноя '11 в 22:58
2 ответа

Отражать вектор в трехмерном пространстве

Вектор должен отражаться при пересечении сетки. При применении следующей формулы для отражения вектора, результат отключается. Я использую токсиклибы в обработке. // Get the normal of the face that is intersected. ReadonlyVec3D n = isect.normal; // …
26 янв '16 в 02:20
5 ответов

Аппроксимация многоугольника с помощью круга

Ну, аппроксимация круга с многоугольником и история Пифагора могут быть хорошо известны. А как же наоборот? У меня есть несколько полигонов, которые должны быть кругами. Однако из-за ошибок измерений их нет. Итак, я ищу круг, который лучше всего "пр…
12 фев '13 в 14:21
1 ответ

Пересечение между двумя трехмерными поверхностями

У меня есть две независимые 3D-фигуры; один квадрат, а другой конус. Давайте предположим, что конус лежит внутри квадрата. Как я могу узнать, что поверхность конуса касается поверхности квадрата, когда я перемещаю конус в любом направлении? Будет по…
22 ноя '17 в 08:33
3 ответа

Подход хорошего дизайна для создания библиотеки геометрии (относительно использования объединения или нет)?

Я делаю библиотеку геометрии, и я запутался, какой должен быть тип возврата функции, которая вычисляет пересечение сегмента с другим сегментом. Возвращаемое значение иногда будет точкой, а иногда сегментом (случай перекрытия), а иногда пустым наборо…
16 ноя '10 в 10:48
2 ответа

Эффективный метод для свертки, как оценка суммы

Задача Даны N 3-мерных точек, которые являются {$p_1,p_2,..,p_n$}, где $p_i = (x_i,y_i,z_i) $ . Я должен найти значение формулы для некоторых заданных постоянных целых чисел P, Q, R, S. все числа находятся в диапазоне от 1 до M ( = 100). Мне нужен э…
12 сен '15 в 18:04
2 ответа

Угол, в какую сторону повернуть

Для игры я пытаюсь вычислить угол между тем, куда я смотрю, и положением другого объекта на сцене. Я получил угол, используя следующий код: Vec3 out_sub; Math.Subtract(pEnt->vOrigin, pLocalEnt->vOrigin, out_sub); float angle = Math.DotProductA…
08 янв '12 в 17:22
2 ответа

Как найти самопересечение в многоугольнике с помощью Boost/?

Мне нужно найти пересечения себя в многоугольнике. я знаю, что повышение имеет эту способность. но я не могу понять, как использовать turn_info для получения информации о пересечениях. например, какие отрезки пересекаются и т. д. кто-нибудь может по…
09 май '16 в 09:26
2 ответа

Построение линейки и компаса в CGAL

Я пытаюсь создать базовые конструкции, такие как "получить пересечение линии и круга", "соединить две точки", "создать круг" с помощью CGAL. Тем не менее, выбор ядра кажется проблемой. Когда я использую точное 2D кольцевое ядро, я получаю Circular_a…
02 фев '18 в 04:16
0 ответов

Алгоритм нахождения самого большого вписанного прямоугольника в простых многоугольниках с дырками?

Я нахожу большую трудность в поиске такого алгоритма. Работа C.Knauer, L.Schlipf,JMSchmidt,HRTiwary для выпуклых многоугольников отмечает, что такой алгоритм возможен (пункт 5), однако я не могу понять / выяснить, как на самом деле сделать это, сохр…
16 авг '18 в 06:44
1 ответ

Ускорьте обработку пересечений на коллекции 3D линий

Рассмотрим множество трехмерных линий, случайно распределенных внутри трехмерного выпуклого тела. Чтобы найти пересечения между всеми линиями, мы получим два цикла следующим образом. n = number of lines for i: 1 to n-1 { for j: i+1 to n { if line(i)…
28 фев '17 в 18:54
1 ответ

Как найти самый большой круг между непересекающимися многоугольниками, заключенными в квадрат?

Пусть P1, .,,, Pk - набор попарно непересекающихся простых многоугольников с общим количеством ребер n, заключенных в данный квадрат. Найдите самый большой диск, который можно вписать в этот квадрат так, чтобы он не пересекался со всеми внутренностя…
23 фев '16 в 17:20
2 ответа

Как найти биссектрису угла в MATLAB

У меня есть вопрос, связанный с этим кодом: t = -20:0.1:20; plot3(zeros(size(t)),t,-t.^2); grid on hold on i = 1; h = plot3([0 0],[0 t(i)],[0 -t(i)^2],'r'); h1 = plot3([-1 0],[0 0],[-400 -200],'g'); for(i=2:length(t)) set(h,'xdata',[-1 0],'ydata',[0…
13 окт '10 в 08:13
4 ответа

Треугольник вписывается в другой треугольник

Даны длины сторон 2 треугольников. Определить, может ли второй треугольник вписаться в первый треугольник? Для получения более подробной информации прочитайте полное изложение проблемы ниже: http://acm.timus.ru/problem.aspx?space=1#=1566&locale;…
14 авг '11 в 12:15
4 ответа

Генерация новых полигонов из вырезанного полигона (2D)

Я застрял с этой маленькой проблемой, и мой алгоритм ее решения подходит не для всех случаев. У кого-нибудь есть идеи, как это решить? Вот пример многоугольника: http://img148.imageshack.us/img148/8804/poly.png Формальное описание У нас есть список …
21 ноя '09 в 13:16
2 ответа

General Polygon Clipper: триангуляция без дополнительных вершин

Я использую GPC, чтобы разбить многоугольники на треугольники. Тем не менее, GPC очень очевидно создает дополнительные вершины при генерации треугольников. Есть ли способ избежать этого?
10 фев '10 в 19:40