algorithm - 范围搜索算法，用于查询给定区域中二维平面中的形状

Question

一般问题陈述：

设计画布形状选择引擎

鉴于：

2D 平面上的任意凸形。（说由 std::vector < IShape* > 表示，IShape 有 getBBox() 成员）

问题：

查找并返回给定矩形区域内的形状集合/子集。

（在这个特定的例子中应该返回形状 A 和 B ）

我知道这个典型的范围范围搜索/范围查询问题，但是“经典”示例是指在给定区域中搜索点，以说明如何使用 kdtree 来解决问题。

我不知道如何“扩展”算法来处理形状。我更多的是寻找想法而不是确切的实施。

（我不考虑对每个形状进行简单的循环以查看是否在给定区域内或之外）

Answer 1

使用边界框，您可以很容易地测试一个形状是否在选择范围内（也就是说，如果所有四个角都在里面）。

要将这个问题简化为“经典”问题，只需将每个形状替换为该形状边界框内的一个随机点（例如左上角）。通过这样做，您可能会获得比您想要的更多的形状（在您的示例中，您将获得右下角的矩形）但这不是问题，因为您可以很容易地检查候选形状是否确实在选择范围内。

Answer 2

KD-Tree 并不适合这种类型的搜索。正如@Thomash 建议的那样，为每个形状创建 AABB（轴对齐边界框）很有用。然后你可以把它们放在类似四叉树或R-Tree的东西中。这些允许您存储 AABB，然后轻松查询与查询矩形相交的所有 AABB。

对于从查询中返回的每个 AABB，您需要检查该形状是否实际上与查询矩形相交（与 AABB 相交显然不能保证与 AABB 内的形状相交）。

如果您使用的是 Java，请查看我对各种空间索引的实现。