假设存在数百万个宽度不超过 5 公里的可变尺寸的潜在重叠边界框。
使用参数 findIntersections(Longitude,Latitude,Radius) 创建一个快速函数，输出是这些边界框 ID 的列表，其中每个边界框原点位于函数参数维度的周长内。
如何优雅地解决这个问题？
最佳答案
这通常使用 R-tree 来完成数据结构
像 mysql 或 postgresql 这样的数据库具有 GIS 模块，这些模块在底层使用 r 树来快速检索 map 上某个点附近一定范围内的位置。
来自http://en.wikipedia.org/wiki/R-tree :
R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods, i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 kilometres (1.2 mi) of my current location".
The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (MBRs, otherwise known as bounding boxes, i.e. "rectangle", what the "R" in R-tree stands for).
Priority R-Tree (PR-tree)是一个变体，其最大运行时间为:
"O((N/B)^(1-1/d)+T/B) I/Os, where N is the number of d-dimensional (hyper-)
rectangles stored in the R-tree, B is the disk block size, and T is the output
size."
实际上，大多数实际查询的平均案例运行时间要快得多。
仅供引用，除了发布的其他很棒的代码之外，还有一些很酷的东西，例如 SpatiaLite和 SQLite R-tree module
关于python - 寻找交叉点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2062325/