我有一组包含在矩形内的点。我想根据点密度将矩形拆分为子矩形（给出多个子矩形或所需的密度，以最简单的为准）。
分区不必精确（几乎任何比常规网格更好的近似值），但算法必须处理大量点 - 大约。2亿。然而，所需的子矩形数量要少得多（大约 1000 个）。
有谁知道任何可以帮助我完成这项特定任务的算法？
问问题
5059 次
8 回答
2
我认为您正在使用标准的 Kd-tree 或二进制空间分区树。（你可以在维基百科上查到。）
由于您有很多点，您可能希望仅大致划分前几个级别。在这种情况下，您应该随机抽取 200M 个点（可能是 200k 个），然后在子样本的中点（沿较长的轴）拆分整个数据集。如果您实际上是随机选择这些点，那么您错过大量需要细分的点的概率大约为零。
现在你有两个问题，每个问题大约 100M 点。沿着较长的轴划分每个。重复直到您停止抽取子样本并沿整个数据集进行拆分。经过十次广度优先迭代后，您将完成。
如果你有不同的问题——你必须提供沿 X 和 Y 轴的刻度线，并尽可能沿这些刻度线填充网格，而不是对 Kd 树进行不规则分解——获取点的子样本并找到沿每个轴的 0/32、1/32、...、32/32 百分位数。在那里画出你的网格线，然后用你的点填充生成的 1024 元素网格。
于 2010-06-02T18:40:48.853 回答
2
于 2010-06-02T16:32:42.633 回答
2
我想我将从以下内容开始，这与@belisarius 已经提出的内容很接近。如果您有任何其他要求，例如更喜欢“接近方形”的矩形而不是“又长又薄”的矩形，则需要修改这种幼稚的方法。为简单起见，我假设这些点大致是随机分布的。
- 用一条平行于矩形短边并恰好穿过中点的线将您的初始矩形分成 2 部分。
- 计算两个半矩形中的点数。如果它们相等（足够），则转到步骤 4。否则，转到步骤 3。
- 根据半矩形之间的点分布，将线移动以再次均匀。因此，如果第一次切割将点分割为 1/3、2/3，则将线的一半移动到矩形的较重的一半。转到第 2 步。（小心不要被困在此处，以不断递减的步长移动线，首先向一个方向移动，然后再向另一个方向移动。）
- 现在，在第 1 步将每个半矩形传递给对该函数的递归调用。
我希望这足以很好地概述提案。它有局限性：它会产生一些等于 2 的幂的矩形，所以如果这还不够好，请调整它。我已经递归地表达了它，但它是并行化的理想选择。每个拆分创建两个任务，每个任务拆分一个矩形并再创建两个任务。
如果您不喜欢这种方法，也许您可以从一个常规网格开始，其中包含您想要的矩形数量的倍数（可能是 10 - 100 个）。计算每个小矩形中的点数。然后开始将小矩形粘合在一起，直到较小的矩形包含（大约）正确数量的点。或者，如果它足够满足您的要求，您可以将其用作离散化方法并将其与我的第一种方法集成，但仅将切割线放置在小矩形的边界上。这可能会快得多，因为您只需计算每个小矩形中的点一次。
我还没有真正考虑过其中任何一个的运行时间；我偏爱前一种方法，因为我进行了大量并行编程并且拥有大量处理器。
于 2010-06-02T17:07:28.547 回答
2
只是为了理解问题。以下是粗制滥造的，表现不佳，但我想知道结果是否是你想要的>
假设>矩形个数是偶数
假设>点分布明显2D（一行没有大的堆积）
程序>
在任一轴上平分 n/2 次，从每个先前确定的矩形的一端循环到另一端，计算“通过”点，并在每次迭代中存储通过点的数量。计数后，将矩形按每个循环中计数的点一分为二。
那是你想要达到的吗？
于 2010-06-02T16:41:51.940 回答
0
QuadTree 会工作吗？
四叉树是一种树数据结构，其中每个内部节点正好有四个孩子。四叉树最常用于通过递归地将二维空间细分为四个象限或区域来划分二维空间。这些区域可以是正方形或矩形，或者可以具有任意形状。这种数据结构在 1974 年被 Raphael Finkel 和 JL Bentley 命名为四叉树。类似的划分也称为 Q-tree。所有形式的四叉树都有一些共同的特征：
- 它们将空间分解成可适应的细胞
- 每个单元（或存储桶）都有一个最大容量。当达到最大容量时，桶分裂
- 树目录遵循四叉树的空间分解
于 2010-06-02T19:34:04.860 回答
0
于 2010-06-02T18:36:31.980 回答
0
K-means 聚类或Voronoi 图是否适合您尝试解决的问题？
于 2010-06-02T18:40:45.500 回答
0
这看起来像聚类分析。
于 2010-06-02T18:44:41.030 回答