Вопросы с тегом «computational-geometry»

Изучение эффективных алгоритмов и структур данных для решения различных задач, включающих наборы точек, отрезки прямых, многоугольники, многогранники, симплексы и т. Д.

29
Хорошие примеры «два легко, три сложно» в вычислительных науках

Недавно я столкнулся с формулировкой мета-феномена : « два - это легко, три - трудно » (так сформулировал Федерико Полони), которую можно описать следующим образом: Когда определенная проблема сформулирована для двух сущностей, ее относительно легко решить; однако алгоритм для формулировки трех...

26
Самые быстрые библиотеки триангуляции Делоне для наборов трехмерных точек

Какая библиотека является самой быстрой для выполнения триангуляции множеств Делона с миллионами, если 3D-точки? Доступны ли также версии GPU? С другой стороны, наличие вороной тесселяции того же набора точек поможет (с точки зрения производительности) получить триангуляцию...

18
Неструктурированное построение четырехугольной сетки?

Каковы лучшие (масштабируемость и эффективность) алгоритмы для генерации неструктурированных четырехмерных сеток в 2D? Где я могу найти хороший неструктурированный четырехъядерный генератор сетки? (предпочтительно с открытым исходным...

16
Нахождение точек треугольников в

Предположим, у меня есть двумерная сетка, состоящая из непересекающихся треугольников и набора точек . Как лучше всего определить, в каком треугольнике лежит каждая из точек?{Tk}Nk=1{Tk}k=1N\{T_k\}_{k=1}^N{pi}Mi=1⊂∪Nk=1TK{pi}i=1M⊂∪k=1NTK\{p_i\}_{i=1}^M \subset \cup_{k=1}^N T_K Например, на...

15
Выбор наиболее рассеянных точек из набора точек

Существует ли какой-либо (эффективный) алгоритм для выбора поднабора из точек из набора из точек ( ), чтобы они «покрывали» большую часть области (по всем возможным подмножествам размера )?MMMNNNM< NM<NM < NMMM Я предполагаю, что точки находятся в 2D плоскости. Наивный алгоритм прост, но...

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

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

13
Подгонка неявных поверхностей к ориентированным наборам точек

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

11
Сортировка облака точек по неструктурированной сетке из шестигранных ячеек

Вопрос Как бы вы отсортировали облако точек относительно неструктурированной сетки шестигранных ячеек? Каждая ячейка имеет центр и уникальный ярлык для ее представления. В основном есть две точки облаков (исходное облако точек и облако точек центров ячеек), но информация о геометрии ячейки...

11
Объем трехмерного выпуклого корпуса малой точки устанавливает все на корпус

У меня есть вопрос, похожий на тот, который задавался ранее, за исключением 3D, и мне нужен только объем, а не фактическая форма корпуса. Точнее, мне дан небольшой набор точек (скажем, 10-15) в 3D, все из которых, как известно, лежат на выпуклой оболочке набора точек (поэтому все они «имеют...

10
Как проблемы тесселяции Вороного и триангуляции Делоне сопряжены друг с другом?

Мне всегда говорили, что диаграмма Вороного является двойственной проблемой триангуляции Делоне. В каком смысле они могут быть двойниками друг друга? Я думал, что двойные задачи (т.е. в линейном программировании) должны давать один и тот же ответ. Очевидно, что две проблемы не имеют одинакового...

10
N-мерные библиотеки программного обеспечения Делоне

У меня есть набор известных точек / узлов, нерегулярно расположенных в N-мерном пространстве (N> = 2), и я хотел бы получить способ сгенерировать триангуляцию Делоне этих точек и вернуть соответствующие элементы. Существуют ли какие-либо библиотеки с сетками, которые будут выполнять триангуляцию...

10
Как выбрать точки в гиперболическом пространстве?

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

9
При заданных значениях в сетке, какой алгоритм я могу использовать для эффективного построения заданных контуров уровня?

У меня есть сетка, грани , ребра и вершины , и у меня есть список предопределенных контуров набора уровней.FFFЕEEВVV Какой алгоритм я могу использовать для построения контуров наиболее эффективным способом? Участок контура показан выше. Линии с одинаковым цветом имеют одинаковое значение...

9
Существует ли алгоритм для поиска почти выпуклой оболочки с учетом угла допуска?

Я хотел бы знать, если есть алгоритм, который дает множество точек и угол вычисляет выпуклую оболочку, если угол α = 0α=0\alpha = 0 и дали α > 0α>0\alpha > 0 вычисляет конверт, который более близко следует за «периметром». И если есть определение непересекающегося периметра множества точек, в...