我有一堆多边形和一个粗糙的均匀网格。我想为与统一网格对齐的矩形实现两个不同的范围查询：

1. 矩形是否与任何多边形相交？
2. 给我所有与矩形相交的多边形。

一个简单的数据结构是为每个单元格提供一个指向与单元格重叠的多边形的指针列表。此数据结构适用于第一个范围查询。第二个范围查询似乎不太合适，因为同一个多边形可能会重叠多个单元格，而且我们不想多次报告同一个多边形。一种解决方案是使用std::set<polygon_t*>容器来收集指向由查询传递的多边形的指针。但是，假设我不std::set相信即使我为多个查询重用同一个容器，它也会分配太多内存。（这种不信任可能是没有根据的，所以我应该先明确地尝试一下。）

我想知道如果我用它们的“网格对齐”边界框替换多边形，是否可以更有效地解决问题。在进行范围查询时，边界框左下点的知识应该足以确定该框对应的多边形是否已经被报告。但即使在这种情况下，查询返回的复杂性$m$多边形不会是，因为对于与多边形边界框相交的每个单元格都做了一些工作。我想知道是否创建三个附加列表，其边界框在此单元格中以“x 方向”、“y 方向”和“x 和 y 方向”开始，从而避免这种额外的工作是一个好主意。除了创建新列表之外，我还可以尝试对现有列表进行适当的分区。$O(m)$

一般来说，上面讨论的基于粗略统一网格的数据结构提供了基本恒定的查找时间，但代价是潜在的高内存消耗。这种数据结构的最新技术是什么？有没有办法避免由具有与许多网格单元重叠的巨大边界框的元素引起的潜在内存膨胀？另外，我不喜欢只有简单的数据结构可以直接处理多边形，而更有效的数据结构只能处理多边形的边界框。