[С++] Обход окрестности точки

Что за контейнер и как (по какому ключу) производится доступ к элементу?

Сколько точек в окрестности надо взять?

Важна ли производительность и если да, то какой размер ячейки контейнера и какой типичный размер контейнера?

R-Tree

Страсть господня... зачем? Если это то, о чем думаю, то просто пишем в массивчик набор смещений относительно исходной точки в порядке удаления, и по нему ходим.

Страсть господня... зачем?

это надо у ТС спрашивать :) был вопрос поиска стандартного велосипеда

Соорудил свой велосипед для обхода окрестности точки, с удовольствием заменю на какой-нибудь стандартный.

теперь стандартный велосипед у ТС есть, а то что он оснащён турбокомпрессором, этого в задаче не оговаривалось :)

Мы с Вами похоже по разному поняли задачу, сэр. Я думаю, что у ТС-а есть двумерный массив (сиречь контейнер), и ему надо обходить ячейки, соседствующие с данной напрямую, через одну и тд.

А Вы, сэр, видимо думаете что у ТС есть набор точек (x,y), и надо обойти соседей данной точки? Тогда конечно R-tree без вопросов;-)

А что там у ТС-а на самом деле одному ТС-у ведомо, все наши телепаты сейчас заглушены мыслями тети Клавы с верхнего этажа к которой пришел полюбовник, и к ТС-у пробиться никак не могут...

>просто пишем в массивчик набор смещений относительно исходной точки в порядке удаления, и по нему ходим.

именно так я и сделал, просто охота найти что-нибудь готовое, задача-то на вид стандартная.

>Что за контейнер и как (по какому ключу) производится доступ к элементу?

тупой двумерный массив с индексацией по координатам, данные которые планируется хранить - POD структуры.

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

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

> Соорудил свой велосипед для обхода окрестности точки

Такой?

#include <stdio.h>

int main() {
        int eps = 5, r = 0, s = 0;

        printf("[0, 0]");

        for (r = 1; r < eps; r++) {
                printf(" (r = %d)", r); 
                
                printf(" [%d, %d]", r, 0);
                printf(" [%d, %d]", -r, 0); 
                printf(" [%d, %d]", 0, r);
                printf(" [%d, %d]", 0, -r); 

                for (s = 1; s < eps; s++) {
                        printf(" (s = %d)", s); 

                        printf(" [%d, %d]", r, s);
                        printf(" [%d, %d]", r, -s); 
                        printf(" [%d, %d]", -r, s); 
                        printf(" [%d, %d]", -r, -s);

                        if (s != r) { 
                                printf(" [%d, %d]", s, r);
                                printf(" [%d, %d]", s, -r); 
                                printf(" [%d, %d]", -s, r); 
                                printf(" [%d, %d]", -s, -r);
                        }   
                }   
        }   

        return 0;
}

не так обход ведется от ближних к дальним, тут порядок другой - это критично. норму я использую первую, тут ||||_бесконечность, на самом деле хотелось бы эвклидову.

ну и я получаю итераторы для окрестности - это удобней.

Да, ерунда получилась...

Я таки повторяю два вопроса:

Сколько точек в окрестности надо взять?

Важна ли производительность и если да, то какой размер ячейки контейнера и какой типичный размер контейнера?

проще всего, как и писал выше, загнать в массив смещения относительно данной ячейки тех соседей, к-е нужны, и в том порядке в котором нужно, и дальше ходить по этому массиву.

>> просто пишем в массивчик набор смещений относительно исходной точки в порядке удаления, и по нему ходим.

именно так я и сделал, просто охота найти что-нибудь готовое, задача-то на вид стандартная.

а это стандратное решение этой стандартной задачи;-) Все отсальное во первых сложнее, во вторых медленнее работает.

Если массив большой а операций над ячейкой сравнительно немного, можно получить существенный профит по производительности перейдя к локально-рекурсивному контейнеру. И наверное это все, что можно тут улучшить...

Окрестность надо строить любого размера, точки брать все, ну или фильтровать по какому-нибудь правилу, например выкидывать те что выходят за границы массива.

Производительность важна, размер ячейки от 4 байт до 64, по-разному может получиться, сейчас 12 байт. Контейнеры планируются большими, собственно чем больше, тем лучше, но реально буду ограничиваться тем что можно будет обработать в реальном времени на GPU. хотелось бы получить 10000x10000, но даже 1000х1000 будет интересно. Сам фильтр простой, так что скорость будет больше зависить от размера окрестности и размера данных.

проще всего, как и писал выше, загнать в массив смещения относительно данной ячейки тех соседей, к-е нужны, и в том порядке в котором нужно, и дальше ходить по этому массиву.

я так и сделал.

