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

问题描述

给定一组n个点的飞机，我想preprocess这些点莫名其妙的速度比为O（n ^ 2）（O（n日志（n））的preferably），然后可以回答以下类型的查询怎么N点多在于给定圆心和半径的圆内？不是为O（n）（O（日志（N）preferably）。

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树之分。在每个节点存储包含在该节点的点的数量。然后，当你需要计算涵盖的查找圆点，遍历树，并在节点检查每个分区，如果它是完全外循环，则忽略它，如果它是完全内圆则其数量添加到总的，如果它与圆，递归相交，当你到了叶，检查点（S）的叶子里面围堵。

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（日志（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屋！