快速算法以查找所有在矩形内的点

Question

给定一个在2D空间中的不同点集，以及一个矩形（所有四个点的坐标，边与xy轴平行），如何快速找到哪些点在矩形内？

我不感兴趣的基本解决方案是遍历所有点并查看哪个点在矩形内。我要找的是一种算法，它可以为我提供每个矩形快速查询时间。

我不在乎预处理步骤花费多少时间，我关心的是，在处理完我的数据后，我能获得一个有用的结构，该结构可以为我提供每个矩形的快速查询时间。

例如，我知道我可以在O(logN)的时间内计算矩形内的点数。这是因为我在开始时进行了大量的重处理，然后每次用新的矩形查询已经处理好的数据，并在logN时间内得到新的点数。 我正在寻找一种类似的算法来查找实际的点，而不仅仅是它们的数量。

- Alex

---

长方形是否旋转？如果没有，它就是一个简单的AABB检查：“如果（p.x> = rect.x && px。<= rect.x + rect.width）{...}” - Draco18s no longer trusts SE

请查看此帖子：https://dev59.com/b2kv5IYBdhLWcg3w6k5Q - Alex

我不明白你是如何提出在LogN时间内完成的。对于N个点，你至少需要遍历所有N个点一次。最好的时间复杂度是O(N)。 - displayName

我正在寻找快速查询时间。也就是说，我的点是给定和固定的。从一个查询到另一个查询所发生的变化是矩形。我希望每个矩形的查询时间都很快（预处理步骤可能需要多长时间都可以，因为这只需要做一次，我关心的是查询时间）。 - Alex

复杂度至少为O(Log N+K)，其中K是报告的点数；第二项可能超过第一项。 - user1196549

Answer 1

一个经典的答案是使用kD-tree(k维树，此处为2D-tree)。

如果你的点分布足够均匀，还可以尝试使用网格来进行简单的替代。

为一个正方形网格选择一个单元大小(如果问题是非各向同性的，则使用一个矩形网格)。将每个点分配到包含它的网格单元中，并存储在一个链表中。当你执行一个查询时，找到所有与矩形重叠的单元格，并扫描它们以遍历它们的列表。对于被部分覆盖的单元格，你需要执行点-矩形测试。

大小的选择很重要：太大可能导致仍需要测试太多的点；太小可能导致有太多的空单元格。

- user1196549

Answer 2

您正在寻找 kd-tree范围搜索 或范围查询。

• Quadtree（或八叉树或16叉树...）在点集不断变化，但您预期分布是均匀的情况下表现更好。无需进一步平衡步骤，因为树的结构是固定的。
• kd-tree 在固定的点集上表现更好，即使分布不均匀。当点集改变时，进行自平衡操作很难（但不是不可能）。
• AABB树（或fat AABB树）提供了一种快速检查重叠形状（而不仅是点）的方法。AABB树偶尔需要一些平衡处理。当包含不停移动的对象时，常见的方法是使用“fat AABB-s”，这样您就不必在每帧中更新树。
• 只按一个轴排序并使用二分搜索（类似于abelenky建议的那样，但我认为没有必要进行第二次二分搜索）是一种简单而优雅的解决方案，但当例如按X轴排序时，所有点都在与Y平行的一条线上时，它将变慢。您必须对由X进行二进制搜索匹配的点进行线性过滤。时间复杂度是最坏情况下O(n)，但这种最坏情况经常发生。

所有这些算法的平均查询时间为O(log n + k)，其中k是匹配点的数量。

像Yves建议的那样进行网格化可以在O(k)时间内执行范围搜索，但仅当查询矩形的大小受限时。这是他们在粒子模拟中经常采用的方法。即使输入集未受到限制，也可以使用网格化--只需基于网格坐标的哈希值创建固定计数的桶即可。但是，如果查询矩形可以是任意大小，则网格化是不可行的。

- Tamas Hegedus

---

你有一个快速链接可以解释一下你的第二点吗？我直觉上会期望相反的结果。 - Jens Schauder

@JensSchauder 不，我没有，这只是凭直觉，有时需要重新平衡树的事实支持。实际上，重新平衡树可能不需要太多时间。我会进行一些研究并在某个时候测量这些方法。 - Tamas Hegedus

哦，我可能误解了你的意思。我理解为kd树在固定点集上比四叉树表现更好。但现在我认为你的意思是相对于不断变化的点集而言更优秀？ - Jens Schauder

@JensSchauder 很抱歉没有表达清楚。我的意思是当你有一组固定的点时，kd树更好。想象一下在一个大的搜索空间中有一组聚类点集。kd树的空间划分适应于聚类，而四叉树需要将整个搜索空间分成四个部分，直到到达聚类为止。这意味着四叉树会更深。 - Tamas Hegedus

@JensSchauder 但是根据http://cstheory.stackexchange.com/questions/8470/why-would-one-ever-use-an-octree-over-a-kd-tree，深度只是一个观点。子空间的长宽比可能更差，使用kd-trees。 - Tamas Hegedus

链接已经损坏。 - codename44

Answer 3

除了其他答案，您还可以研究莫顿码（z-order曲线排序）。

在您的情况下，这是静态数据，您甚至可以将整个点数据表示为数组。

https://en.wikipedia.org/wiki/Z-order_curve

这篇论文还涉及到一些比较复杂的"多维访问方法"的时间线 -- http://www.cc.gatech.edu/computing/Database/readinggroup/articles/p170-gaede.pdf。

- hkrish

Answer 4

你可以将点分组成扇形。如果一个扇形完全在或完全不在给定的矩形内，那么其中所有的点也都在或不在。如果一个扇形部分在矩形内，则需要搜索该扇形中的点以检查它们是否在矩形内，时间复杂度为O(n)。可以尝试使用k-d树搜索。

- Dialecticus

Answer 5

我认为你应该将你的点存储在一个四叉树中。虽然我还没有详细研究过，但它应该允许基本上执行类似于二分查找的操作，直接得到在矩形内部的点。

如果你的点是聚集的，即存在包含许多点的小区域和其他几乎没有或非常少的点的区域，那么R树可能会更好。

我认为运行时复杂度应该是O(logN)。

- Jens Schauder