https://stackoverflow.com/questions/2959564
-
23-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有一组包含在矩形内的点。我想根据点密度将矩形分割成子矩形（给出多个子矩形或所需的密度，以最简单的为准）。
分区不必是精确的（几乎任何比常规网格更好的近似都会做），但算法必须处理大量的点 - 大约。2亿。然而，所需的子矩形数量要少得多（大约 1000）。
有谁知道任何算法可以帮助我完成这个特定的任务？
解决方案
只是为了理解问题。以下是粗略的，表现不佳，但是我想知道结果是否是您想要的>
假设>矩形数量是
假设>点分布是显着的2D（一条线上没有大积累）
过程>
在任一轴上的二次n/2次，从一个先前确定的矩形计数“传递”点的一端循环到另一端，并在每次迭代中存储传递点的数量。计数后，将每个循环中计数的点选择的矩形选择。
那是您想实现的目标吗？
其他提示
我认为，您正在追求标准的KD-Tree或二进制空间分区树。 （您可以在Wikipedia上查找它。）
由于您有很多分数，因此您可能只希望将前几个级别分开。在这种情况下，您应该随机进行200m点的随机示例 - 其中的200k - 并在子样本的中点（沿轴更长）分配完整的数据集。如果您实际选择这些点，那么您会错过需要细分的大量点的概率将大约为零。
现在，您有两个问题约为100m点。沿较长的轴划分。重复直到停止取样并沿整个数据集分开。经过十个宽阔的迭代后，您将完成。
如果您有不同的问题 - 您必须沿X和Y轴提供刻度标记，并尽可能地填充网格，而不是将kd-tree的不规则分解 - 请访问您的点子样本和找到沿每个轴的0/32、1/32，...，32/32％。在那里绘制网格线，然后用您的点填充所得的1024个元素网格。
我想我会从以下内容开始，这与 @belisarius 已经提出的内容很接近。如果您有任何其他要求，例如更喜欢“接近正方形”的矩形而不是“又长又薄”的矩形，您将需要修改这种简单的方法。为了简单起见，我假设这些点近似随机分布。
- 用一条与矩形短边平行并恰好穿过中点的线将您的初始矩形一分为二。
- 计算两个半矩形中的点数。如果它们相等（足够），则转到步骤 4。否则，转至步骤 3。
- 根据半矩形之间的点分布，移动线条以使其再次均匀。因此，如果第一次切割将点分割为 1/3、2/3，则将线移至矩形较重的一半。转到步骤 2。（小心不要被困在这里，先朝一个方向逐渐减小步长移动线路，然后再朝另一个方向移动。）
- 现在，在步骤 1 中将每个半矩形传递给该函数的递归调用。
我希望这足以很好地概述该提案。它有局限性：它会产生一些等于 2 的幂的矩形，所以如果这还不够好，请调整它。我已经用递归的方式表达了它，但它对于并行化来说是理想的。每次分割都会创建两个任务，每个任务分割一个矩形并再创建两个任务。
如果您不喜欢这种方法，也许您可以从常规网格开始，其中包含您想要的矩形数量的倍数（也许是 10 - 100 个）。计算每个小矩形中的点数。然后开始将小矩形粘合在一起，直到较小的矩形包含（大约）正确数量的点。或者，如果它足够好地满足您的要求，您可以使用它作为离散化方法并将其与我的第一种方法集成，但仅将切割线沿着小矩形的边界放置。这可能会快得多，因为您只需对每个小矩形中的点进行一次计数。
我还没有真正考虑过其中任何一个的运行时间；我更喜欢前一种方法，因为我进行了大量的并行编程并且拥有大量的处理器。
看起来像 聚类分析.
会 Quadtree 工作？
Quadtree是一个树数据结构，每个内部节点都有四个孩子。四分之一最常用于通过将其递归细分为四个象限或区域来划分二维空间。区域可以是正方形的或矩形的，也可以具有任意形状。这种数据结构在1974年被拉斐尔·芬克尔（Raphael Finkel）和JL Bentley命名为Quadtree。类似的分区也被称为Q-Tree。所有形式的四分之一都有一些共同的特征：
- 他们将空间分解为适应性的细胞
- 每个单元格（或桶）具有最大容量。当达到最大容量时，桶形拆分
- 树目录遵循Quadtree的空间分解
