Исходная задача — есть большой набор объектов в ограниченной области 3d пространства. Требуется эффективно найти точки пересечения этих объектов с произвольно заданным лучом.
Я планирую подход, когда все пространство разбивается на одинаковые кубики (с помощью octree), каждому из которых приписывается набор номеров объектов, с которыми тот имеет пересечение. Тогда процедура поиска точек пересечений сводится к движению по кубикам (которые пересекаются с лучом) и нахождению для каждого кубика точек пересечений со всеми объектами из приписанного ему набора.
Проблема в том, что может оказаться, что в рядом стоящих кубиках будут одинаковые наборы, а потому получится повторение проверок на пересечение с лучом. Хотелось бы как-то это быстро отслеживать. но ничего кроме заведения множества уже проверенных объектов и работе с ним в голову не приходит. А в С++ множество (std::set), насколько я себе представляю, работает с динамическим выделением памяти + теоретико-множественные операции тоже каждый раз будут образовывать новое множество с опять-таки выделением памяти. То есть, получается долго.

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

Спасибо.

Здравствуйте, _hum_, Вы писали:

__>Есть ли какой-нибудь другой подход или какая-нибудь другая структура данных, которая бы была в этом случае эффективна?
Первое, что приходит на ум — битовое поле.
У нас есть Н объектов, нужно хранить их в массиве unsigned char с размером Н/8.
Операции объединения\пересечения множеств опредаляются через битовые операции.

Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, _hum_, Вы писали:

__>>Есть ли какой-нибудь другой подход или какая-нибудь другая структура данных, которая бы была в этом случае эффективна?
GC>Первое, что приходит на ум — битовое поле.
GC>У нас есть Н объектов, нужно хранить их в массиве unsigned char с размером Н/8.
GC>Операции объединения\пересечения множеств опредаляются через битовые операции.
этот вариант не подходит, потому что
1) объектов очень много (порядка миллиона), потому для побитовых операций придется бегать как минимум по uint64_t массиву;
2) получить список битового поля — опять же надо все биты проверить.

Здравствуйте, _hum_, Вы писали:

__>Исходная задача — есть большой набор объектов в ограниченной области 3d пространства. Требуется эффективно найти точки пересечения этих объектов с произвольно заданным лучом.
__>Я планирую подход, когда все пространство разбивается на одинаковые кубики (с помощью octree), каждому из которых приписывается набор номеров объектов, с которыми тот имеет пересечение. Тогда процедура поиска точек пересечений сводится к движению по кубикам (которые пересекаются с лучом) и нахождению для каждого кубика точек пересечений со всеми объектами из приписанного ему набора.
__>Проблема в том, что может оказаться, что в рядом стоящих кубиках будут одинаковые наборы, а потому получится повторение проверок на пересечение с лучом. Хотелось бы как-то это быстро отслеживать. но ничего кроме заведения множества уже проверенных объектов и работе с ним в голову не приходит. А в С++ множество (std::set), насколько я себе представляю, работает с динамическим выделением памяти + теоретико-множественные операции тоже каждый раз будут образовывать новое множество с опять-таки выделением памяти. То есть, получается долго.

__>Есть ли какой-нибудь другой подход или какая-нибудь другая структура данных, которая бы была в этом случае эффективна?

__>Спасибо.

Если списки, которые нужно сливать — короткие, можно посмотреть в сторону хранения сортированного массива элементов.
Или, что тоже самое, boost::flat_set https://www.boost.org/doc/libs/1_56_0/doc/html/boost/container/flat_set.html , но он тоже делает аллокацию, правда только одну, и можно поиграть с reserve и пер-использованием одной и той-же переменной.

Здравствуйте, Chorkov, Вы писали:

C>Если списки, которые нужно сливать — короткие, можно посмотреть в сторону хранения сортированного массива элементов.
У него миллионные списки:
__>этот вариант не подходит, потому что
__>1) объектов очень много (порядка миллиона), потому для побитовых операций придется бегать как минимум по uint64_t массиву;

Здравствуйте, GhostCoders, Вы писали:

GC>Здравствуйте, Chorkov, Вы писали:

C>>Если списки, которые нужно сливать — короткие, можно посмотреть в сторону хранения сортированного массива элементов.
GC>У него миллионные списки:

Милионные — это объектов всего.
Число объектов в одном кубике — врядли очень большое.
Число объектов, которые пересекает луч — тут надо спросить статистику у _hum_.
В любом случае можно разбивать кубики на группы, и мерджить сперва в пределах групп, а потом группы.

Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, _hum_, Вы писали:

__>>Исходная задача — есть большой набор объектов в ограниченной области 3d пространства. Требуется эффективно найти точки пересечения этих объектов с произвольно заданным лучом.
__>>Я планирую подход, когда все пространство разбивается на одинаковые кубики (с помощью octree), каждому из которых приписывается набор номеров объектов, с которыми тот имеет пересечение. Тогда процедура поиска точек пересечений сводится к движению по кубикам (которые пересекаются с лучом) и нахождению для каждого кубика точек пересечений со всеми объектами из приписанного ему набора.
__>>Проблема в том, что может оказаться, что в рядом стоящих кубиках будут одинаковые наборы, а потому получится повторение проверок на пересечение с лучом. Хотелось бы как-то это быстро отслеживать. но ничего кроме заведения множества уже проверенных объектов и работе с ним в голову не приходит. А в С++ множество (std::set), насколько я себе представляю, работает с динамическим выделением памяти + теоретико-множественные операции тоже каждый раз будут образовывать новое множество с опять-таки выделением памяти. То есть, получается долго.

