Структура данных с моментальным доступом по формуле

Добрый день. Мне нужна структура данных, которая обеспечивала бы моментальный доступ к данным, не перебирая все варианты, по формуле. Что имеется ввиду собственно...
1. Есть миллиарды точек в 2D пространстве с координатами X и Y.
2. Есть какая - то хитрая база данных, хитро связанный список или что - то ещё, что собственно и нужно придумать, в общем какой то контейнер, который хранит все эти миллиарды точек из п.1.
3. Задача, не перебирая все точки в контейнере (т.к. это очень медленно), выбрать одной или хотя бы небольшим кол-вом операций, все точки, который лежат на прямой, заданной, например, как y = kx+b или любым другим способом.
То есть из этого огромного 2д массива точек нужно одним махом выбрать все точки, соответствующие какому - то условию, для простоты будет рассматривать условие только прямой линии/ луча/ отрезка.... Ну вот представьте, к примеру, квадрат размером 1000 х 1000 точек, я как бы виртуально провожу насквозь этого квадрата линию и хочу выбрать все точки, которые лежат на этой линии (или лежат рядом с ней)...

Есть ли какие - то готовые решения на этот счёт? Может какие - то хитрые NoSQL методы или ещё что?

0

Сообщение от Praktolock Я думаю, что вы усложнили себе задачу

Усложнил? Да вы что, это дикое упрощение, т.к.

Сообщение от Praktolock Вам все-таки треугольники нужно искать

это гораздо сложнее

Сообщение от Praktolock 3-д движок пишете что-ли?

Свой низкоуровневый рендер движок на OpenCL типа DirectX/ OpenGL/ Vulkan и пр

У меня кажется появились идеи на счёт основной задачи в нуль посте... Сейчас проверю...

Praktolock, прикольный ник Собственно как и у меня )))))

0

Сообщение от stupid Усложнил? Да вы что, это дикое упрощение, т.к.

Да как раз нет. Кароч, нужно сначала отсечь треугольники выходящие за пределы экрана, пометить их как невидимые(опционально отсечь повернутые к нам задами), вычислить квадратные области оставшихся треугольников в координатах экрана, и их же многоугольники полученные отсечением краями экрана. При трассировке каждого луча проверять сначала на попадание в квадрат, затем в многоугольник, и при совпадении этих условий искать пересечение с треугольником. Таким образом сильно экономятся ресурсы. А пересечение луча с треугольником ищется очень просто. Задача сволится к разложению вектора по базису решением системы линейных уравнений.

Добавлено через 34 секунды
Я писал такое как-то раз, только без оптимизаций описанных мною выше

Добавлено через 2 минуты
А то что вы пытаетесь сделать, напоминает толи воксельную графику, толи какую-то странную разновидность Z-buffer'а

0

Сообщение от stupid Это подойдёт только для ортогональных линий, то есть ты как бы для каждого X делаешь список всех Y-ков, ну и для каждый Y-ков можешь сделать список всех X-ов, тогда да, ты сможешь легко взять ортогональную линию, посмотреть её массив и выбрать ближайшую точку. Но если речь идёт не только об ортогональных линиях, а об линиях любого направления, тогда подобные массивы нужны для всех направления и со всеми сдвигами по Х и Y, то есть это очень много....

Обращение к элементу по его значению (значение - ключ) это структура вроде разряженного массива или дерева поиска. Эти структуры плохо дружат с упорядоченностью и, следовательно, индексным обращением (с бинарным поиском) по своей природе. Но моментальный быстрый доступ они обеспечивают. Есть трудности с временем добавления/удаления. Иначе - массив, то есть очень много памяти. Всё в одной тарелке не получится. Или что-то надо изобрести.

Сообщение от stupid Это подойдёт только для ортогональных линий

А это неверно. Если Вы дерево деревянное имеете ввиду. Оно быстро Вам выдаст точку M(x,y) если она у него есть. Теперь, если у Вас есть у=kx+b то вы идёте по всем парам х, y=f(x) и смотрите какие точки присутствуют собирая их в какой-то контейнер. Список например. Это быстрее последовательного перебора. Намного.

