Есть площадь заданного размера, на ней указаны N точек, и даны их координаты. Нужно научиться быстро отвечать на запрос сколько точек находится в квадрате. Моя идея заключается в том, чтобы поделить область на sqrt(N) * sqrt(N) меньших областей, преподсчетом решить задачу на них, по данной матрице построить матрицу частичных сумм, и в итоге просто после поступления запроса (координат квадрата) добавлять к подсчитанным точкам из маленьких квадратов, рассмотренные отдельно, вручную. Что-то такое:
int sqrt_count = std::ceil(std::sqrt(points_num));
int rect_size = std::ceil(lim / sqrt_count);
matrix2d ppr = matrix2d(sqrt_count, std::vector<int>(sqrt_count, 0)); // points_per_rect
for (int i = 0; i < points_num; ++i)
{
++ppr[points[i].X / rect_size][points[i].Y / rect_size];
}
matrix2d blocks = matrix2d(sqrt_count + 1, std::vector<int>(sqrt_count + 1, 0));
for (int i = 1; i < sqrt_count; ++i)
{
for (int j = 1; j < sqrt_count; ++j)
{
blocks[i][j] = blocks[i][j - 1] + blocks[i - 1][j] - blocks[i - 1][j - 1] + ppr[i - 1][j - 1];
}
}
Но проблема с которой я столкнулся, это то что я не пойму, как теперь мне узнать, какие конкретно точки принадлежат какому из этих квадратов. Допустим поступает запрос, где используются два цельных маленьких квадрата, и один наполовину. Два цельных я могу просто добавить не считая, а для того что наполовину, мне нужно проверить какие точки из него входят, а какие нет. Хранить отдельно те точки что я добавляю для каждого квадратика очень накладно. В обычной одномерной sqrt декомпозиции все просто, ведь там преобразовывается индекс, а как быть здесь?
Точка с координатами x,y
попадает в ячейку с индексами [y / cellHeight], [x / cellWidth]
- это уже сделано
А относительно хранения - трёхмерный вектор должен содержать векторы точек в каждой ячейке, в другом месте их хранить уже не нужно. При обработке каждой точки добавляем её в вектор с указанными индексами.
Вот пример похожей задачи на Delphi
Grid: array[0..63, 0..63] of TArray<Integer>;
хранит индексы точек, но ничего не мешает держать там сами точки
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
После компилиции выдает ошибку "Это объявление не содержит класс хранения или спецификатор типа"
Реализую протокол RTP, не могу разобраться с RTP Payload Format for H264 Video а если точнее быть то с первыми 4 байтами в CSRC
3дравствуйте, пытаюсь установить библиотеку BLAS в MVS, делаю все по инструкции, остановился на одном моменте(скриншот приложил)