__>>Есть ли какой-нибудь другой подход или какая-нибудь другая структура данных, которая бы была в этом случае эффективна?

__>>Спасибо.

C>Если списки, которые нужно сливать — короткие, можно посмотреть в сторону хранения сортированного массива элементов.
C>Или, что тоже самое, boost::flat_set https://www.boost.org/doc/libs/1_56_0/doc/html/boost/container/flat_set.html , но он тоже делает аллокацию, правда только одну, и можно поиграть с reserve и пер-использованием одной и той-же переменной.

Так а в чем выигрыш? Все равно придется для каждого нового кубика пробегаться по всему набору его объектов, чтобы проверить, есть он в списке уже отсмотренных или нет. Это равносильно заведению массива для всех возможных объектов с пометками в нем, какие уже были проверены к данному моменту, а какие нет.

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

Здравствуйте, _hum_, Вы писали:

__>Здравствуйте, Chorkov, Вы писали:

C>>Здравствуйте, _hum_, Вы писали:

__>>>Исходная задача — есть большой набор объектов в ограниченной области 3d пространства. Требуется эффективно найти точки пересечения этих объектов с произвольно заданным лучом.
__>>>Я планирую подход, когда все пространство разбивается на одинаковые кубики (с помощью octree), каждому из которых приписывается набор номеров объектов, с которыми тот имеет пересечение. Тогда процедура поиска точек пересечений сводится к движению по кубикам (которые пересекаются с лучом) и нахождению для каждого кубика точек пересечений со всеми объектами из приписанного ему набора.
__>>>Проблема в том, что может оказаться, что в рядом стоящих кубиках будут одинаковые наборы, а потому получится повторение проверок на пересечение с лучом. Хотелось бы как-то это быстро отслеживать. но ничего кроме заведения множества уже проверенных объектов и работе с ним в голову не приходит. А в С++ множество (std::set), насколько я себе представляю, работает с динамическим выделением памяти + теоретико-множественные операции тоже каждый раз будут образовывать новое множество с опять-таки выделением памяти. То есть, получается долго.

__>>>Есть ли какой-нибудь другой подход или какая-нибудь другая структура данных, которая бы была в этом случае эффективна?

__>>>Спасибо.

C>>Если списки, которые нужно сливать — короткие, можно посмотреть в сторону хранения сортированного массива элементов.
C>>Или, что тоже самое, boost::flat_set https://www.boost.org/doc/libs/1_56_0/doc/html/boost/container/flat_set.html , но он тоже делает аллокацию, правда только одну, и можно поиграть с reserve и пер-использованием одной и той-же переменной.

__>Так а в чем выигрыш? Все равно придется для каждого нового кубика пробегаться по всему набору его объектов, чтобы проверить, есть он в списке уже отсмотренных или нет. Это равносильно заведению массива для всех возможных объектов с пометками в нем, какие уже были проверены к данному моменту, а какие нет.

Проверка в массиве флагов, конечно, O(1). Но предварительное обнуление массива — О(число объектов в системе).
Если число объектов пересекаемымых лучем не велико, обнуление масива может быть дороже всех проверок.
Просто я, видимо, предположил другую статистику, по опыту своей звдачи.

__>Я тут было подумал, что можно хранить в каждом кубике еще и разности наборов объектов с соседними с ним кубиками — тогда во многих случаях (особенно для больших областей повторения) это должно сработать. Но плохо, что тут гарантия только "в среднем", а памяти и времени такой подход будет есть предостаточно

Можно хранить в кубе список элементов граница которых пересекается с кубом.

Здравствуйте, Chorkov, Вы писали:

C>Здравствуйте, _hum_, Вы писали:

C>>>Если списки, которые нужно сливать — короткие, можно посмотреть в сторону хранения сортированного массива элементов.
C>>>Или, что тоже самое, boost::flat_set https://www.boost.org/doc/libs/1_56_0/doc/html/boost/container/flat_set.html , но он тоже делает аллокацию, правда только одну, и можно поиграть с reserve и пер-использованием одной и той-же переменной.

__>>Так а в чем выигрыш? Все равно придется для каждого нового кубика пробегаться по всему набору его объектов, чтобы проверить, есть он в списке уже отсмотренных или нет. Это равносильно заведению массива для всех возможных объектов с пометками в нем, какие уже были проверены к данному моменту, а какие нет.

C>Проверка в массиве флагов, конечно, O(1). Но предварительное обнуление массива — О(число объектов в системе).

не обязательно. Можно в массиве хранить еще и идентификатор луча, тем самым "обнуляя" все результаты трассировки предыдущего.

__>>Я тут было подумал, что можно хранить в каждом кубике еще и разности наборов объектов с соседними с ним кубиками — тогда во многих случаях (особенно для больших областей повторения) это должно сработать. Но плохо, что тут гарантия только "в среднем", а памяти и времени такой подход будет есть предостаточно

C>Можно хранить в кубе список элементов граница которых пересекается с кубом.

по исходной задаче в кубе и содержится список объектов, имеющих пересечение с кубом (треугольники триангулированных поверхностей объектов)