快速计算圆内的点数 [英] Count number of points inside a circle fast

问题描述

给定平面上的一组 n 个点，我想以某种方式比 O(n^2) 更快地预处理这些点(最好是 O(nlog(n)))，然后能够回答以下类型的查询有多少 n 个点位于具有给定中心和半径的圆内?"比 O(n) 快(最好是 O(log(n)).

Given a set of n points on plane, I want to preprocess these points somehow faster than O(n^2) (O(nlog(n)) preferably), and then be able to answer on queries of the following kind "How many of n points lie inside a circle with given center and radius?" faster than O(n) (O(log(n) preferably).

你能推荐一些我可以用来解决这个问题的数据结构或算法吗?

Can you suggest some data structure or algorithm I can use for this problem?

我知道这类问题通常可以使用 Voronoi 图来解决，但我不知道如何在这里应用它.

I know that such types of problems are often solved using Voronoi diagrams, but I don't know how to apply it here.

推荐答案

构建一个空间细分结构，如 四叉树 或 KD-tree 的点.在每个节点上存储该节点覆盖的点数.然后，当您需要计算查找圈所覆盖的点时，遍历树并为节点中的每个细分检查它是否完全在圈外，然后忽略它，如果它完全在圈内，则将其计数添加到如果它与圆相交，则总计，递归，当你到达叶子时，检查叶子内的点是否包含.

Build a spatial subdivision structure such as a quadtree or KD-tree of the points. At each node store the amount of points covered by that node. Then when you need to count the points covered by the lookup circle, traverse the tree and for each subdivision in a node check if it is fully outside the circle, then ignore it, if it is fully inside the circle then add its count to the total if it intersects with the circle, recurse, when you get to the leaf, check the point(s) inside the leaf for containment.

这仍然是 O(n) 最坏的情况(例如，如果所有点都位于圆周上)，但平均情况是 O(log(n)).

This is still O(n) worst case (for instance if all the points lie on the circle perimeter) but average case is O(log(n)).

这篇关于快速计算圆内的点数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！