0

Сообщение от Praktolock Да как раз нет. Кароч, нужно сначала отсечь треугольники выходящие за пределы экрана, пометить их как невидимые(опционально отсечь повернутые к нам задами), вычислить квадратные области оставшихся треугольников в координатах экрана, и их же многоугольники полученные отсечением краями экрана

Это вообще не в тему, это перебор всех треугольников, отсеивание, ещё перебор и ещё и ещё.......это ерунда в общем, которая характерна для любого piplina всяких DirectX-ов...

Сообщение от Praktolock При трассировке каждого луча проверять сначала на попадание в квадрат, затем в многоугольник

Это всякие kd и иерархические деревья, они ускоряют, но не на столько. Плюс с ними геморроя много.
У нас же тут тема про риал тайм с миллиардами треугольников и структурой данных с моментальным доступом.

Сообщение от IGPIGP Обращение к элементу по его значению (значение - ключ) это структура вроде разряженного массива или дерева поиска.

Ну можно ж в памяти выделять блок и считать что адрес ячейки это и есть значение. Так можно моментально получить элемент по значению, с этим проблем нет. Но! Если наши точки даже в 2д пространстве, у них есть две координаты, то есть Х и У, то есть у нас уже два разряженных дерева, то есть два массива типа [адрес памяти, он же - значение; ссылка на полезные данные]. Из одного массива я легко могу моментально взять нужное мне значение, просто взяв его по адресу, а вот из двух массивов взять элемент, который соответствует двум значениям, то есть какому - то значению по Х и какому - то по У - уже сложнее, но так же просто, для этого для каждого Х в первом массиве как бы делаешь свой массив У-ков, то есть если тебе нужно выбрать точку с координатами 100,200; ты просто моментально берёшь указатель на массив У-ков и первого массива Х-ов (на отметке 100) и оттуда уже так же моментально берёшь по У-ку. Всё просто, но только для выбора одной точки, а вот если требуется выбрать диапазон - то тут уже начинается и весь геморрой, то есть для того, что бы из 2д массива моментально выбрать хотя бы все точки, лежащие внутри окружности, расположенной где - то там ..... Нужно уже.... Я не знаю пока что, что для этого нужно делать.... Понятно, что тут должны быть хеши... Но их должно быть слишком много, для всех возможных случаев, что полнейший оверхэд по памяти.... Пока что я не знаю, как решить эту задачу....

Добавлено через 2 минуты

Сообщение от IGPIGP то вы идёте по всем парам х, y=f(x) и смотрите какие точки присутствуют

то есть это полный перебор всех ячеек.... чем это может быть быстрее?

Сообщение от IGPIGP последовательного перебора

?

0

Сообщение от stupid то есть у нас уже два разряженных дерева,

Одно. Это елка. Наряженное дерево. А разряжённый это массив или кольт.

Сообщение от stupid то есть это полный перебор всех ячеек.... чем это может быть быстрее?

по х придётся идти подряд. Это потому, что формула вроде kx+b не имеет понятия о том какие из x содержат y удовлетворяющие данному условию. Некоторые x вообще могут не содержать y-ков. Но в сбалансированном дереве Вы легко дойдёте до листа в каждом случае когда нет требуемого нода. Но вначале поста Вы спрашивали доступ по ключу - значение, а потом стали спрашивать о доступе по порядку и по диапазону значений. Это противоположные задачи всё-таки. Дерево лучше по значению работает. Что касается последовательного перебора то ещё можно выбирать иксы при inorder итерации. Это может быть быстрее чем перебирать последовательно все возможные значения.

0

Сообщение от stupid Это вообще не в тему, это перебор всех треугольников, отсеивание, ещё перебор и ещё и ещё.......это ерунда в общем, которая характерна для любого piplina всяких DirectX-ов..

Да, это не в тему. Это о том, что , на мой взгляд, задача в принципе неверно поставлена, и я решал бы по-другому. ИМХО

1