Python中用于二维范围计数查询的数据结构
我需要一种数据结构，用来进行二维范围计数查询（也就是说，想知道在一个给定的矩形里有多少个点）。
我觉得最好的选择是范围树（它可以在对数平方的时间内进行计数，经过一些优化后甚至可以做到对数时间）。这样听起来不错吗？有没有人知道有没有现成的Python实现，还是我得自己写一个？
1 个回答
2
可以查看 scipy.spatial.KDTree 这个链接，里面有一种实现方式。
还有一种实现方式，虽然不那么通用，但在某些情况下可能更有用，特别是如果你有特定的想法的话。这种方式是使用 shapelib 的四叉树。你可以看看 这个博客 和相应的 PyPi 上的包。
可能还有其他的实现方式，但这两个是我用过的...