设计画布上的形状选择引擎
2D平面上的任意凸形。 （比如用std :: vector <Shape *>表示，Shape有getBBox（）成员）
查找并返回给定矩形区域内的形状的集合/子集。
（在此特定示例中应返回形状A和B）
我知道这个典型的范围范围 - 搜索/范围查询问题，但“经典”示例是指在给定区域中搜索点以说明如何使用kdtree来解决问题。
我无法弄清楚如何“扩展”算法来改变形状。我更关注的是想法而不是确切的实现。
（我不考虑在每个形状上进行微不足道的循环，以查看是否进入或离开给定区域）
使用边界框，您可以非常轻松地测试形状是否在选区内（即如果所有四个角都在内部）。
要将此问题简化为“经典”问题，只需将此形状的边界框内的随机点替换为每个形状（例如，左上角）。通过这样做，您可能会得到比您想要的更多的形状（使用您的示例，您将获得右下方的矩形）但是这不是问题，因为您可以非常轻松地检查候选形状是否确实在选择内。
KD-Tree不适合此类搜索。正如@Thomash所建议的那样，为每个形状创建AABB（轴对齐的边界框）很有用。然后你可以把它们放在像quadtree或R-Tree这样的东西上。这些允许您存储AABB，然后轻松查询与查询矩形相交的所有AABB。
对于从查询中返回的每个AABB，您需要检查形状是否实际上与查询矩形相关（与AABB相交显然不能保证与AABB内部的形状相交）。
如果您使用的是Java，请查看各种空间索引的my implementations。