Как эффективно разделить 2D-пространство на ячейки так, чтобы каждая ячейка содержала не более K точек?

Question

У меня есть набор данных 2D точек (из них ~ 500 тыс.), По которым я хотел бы провести какой-то анализ числа квадратов. Основа подсчета квадратов состоит в том, чтобы разделить ваше 2D-пространство на регулярную сетку (каждая ячейка имеет размер SxS) и подсчитать количество точек в каждой ячейке.

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

Я сделал следующее: я начинаю со всего пространства и делю его на 4 ячейки («разрезая» каждое измерение пополам). Затем я подсчитываю количество точек в каждой ячейке. Для тех, которые содержат более K баллов, я делю их снова и т. Д., Пока я не закончу.

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

(Сейчас я просто использую «условную индексацию» в Python: points = points[points[,1] > x1 and points[,1] <= x2 and points[,2] > y1 and points[,2] <= y2,])

Кроме того, у вас может быть другая идея о том, как я мог бы построить свою сетку?

РЕДАКТИРОВАТЬ: Другими словами, какую структуру данных я мог бы использовать для быстрого подсчета (и получения) точек, которые попадают в данный прямоугольник ((x1, y1), (x2, y2))?

Answer 1

Это не завершено, но это может указать вам правильное направление.

Вместо того, чтобы начинать с большого и становиться маленьким, начинайте с малого и становитесь большим.

Разделите ваше пространство, скажем, на 100x100 клеток. Посчитайте число в каждой ячейке (это точно O (n), вы посчитаете каждую ячейку один раз.)

С этого момента вам не нужно считать клетки. Вы можете создать CellGroups, чтобы подсчитать, какие ячейки у него есть, и оттуда я бы использовал алгоритм для объединения ячеек в CellGroups.

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

while(true) {
    take the smallest cellgroup
    compare it to each other cellgroup starting with the second smallest
    go up the list until you find two adjecent cell groups
    if you find a match
        merge them
        update the cellgroup size rankings
        repeat the process (continue the while(true)
    otherwise
        break out, you're done merging cells

}

Answer 2

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

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

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