А если разбить окрестность на 8 симметричных/зеркально симметричных частей. И для одной окрестности посчитать массив норм, выполнить быструю сортировку по этой норме, а дальше выполнять обход.
Сортируемый массив структур.

struct point_s {
        int x;
        int y;
        double norm;
}

Все? N^2 операций, и для каждой ячейки надо пройти все ячейки массива? Тухляк, тупо упретесь в пропускную способность подсистемы памяти. Как ни делай - все равно будет плохо.

Что ж за задача то такая...

>Все? N^2 операций, и для каждой ячейки надо пройти все ячейки массива?

не все ячейки массива, а все ячейки окрестности, а размер окрестности придется подбирать. задача - эксперименты со всякими схемами эволюции больших систем в зависимости от начальной конфигурации, just for fun. в худшем случае получу вот такие анимации. http://vasaka.deviantart.com/#/d4aii8f

>А если...

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

это же для фильтрации изображений стандартная процедура.

это же для фильтрации изображений стандартная процедура

Казалось бы да. Но на самом деле - черт те что творится. Я так ничего приличного и не нашел, пришлось даже популярные алгоритмы самому велосипедить.

Если есть возможность использовать ещё 12.5% памяти, нутром чую, лучше не придумаешь алгоритма. Быстрая сортировка - уже не велосипед.
А чтобы ещё и сортировку ускорить в случае Евклидовой нормы, можно заполнять сортируемый массив по алгоритму, предложенному в коде выше. В конце сортировки брать первые наперёд заданные N чисел, N определяется радиусом окружности.

...12.5% от занимаемой памяти одним окном, т.е. 0 фактически в целом.
Эту процедуру нужно выполнить лишь один раз же?!
В массиве будут храниться смещения относительно произвольной (x;y). Если я правильно понял, любой алгоритм подойдёт для этого. =)

То ли я чего-то не понял... Целочисленные точки (X,Y), удаленные от исходной (X0,Y0) на C шагов: abs(X-X0)+abs(Y-Y0) = C. Цикл по С, цикл по X (от X0-C до X0+C) или Y - и вот мы обходим точки в порядке удаления от данной, прям как если бы честно запустили поиск в ширину.

А, ну тогда берите локально-рекурсивный контейнер - для небольших окрестностей (десятки точек) и больших размеров массивов можете получить выигрыш на порядок и более. Правда массив будет только квадратным со стороной 2^n

>То ли я чего-то не понял...

похоже на то. я спрашиваю не как это написать, а нет ли готового. а предложенное решение может работать только для нормы у которых окрестность квадрат или ромб. с эвклидовой нормой надо по-другому.

локально-рекурсивный контейнер

а что это? гугл меня только на лор и отправляет.

Уф... вот обычный массив (эмуляция двумерного массива на основе одномерного, выделяется Nx*Ny ячеек), показан индекс- смещение ячейки от начала вектора.

0 1 2 3 
4 5 6 7 
8 9 10 11
12 13 14 15

А вот локально-рекурсивный:

0 1 4 5
2 3 6 7
8 9 12 13
10 11 14 15

Если массив квадратный, со стороной 2^n, то в обычном массиве первые n бит индекса отвечают за координату по x, вторые n бит индекса отвечают за координату по y

В LR массиве число, составленное из четных бит индекса отвечает за координату по x, число состоавленное из нечетных бит индекса - за координату по y. Двумерный LR массив можно рассматривать как четверичное дерево с одинаковой длиной ветвей, на листьях которого лежат данные.

LR массив обеспечивает высокую локальность данных при обращении к соседям ячейки.

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

а то это либо что-то малораспространенное, либо как-то по-другому зовется обычно.

Это что то малораспространенное наск мне известно, типа нашего ноу-хау;-) Такие контейнеры используются при реализации LRnLA алгоритмов. Аналог я приводил - четверичное дерево, но оно по другому реализуется (потому что там задачи другие).

А чего тут гуглить то, структтуру и алгоритм я расписал. Профит очевиден как бы - в станд. массиве для доступа к ближ. соседу по вертикали надо прыгнуть на Nx ячеек, при большом массиве это гарантированно другая страница -> задержка на ее подгрузку в кэш. В LR контейнере с весьма высоком вероятностью все ближ. соседи лежат рядом.

Реализацию (не самую удачную, я там за гибкостью гнался) можно глянуть тут http://a-iv.ru/aivlib/include/lrCubeTD.hpp

Общая мысль - делаете массив смещений pos_shift по одной из координат, по второй координате будут те же смещения но умноженные на два. Что бы вычислить индекс для элемента с координатами (x,y) делаете так pos_shift[x]+pos_shift[y]*2

Ну для Вашей задачи можно перейти к смещениям относительно ячейки, они там имеют свои закономерности.

google://spatial indexing/

о, спасибо, не мог правильных ключевых слов найти.