空间分割算法 [英] Space partitioning algorithm

问题描述

我有一组其包含在矩形内的点。我想矩形分割成基于点密度subrectangles（给一些subrectangles或所需的密度，取其最容易）。

I have a set of points which are contained within the rectangle. I'd like to split the rectangles into subrectangles based on point density (giving a number of subrectangles or desired density, whichever is easiest).

的划分并不一定准确（几乎所有的近似比常规电网会做），但该算法，以应付大量的点的 - 约。 200百万。 subrectangles的期望数量的但是基本上较低（约1000）。

The partitioning doesn't have to be exact (almost any approximation better than regular grid would do), but the algorithm has to cope with the large number of points - approx. 200 millions. The desired number of subrectangles however is substantially lower (around 1000).

没有人知道任何算法，该算法可以帮我这个特定的任务？

Does anyone know any algorithm which may help me with this particular task?

推荐答案

只是为了理解这个问题。 以下是原油和表现不好，但我想知道，如果结果是你想要什么>

Just to understand the problem. The following is crude and perform badly, but I want to know if the result is what you want>

假设>长方形数是偶数
假设>点分布范围明显2D（在同一行没有什么大的积累）

Assumption> Number of rectangles is even
Assumption> Point distribution is markedly 2D (no big accumulation in one line)

程序>
平分的n / 2倍在任一轴，从一端循环到另一每previously确定矩形计数​​通过点并存储通过点中的每一次迭代的数目。计算一次，平分矩形选择在每个循环计数点。

Procedure>
Bisect n/2 times in either axis, looping from one end to the other of each previously determined rectangle counting "passed" points and storing the number of passed points at each iteration. Once counted, bisect the rectangle selecting by the points counted in each loop.

这就是你想达到什么？

这篇关于空间分割算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！