<p>所描述的问题是一个可以使用<a href="http://en.wikipedia.org/wiki/K-d_tree" rel="nofollow noreferrer">K-D tree</a>有效解决的典型问题。在</p>
<p>k-d树(k-dimensional tree的缩写)是一种用于在k维空间中组织点的空间划分数据结构。在你的例子中k等于2。它基本上是一个二叉搜索树,在其中,您可以在每个级别上进行的比较之间进行交替。例如,如果在某个级别上,根据点的x坐标比较点,则在下一个级别上,将使用y坐标比较点。在</p>
<p>因此在树中插入一个点可以在<code>O(logN)</code>中完成。这个图像可以演示插入。因此,在数据结构中插入N个点将花费<code>O(NlogN)</code>时间。在</p>
<p><img src="https://i.stack.imgur.com/Ae6ti.png" alt=""/>
<sub>从<a href="http://coursera.cs.princeton.edu/algs4/assignments/kdtree.html" rel="nofollow noreferrer">http://coursera.cs.princeton.edu/algs4/assignments/kdtree.html</a>拍摄的图像</sub></p>
<p>若要查找给定查询矩形中包含的所有点,请从根开始,并使用以下修剪规则递归搜索两个子树中的点:如果查询矩形与节点对应的矩形不相交,则无需探索该节点(或其子树)。只有当子树可能包含查询矩形中包含的点时,才会搜索子树。在</p>
<p>因此,下面的<a href="http://ideone.com/IMEPCs" rel="nofollow noreferrer">running Java code</a>以最佳的方式解决了这个问题。对于矩形中包含的点的每个查询通常可以在<code>O(R+logN)</code>时间内得到回答。其中R是范围内的点数,N是点数。然而,对于病理数据,最坏的运行时间是<code>O(R + sqrt(N))</code>。在</p>
<pre><code> void run(){
Scanner in = new Scanner(System.in);
int numQueries = in.nextInt();
Point2D root = null;
for(int i=0; i<numQueries; i++){
int type = in.nextInt();
if(type == 0){ // Add a point
double x = in.nextDouble();
double y = in.nextDouble();
root = addPoint(root, x, y, true);
}else{
double x1 = in.nextDouble();
double y1 = in.nextDouble();
double x2 = in.nextDouble();
double y2 = in.nextDouble();
System.out.println("the points in between the rectange with end points " +
new Point2D(x1, y1) + " and " + new Point2D(x2, y2) + " are :");
printPointsInRange(root, x1, y1, x2, y2, true);
}
}
}
// prints all points in the rectangle which has top left coordinates
// (x1, y1) and bottom right coordinates (x2, y2)
void printPointsInRange(Point2D root,
double x1, double y1,
double x2, double y2, boolean vertical){
if(root==null){
return;
}
double x = root.x;
double y = root.y;
boolean outsideRange = Double.compare(x, x1)<0 ||
Double.compare(x, x2)>0 ||
Double.compare(y, y1)>0 ||
Double.compare(y, y2)<0;
if(!outsideRange){
System.out.println(root);
}
if(vertical){
if(Double.compare(x, x1)<=0){
// root lies left of left boundary or on the boundary
printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
}else if(Double.compare(x, x2)>0){
// root lies right of right boundary
printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
}else if(Double.compare(x, x2)==0){
// root lies on right boundary
printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
}else{
// root lies in between x1 and x2
printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
}
}else{
if(Double.compare(y, y2)<=0){
// root lies below bottom boundary or on bottom boundary
printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
}else if(Double.compare(y, y1)>0){
// root lies above top boundary
printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
}else if(Double.compare(y, y1)==0){
// root lies on top boundary
printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
}else{
// root lies in between y1 and y2
printPointsInRange(root.left, x1, y1, x2, y2, !vertical);
printPointsInRange(root.right, x1, y1, x2, y2, !vertical);
}
}
}
Point2D addPoint(Point2D root, double x, double y, boolean vertical){
if(root==null){
return new Point2D(x, y);
}
if(vertical){ // vertical division
double compare = Double.compare(root.x, x);
if(compare<0){ // point is on left of root
root.left = addPoint(root.left, x, y, !vertical);
}else{ // point is on right of root or on root's x
root.right = addPoint(root.right, x, y, !vertical);
}
}else{
double compare = Double.compare(y, root.y);
if(compare>0){ // point is above the root
root.right = addPoint(root.right, x, y, !vertical);
}else{ // point is below the root or on root's y
root.left = addPoint(root.left, x, y, !vertical);
}
}
return root;
}
</code></pre>