Описание тега space-partitioning

Вопросы с тегом
1 ответ

QuadTree для пространственного разделения (Java)

В настоящее время я пытаюсь реализовать quadtree для разделения карты. Я провел исследование на прошлой неделе и не был успешным. Я пытаюсь разделить карту на различные прямоугольники, которые будут разными областями карты в зависимости от того, где…
07 авг '15 в 16:45
1 ответ

В поисках хорошей структуры данных с пространственным разделением для быстрой генерации миллионов атомных связей из

Я выполняю некоторые МД симуляции с участием систем из миллионов атомов. Я написал некоторый код для генерации файла, который представляет собой просто список координат атома XYZ. Теперь мне нужно создать связи между атомами. Если два атома находятс…
30 янв '13 в 22:43
2 ответа

Реализация Octree для треугольной сетки и частиц

В настоящее время я работаю в эффективном механизме расчета для моделирования частиц как в CPU, так и в GPU. В последнее время я работал в октриах, и мне удалось написать рабочую версию октри для частиц в космосе, а также эффективно обрабатывать их …
12 июл '14 в 09:23
6 ответов

Пересечение тысяч лучей с треугольниками в трехмерном пространстве

Есть тысячи лучей и треугольников. Нам нужно получить все точки пересечения. Если мы используем обычные двухуровневые циклы, нам понадобится O (mn) временная сложность. Есть ли способ уменьшить временную сложность от O (m n) до O(m* logn) или O(logm…
23 дек '09 в 09:29
1 ответ

Пересечение одной сферы и множества отрезков

Я знаком с BSP, KD-деревом и BVH для общей задачи поиска пересечения примитивных лучей. Существуют ли более эффективные алгоритмы и структуры данных для поиска пересечений только между одной сферой и множеством отрезков? Обратите внимание, что сфера…
04 фев '18 в 15:06
0 ответов

Pygame заставляет один круг двигаться в соответствии с другим

Я занимаюсь разработкой симулятора баскетбола в Pygame. Мне нужно, чтобы он работал так, чтобы, если пространство перед игроком в 1 команде было свободным, он двигался к обручу, если нет, он будет пытаться преодолеть указанное препятствие с заранее …
13 фев '18 в 17:59
1 ответ

Как разделить / разбить полигоны на существующие регионы?

Я сталкиваюсь с проблемой, касающейся "разбиения"/ поднабора полигонов на регионы (большие полигоны), чтобы в каждом регионе были непересекающиеся значимые элементы. Например, у нас есть следующие регионы / полигоны. В данный момент времени мы знаем…
25 июл '16 в 07:23
2 ответа

Как устранить сталкивающиеся маркеры в Google Maps

Я должен показать набор маркеров на карте, чтобы указать близлежащие достопримечательности. Эти маркеры откроют общедоступные чаты по щелчку, и поэтому я думаю, что пользователи должны видеть краткую адресную информацию о каждом маркере перед входом…
30 янв '17 в 00:12
1 ответ

Структура данных для подвижных точек в 3d

У меня много точек (+100 000) в трехмерном пространстве. Мне нужно использовать запросы ближайшего соседа и диапазона. Сначала я использовал kdtree (k=3), но каждая точка имеет атрибут скорости. Их местоположение не является статичным, они меняют св…
28 авг '13 в 09:58
4 ответа

Визуализация ближайших соседних зон

Я пишу приложение, которое ищет точки в двухмерном пространстве, используя дерево kd. Во время разработки было бы хорошо иметь возможность "видеть" зоны ближайших соседей, окружающих каждую точку. На прилагаемом изображении красные точки - это точки…
15 фев '12 в 06:32
2 ответа

Определить, если область пространства пуста

У меня есть область пространства, 2 измерения, от (0,0) в (MAX_X, MAX_Y), Внутри этой области пространства я рисую некоторые линии, они пересекают периметр области и могут пересекаться друг с другом. Таким образом, эти линии разделяют мою область пр…
10 авг '11 в 21:34
7 ответов

Когда использовать Binary Space Partitioning, Quadtree, Octree?

Недавно я узнал о деревьях разбиения двоичного пространства и их применении к трехмерной графике и обнаружению столкновений. Я также кратко ознакомился с материалами, касающимися квадр и октре. Когда бы вы использовали дерево на деревьях BSP, или на…
19 сен '08 в 05:08
1 ответ

Алгоритм разбиения одномерного пространства

Я два набора интервалов, которые соответствуют одному и тому же одномерному (линейному) пространству. Вот грубое визуальное представление - на самом деле интервалов намного больше, и они гораздо более разбросаны, но это дает основную идею. Каждый из…
01 апр '11 в 03:13
3 ответа

Что-нибудь лучше, чем ограничительные рамки?

У меня есть сценарий, где у меня есть x миллионов точек широты долготы. Когда добавляется новая точка long/lat, я хочу эффективно знать, какие другие точки находятся в параметре расстояния, настроенного пользователем, чтобы я мог добавить их в списо…
04 дек '09 в 17:04
2 ответа

Как работает алгоритм разделения пространства для поиска ближайших соседей?

Для нахождения ближайшего соседа Space Partitioning является одним из алгоритмов. Как это работает? Предположим, у меня есть двумерный набор точек (координаты x и y), и мне дана точка (a,b). Как этот алгоритм узнает ближайшего соседа?
11 ноя '09 в 08:02
3 ответа

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

У меня есть 2D-карта, которая оборачивается по краям. Поэтому, если вы отойдете от правого края, вы снова появитесь в левой части карты. Точно так же с тремя другими краями. Это наследственная проблема для KDTree, которую я использую для поиска элем…
06 ноя '11 в 01:08
8 ответов

Алгоритм разделения пространства

У меня есть набор точек, которые содержатся в прямоугольнике. Я хотел бы разбить прямоугольники на под прямоугольники, основываясь на плотности точек (давая количество под прямоугольников или желаемую плотность, в зависимости от того, что проще). Ра…
02 июн '10 в 16:21
2 ответа

Как сделать разделение пространства чайника в Юте?

Имея дело с преобразованием патчей Безье в треугольники, мне нужно сделать бинарное пространство, чтобы нарисовать спроецированные треугольники, используя алгоритм Painter. Я реализовал алгоритм из Википедии с большой помощью по математике. Но это д…
11 фев '13 в 07:00
2 ответа

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

У меня есть несколько кубоидов, чьи позиции и размеры даны с минимальным и максимальным x, y а также z координаты (поэтому они параллельны основным осям). например, у меня могут быть следующие 3 кубоида: 10,5 <= x <= 39,4, 90,73 <= y <= 110,2, 90,23…
21 июл '09 в 12:14
3 ответа

Оптимизировать отбор Frustum

Я пишу игру на C++, и у меня есть уровень, состоящий из множества отдельных сеток, каждая из которых имеет свой собственный буфер вершин. я использую vmmlib (блестящий бесплатный gl compat. vector/matrix library), чтобы создать свой сборщик frustum …
07 окт '08 в 17:57