Мотивация:
Я видел описанный алгоритм, и я бы не стал изобретать велосипед, если существует стандартная реализация. Я также узнал, что, если есть реализация scipy / numpy, она обычно намного быстрее, чем что-либо, что я могу использовать в python.
Описание алгоритма
У меня есть большое количество точек на плоскости (несколько миллионов). Начиная с большой рамки, охватывающей все точки, я бы хотел непрерывно подразделять эту ячейку на подполя равной площади. Подразделение продолжается рекурсивно, пока в суббоксе есть не менее 1000 точек. Алгоритм возвращает дерево, которое описывает подразделения и отображение точек на каждый листовой узел дерева.
Как называется этот алгоритм (что-то вроде «разделяй и властвуй»?), И существует ли стандартный способ сделать это, когда дан двумерный массив точек?