寻找交点
假设我们有一个场景，里面有数百万个可能重叠的边界框，这些边界框的宽度都小于5公里。
我们需要写一个快速的函数，输入参数是经度、纬度和半径，输出结果是一个包含那些边界框ID的列表，这些边界框的起点在输入的参数范围内。
我该如何优雅地解决这个问题呢？
3 个回答
0
这看起来是一个更好、更通用的方法，叫做GiST。
1
PostGIS 是一个开源的地理信息系统（GIS）扩展，专门用于 PostgreSQL 数据库。
它提供了 ST_Intersects 和 ST_Intersection 这两个功能。
如果你感兴趣，可以去看看它们是怎么实现的：
4
这通常是通过一种叫做 R树 的数据结构来实现的。
像 MySQL 或 PostgreSQL 这样的数据库都有地理信息系统（GIS）模块，它们在后台使用 R树来快速找到离地图上某个点近的地点。
根据 维基百科 的介绍：
R树是一种树形数据结构，和 B树有点相似，但主要用于空间访问方法，也就是用来索引多维信息；比如说，地理数据的 (X, Y) 坐标。R树的一个常见实际应用是：“找到离我当前位置 2 公里（1.2 英里）内的所有博物馆”。
这种数据结构通过分割空间，形成层次嵌套的、可能重叠的最小边界矩形（MBR，通常叫做边界框，也就是“矩形”，这就是 R树中“R”的意思）。
优先 R 树（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 模块。