blocks|key|1486101|text|也许来自Stony-Brook算法存储库的Nearest+Neighbor+Search和KD-trees可以提供帮助。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1486102|entityMap|0|LINK|mutability|MUTABLE|url|http://www.cs.sunysb.edu/~algorith/files/nearest-neighbor.shtml|1|http://www.cs.sunysb.edu/~algorith/files/kd-trees.shtml^0|L|N|0|19|8|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

Maybe <a href="http://www.cs.sunysb.edu/~algorith/files/nearest-neighbor.shtml" rel="nofollow noreferrer">Nearest Neighbor Search</a> and <a href="http://www.cs.sunysb.edu/~algorith/files/kd-trees.shtml" rel="nofollow noreferrer">KD-trees</a> from the Stony-Brook algorithm repository can help.

blocks|key|1486175|text|在Algorithms+in+a+Nutshell一书中，有一个用java编写的kd树实现，以及一些变体。所有的代码都在oreilly.com上，这本书本身也向你介绍了算法，这样你就可以自己构建一个。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1486176|entityMap|0|LINK|mutability|MUTABLE|url|http://oreilly.com/catalog/9780596516246/|1|http://examples.oreilly.com/9780596516246/^0|1|O|0|1O|B|1|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]|$A|R|B|S|1|T]]|C|$]]|$1|D|3|-4|5|6|7|U|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]|L|$5|G|H|I|C|$J|M]]]]

In the book <a href="http://oreilly.com/catalog/9780596516246/" rel="noreferrer">Algorithms in a Nutshell</a> there is a kd tree implementation in java along with a few variations. All of the code is on <a href="http://examples.oreilly.com/9780596516246/" rel="noreferrer">oreilly.com</a> and the book itself also walk you through the algorithm so you could build one yourself.

blocks|key|1701322|text|我已经成功地实现了Levy教授的found+here。我知道您正在寻找一个经过更多生产认证的实现，所以这可能不是一个很好的选择。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1701323|但是请过路人注意，我已经在我的照片拼接项目中使用它一段时间了，没有任何问题。不能保证，但总比没有好:)|1701324|entityMap|0|LINK|mutability|MUTABLE|url|https://simondlevy.academic.wlu.edu/software/kd/^0|M|4|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

I've had success with Professor Levy's implementation found <a href="https://simondlevy.academic.wlu.edu/software/kd/" rel="nofollow noreferrer">here</a>. I realize you're looking for a more production-certified implementation so this is probably not a good fit. 

However note to any passers-by, I've been using it for a while now in my photomosaic project with no issues. No guarantee but better than nothing :)

blocks|key|1701363|text|给未来的探索者。Java-ml库有一个运行良好的kd-tree实现。http://java-ml.sourceforge.net/|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1701364|entityMap|0|LINK|mutability|MUTABLE|url|http://java-ml.sourceforge.net/^0|Y|V|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

for future seekers. Java-ml library has a kd-tree implementation that work fine.
<a href="http://java-ml.sourceforge.net/">http://java-ml.sourceforge.net/</a>

blocks|key|1701395|text|我创建了一个KD-Tree实现，作为离线反向地理编码库的一部分|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1701396|https://github.com/AReallyGoodName/OfflineReverseGeocode|offset|length|1701397|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|1K|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|N|8|@]|9|@$D|O|E|P|1|Q]]|A|$]]|$1|F|3|-4|5|6|7|R|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|C]]]]

I created a KD-Tree implementation as part of an offline reverse geocoding library

<a href="https://github.com/AReallyGoodName/OfflineReverseGeocode" rel="nofollow noreferrer">https://github.com/AReallyGoodName/OfflineReverseGeocode</a>

blocks|key|1486379|text|还有JTS+Topology+Suite|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1486380|KdTree实现只提供范围搜索(无最近邻)。|1486381|如果最近的邻居是你喜欢的，看看STRtree|1486382|entityMap|0|LINK|mutability|MUTABLE|url|http://www.vividsolutions.com/jts/jtshome.htm|1|http://www.vividsolutions.com/jts/javadoc/com/vividsolutions/jts/index/strtree/package-summary.html^0|2|I|0|0|0|F|7|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]|P|$5|K|L|M|C|$N|Q]]]]

There is also <a href="http://www.vividsolutions.com/jts/jtshome.htm" rel="nofollow" title="JTS Topology Suite">JTS Topology Suite</a>

The KdTree implementation only provides range search (no nearest-neighbors).

If nearest-neighbor is your thing look at <a href="http://www.vividsolutions.com/jts/javadoc/com/vividsolutions/jts/index/strtree/package-summary.html" rel="nofollow">STRtree</a>

blocks|key|1701505|text|你是对的，没有那么多网站有java的kd实现！无论如何，kd树基本上是一个二进制搜索树，通常每次都会计算该维度的中位数。下面是一个简单的KDNode，无论是最近邻方法还是完整实现，请看一下这个github项目。这是我能给你找到的最好的了。希望这对你有帮助。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1701506|private+class+KDNode+{
++++KDNode+left;
++++KDNode+right;
++++E+val;
++++int+depth;
++++private+KDNode(E+e,+int+depth){
++++this.left+=+null;
++++this.right+=+null;
++++this.val+=+e;
++++this.depth+=+depth;
}|code-block|syntax|javascript|1701507|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/aerlinn/traffic/blob/8395c15b9a028ec06c394f1cab1b11b18749f9ce/src/edu/brown/cs32/cjm5/stars/KDTree.java^0|2O|6|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

You are correct, there are not that many sites with kd implementation for java! anyways, kd tree is basically a binary search tree which a median value typically is calculated each time for that dimension. Here is simple KDNode and in terms of nearest neighbor method or full implementation take a look at this <a href="https://github.com/aerlinn/traffic/blob/8395c15b9a028ec06c394f1cab1b11b18749f9ce/src/edu/brown/cs32/cjm5/stars/KDTree.java" rel="nofollow">github</a> project. It was the best one I could find for you. Hope this helps you.

<pre><code>private class KDNode {
 KDNode left;
 KDNode right;
 E val;
 int depth;
 private KDNode(E e, int depth){
 this.left = null;
 this.right = null;
 this.val = e;
 this.depth = depth;
}
</code></pre>

blocks|key|1486463|text|package+kdtree;

class+KDNode{
++++KDNode+left;
++++KDNode+right;
++++int+[]data;

++++public+KDNode(){
++++++++left=null;
++++++++right=null;
++++}

++++public+KDNode(int+[]x){
++++++++left=null;
++++++++right=null;
++++++++data+=+new+int[2];
++++++++for+(int+k+=+0;+k+<+2;+k%2B%2B)
++++++++++++data[k]=x[k];
++++}
}
class+KDTreeImpl{
++++KDNode+root;
++++int+cd=0;
++++int+DIM=2;

++++public+KDTreeImpl()+{
++++++++root=null;
++++}

++++public+boolean+isEmpty(){
++++++++return+root+==+null;
++++}

++++public+void+insert(int+[]x){
++++++++root+=+insert(x,root,cd);
++++}
++++private+KDNode+insert(int+[]x,KDNode+t,int+cd){
++++++++if+(t+==+null)
++++++++++++t+=+new+KDNode(x);
++++++++else+if+(x[cd]+<+t.data[cd])
++++++++++++t.left+=+insert(x,+t.left,+(cd%2B1)%25DIM);
++++++++else
++++++++++++t.right+=+insert(x,+t.right,+(cd%2B1)%25DIM);
++++++++return+t;
++++}

++++public+boolean+search(int+[]data){
++++++++return+search(data,root,0);
++++}

++++private+boolean+search(int+[]x,KDNode+t,int+cd){
++++++++boolean+found=false;
++++++++if(t==null){
++++++++++++return+false;
++++++++}
++++++++else+{
++++++++++++if(x[cd]==t.data[cd]){
++++++++++++++++if(x[0]==t.data[0]+&&+x[1]==t.data[1])+
++++++++++++++++return+true;
++++++++++++}else+if(x[cd]<t.data[cd]){
++++++++++++++++found+=+search(x,t.left,(cd%2B1)%25DIM);
++++++++++++}else+if(x[cd]>t.data[cd]){
++++++++++++++++found+=+search(x,t.right,(cd%2B1)%25DIM);
++++++++++++}
++++++++++++return+found;
++++++++}
++++}

++++public+void+inorder(){
++++++++inorder(root);
++++}
++++private+void+inorder(KDNode+r){
++++++++if+(r+!=+null){
++++++++++++inorder(r.left);
++++++++++++System.out.print("("%2Br.data[0]%2B","%2Br.data[1]+%2B")+");
++++++++++++inorder(r.right);
++++++++}
++++}
++++public+void+preorder()+{
++++++++preorder(root);
++++}
++++private+void+preorder(KDNode+r){
++++++++if+(r+!=+null){
++++++++++++System.out.print("("%2Br.data[0]%2B","%2Br.data[1]+%2B")+");
++++++++++++preorder(r.left);+++++++++++++
++++++++++++preorder(r.right);
++++++++}
++++}
++++/*+Function+for+postorder+traversal+*/
++++public+void+postorder()+{
++++++++postorder(root);
++++}
++++private+void+postorder(KDNode+r)+{
++++++++if+(r+!=+null){
++++++++++++postorder(r.left);+++++++++++++
++++++++++++postorder(r.right);
++++++++++++System.out.print("("%2Br.data[0]%2B","%2Br.data[1]+%2B")+");
++++++++}
++++}
}
public+class+KDTree+{

++++/**
+++++*+@param+args+the+command+line+arguments
+++++*/
++++public+static+void+main(String[]+args)+{
++++++++//+TODO+code+application+logic+here
++++++++KDTreeImpl+kdt+=+new+KDTreeImpl();
++++++++int+x[]+=+new+int[2];
++++++++x[0]+=+30;
++++++++x[1]+=+40;
++++++++kdt.insert(x);

++++++++x[0]+=+5;
++++++++x[1]+=+25;
++++++++kdt.insert(x);

++++++++x[0]+=+10;
++++++++x[1]+=+12;
++++++++kdt.insert(x);

++++++++x[0]+=+70;
++++++++x[1]+=+70;
++++++++kdt.insert(x);

++++++++x[0]+=+50;
++++++++x[1]+=+30;
++++++++kdt.insert(x);
++++++++System.out.println("Input+Elements");
++++++++System.out.println("(30,40)+(5,25)+(10,12)+(70,70)+(50,30)\n\n");
++++++++System.out.println("Printing+KD+Tree+in+Inorder");
++++++++kdt.inorder();
++++++++System.out.println("\nPrinting+KD+Tree+in+PreOder");
++++++++kdt.preorder();
++++++++System.out.println("\nPrinting+KD+Tree+in+PostOrder");
++++++++kdt.postorder();
++++++++System.out.println("\nsearching...............");
++++++++x[0]=40;x[1]=40;
++++++++System.out.println(kdt.search(x));
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1486464|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>package kdtree;

class KDNode{
 KDNode left;
 KDNode right;
 int []data;

 public KDNode(){
 left=null;
 right=null;
 }

 public KDNode(int []x){
 left=null;
 right=null;
 data = new int[2];
 for (int k = 0; k &lt; 2; k++)
 data[k]=x[k];
 }
}
class KDTreeImpl{
 KDNode root;
 int cd=0;
 int DIM=2;

 public KDTreeImpl() {
 root=null;
 }

 public boolean isEmpty(){
 return root == null;
 }

 public void insert(int []x){
 root = insert(x,root,cd);
 }
 private KDNode insert(int []x,KDNode t,int cd){
 if (t == null)
 t = new KDNode(x);
 else if (x[cd] &lt; t.data[cd])
 t.left = insert(x, t.left, (cd+1)%DIM);
 else
 t.right = insert(x, t.right, (cd+1)%DIM);
 return t;
 }

 public boolean search(int []data){
 return search(data,root,0);
 }

 private boolean search(int []x,KDNode t,int cd){
 boolean found=false;
 if(t==null){
 return false;
 }
 else {
 if(x[cd]==t.data[cd]){
 if(x[0]==t.data[0] &amp;&amp; x[1]==t.data[1]) 
 return true;
 }else if(x[cd]&lt;t.data[cd]){
 found = search(x,t.left,(cd+1)%DIM);
 }else if(x[cd]&gt;t.data[cd]){
 found = search(x,t.right,(cd+1)%DIM);
 }
 return found;
 }
 }

 public void inorder(){
 inorder(root);
 }
 private void inorder(KDNode r){
 if (r != null){
 inorder(r.left);
 System.out.print("("+r.data[0]+","+r.data[1] +") ");
 inorder(r.right);
 }
 }
 public void preorder() {
 preorder(root);
 }
 private void preorder(KDNode r){
 if (r != null){
 System.out.print("("+r.data[0]+","+r.data[1] +") ");
 preorder(r.left); 
 preorder(r.right);
 }
 }
 /* Function for postorder traversal */
 public void postorder() {
 postorder(root);
 }
 private void postorder(KDNode r) {
 if (r != null){
 postorder(r.left); 
 postorder(r.right);
 System.out.print("("+r.data[0]+","+r.data[1] +") ");
 }
 }
}
public class KDTree {

 /**
 * @param args the command line arguments
 */
 public static void main(String[] args) {
 // TODO code application logic here
 KDTreeImpl kdt = new KDTreeImpl();
 int x[] = new int[2];
 x[0] = 30;
 x[1] = 40;
 kdt.insert(x);

 x[0] = 5;
 x[1] = 25;
 kdt.insert(x);

 x[0] = 10;
 x[1] = 12;
 kdt.insert(x);

 x[0] = 70;
 x[1] = 70;
 kdt.insert(x);

 x[0] = 50;
 x[1] = 30;
 kdt.insert(x);
 System.out.println("Input Elements");
 System.out.println("(30,40) (5,25) (10,12) (70,70) (50,30)\n\n");
 System.out.println("Printing KD Tree in Inorder");
 kdt.inorder();
 System.out.println("\nPrinting KD Tree in PreOder");
 kdt.preorder();
 System.out.println("\nPrinting KD Tree in PostOrder");
 kdt.postorder();
 System.out.println("\nsearching...............");
 x[0]=40;x[1]=40;
 System.out.println(kdt.search(x));
 }
}
</code></pre>

blocks|key|1701570|text|这是KD-Tree的完整实现，我使用了一些库来存储点和矩形。这些库是免费提供的。可以使用这些类来创建自己的类来存储点和矩形。请分享您的反馈。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1701571|import+java.util.ArrayList;
import+java.util.List;
import+edu.princeton.cs.algs4.In;
import+edu.princeton.cs.algs4.Point2D;
import+edu.princeton.cs.algs4.RectHV;
import+edu.princeton.cs.algs4.StdDraw;
public+class+KdTree+{
++++private+static+class+Node+{
++++++++public+Point2D+point;+//+the+point
++++++++public+RectHV+rect;+//+the+axis-aligned+rectangle+corresponding+to+this
++++++++public+Node+lb;+//+the+left/bottom+subtree
++++++++public+Node+rt;+//+the+right/top+subtree
++++++++public+int+size;
++++++++public+double+x+=+0;
++++++++public+double+y+=+0;
++++++++public+Node(Point2D+p,+RectHV+rect,+Node+lb,+Node+rt)+{
++++++++++++super();
++++++++++++this.point+=+p;
++++++++++++this.rect+=+rect;
++++++++++++this.lb+=+lb;
++++++++++++this.rt+=+rt;
++++++++++++x+=+p.x();
++++++++++++y+=+p.y();
++++++++}

++++}
++++private+Node+root+=+null;;

++++public+KdTree()+{
++++}

++++public+boolean+isEmpty()+{
++++++++return+root+==+null;
++++}

++++public+int+size()+{
++++++++return+rechnenSize(root);
++++}

++++private+int+rechnenSize(Node+node)+{
++++++++if+(node+==+null)+{
++++++++++++return+0;
++++++++}+else+{
++++++++++++return+node.size;
++++++++}
++++}

++++public+void+insert(Point2D+p)+{
++++++++if+(p+==+null)+{
++++++++++++throw+new+NullPointerException();
++++++++}
++++++++if+(isEmpty())+{
++++++++++++root+=+insertInternal(p,+root,+0);
++++++++++++root.rect+=+new+RectHV(0,+0,+1,+1);
++++++++}+else+{
++++++++++++root+=+insertInternal(p,+root,+1);
++++++++}
++++}

++++//+at+odd+level+we+will+compare+x+coordinate,+and+at+even+level+we+will
++++//+compare+y+coordinate
++++private+Node+insertInternal(Point2D+pointToInsert,+Node+node,+int+level)+{
++++++++if+(node+==+null)+{
++++++++++++Node+newNode+=+new+Node(pointToInsert,+null,+null,+null);
++++++++++++newNode.size+=+1;
++++++++++++return+newNode;
++++++++}
++++++++if+(level+%25+2+==+0)+{//Horizontal+partition+line
++++++++++++if+(pointToInsert.y()+<+node.y)+{//Traverse+in+bottom+area+of+partition
++++++++++++++++node.lb+=+insertInternal(pointToInsert,+node.lb,+level+%2B+1);
++++++++++++++++if(node.lb.rect+==+null){
++++++++++++++++++++node.lb.rect+=+new+RectHV(node.rect.xmin(),+node.rect.ymin(),
++++++++++++++++++++++++++++node.rect.xmax(),+node.y);
++++++++++++++++}
++++++++++++}+else+{//Traverse+in+top+area+of+partition
++++++++++++++++if+(!node.point.equals(pointToInsert))+{
++++++++++++++++++++node.rt+=+insertInternal(pointToInsert,+node.rt,+level+%2B+1);
++++++++++++++++++++if(node.rt.rect+==+null){
++++++++++++++++++++++++node.rt.rect+=+new+RectHV(node.rect.xmin(),+node.y,
++++++++++++++++++++++++++++++++node.rect.xmax(),+node.rect.ymax());
++++++++++++++++++++}
++++++++++++++++}
++++++++++++}

++++++++}+else+if+(level+%25+2+!=+0)+{//Vertical+partition+line
++++++++++++if+(pointToInsert.x()+<+node.x)+{//Traverse+in+left+area+of+partition
++++++++++++++++node.lb+=+insertInternal(pointToInsert,+node.lb,+level+%2B+1);
++++++++++++++++if(node.lb.rect+==+null){
++++++++++++++++++++node.lb.rect+=+new+RectHV(node.rect.xmin(),+node.rect.ymin(),
++++++++++++++++++++++++++++node.x,+node.rect.ymax());
++++++++++++++++}
++++++++++++}+else+{//Traverse+in+right+area+of+partition
++++++++++++++++if+(!node.point.equals(pointToInsert))+{
++++++++++++++++++++node.rt+=+insertInternal(pointToInsert,+node.rt,+level+%2B+1);
++++++++++++++++++++if(node.rt.rect+==+null){
++++++++++++++++++++++++node.rt.rect+=+new+RectHV(node.x,+node.rect.ymin(),
++++++++++++++++++++++++++++++++node.rect.xmax(),+node.rect.ymax());
++++++++++++++++++++}
++++++++++++++++}
++++++++++++}
++++++++}
++++++++node.size+=+1+%2B+rechnenSize(node.lb)+%2B+rechnenSize(node.rt);
++++++++return+node;
++++}

++++public+boolean+contains(Point2D+p)+{
++++++++return+containsInternal(p,+root,+1);
++++}

++++private+boolean+containsInternal(Point2D+pointToSearch,+Node+node,+int+level)+{
++++++++if+(node+==+null)+{
++++++++++++return+false;
++++++++}
++++++++if+(level+%25+2+==+0)+{//Horizontal+partition+line
++++++++++++if+(pointToSearch.y()+<+node.y)+{
++++++++++++++++return+containsInternal(pointToSearch,+node.lb,+level+%2B+1);
++++++++++++}+else+{
++++++++++++++++if+(node.point.equals(pointToSearch))+{
++++++++++++++++++++return+true;
++++++++++++++++}
++++++++++++++++return+containsInternal(pointToSearch,+node.rt,+level+%2B+1);
++++++++++++}
++++++++}+else+{//Vertical+partition+line
++++++++++++if+(pointToSearch.x()+<+node.x)+{
++++++++++++++++return+containsInternal(pointToSearch,+node.lb,+level+%2B+1);
++++++++++++}+else+{
++++++++++++++++if+(node.point.equals(pointToSearch))+{
++++++++++++++++++++return+true;
++++++++++++++++}
++++++++++++++++return+containsInternal(pointToSearch,+node.rt,+level+%2B+1);
++++++++++++}
++++++++}

++++}

++++public+void+draw()+{
++++++++StdDraw.clear();
++++++++drawInternal(root,+1);
++++}

++++private+void+drawInternal(Node+node,+int+level)+{
++++++++if+(node+==+null)+{
++++++++++++return;
++++++++}
++++++++StdDraw.setPenColor(StdDraw.BLACK);
++++++++StdDraw.setPenRadius(0.02);
++++++++node.point.draw();
++++++++double+sx+=+node.rect.xmin();
++++++++double+ex+=+node.rect.xmax();
++++++++double+sy+=+node.rect.ymin();
++++++++double+ey+=+node.rect.ymax();
++++++++StdDraw.setPenRadius(0.01);
++++++++if+(level+%25+2+==+0)+{
++++++++++++StdDraw.setPenColor(StdDraw.BLUE);
++++++++++++sy+=+ey+=+node.y;
++++++++}+else+{
++++++++++++StdDraw.setPenColor(StdDraw.RED);
++++++++++++sx+=+ex+=+node.x;
++++++++}
++++++++StdDraw.line(sx,+sy,+ex,+ey);
++++++++drawInternal(node.lb,+level+%2B+1);
++++++++drawInternal(node.rt,+level+%2B+1);
++++}

++++/**
+++++*+Find+the+points+which+lies+in+the+rectangle+as+parameter
+++++*+@param+rect
+++++*+@return
+++++*/
++++public+Iterable<Point2D>+range(RectHV+rect)+{
++++++++List<Point2D>+resultList+=+new+ArrayList<Point2D>();
++++++++rangeInternal(root,+rect,+resultList);
++++++++return+resultList;
++++}

++++private+void+rangeInternal(Node+node,+RectHV+rect,+List<Point2D>+resultList)+{
++++++++if+(node+==+null)+{
++++++++++++return;
++++++++}
++++++++if+(node.rect.intersects(rect))+{
++++++++++++if+(rect.contains(node.point))+{
++++++++++++++++resultList.add(node.point);
++++++++++++}
++++++++++++rangeInternal(node.lb,+rect,+resultList);
++++++++++++rangeInternal(node.rt,+rect,+resultList);
++++++++}

++++}

++++public+Point2D+nearest(Point2D+p)+{
++++++++if(root+==+null){
++++++++++++return+null;
++++++++}
++++++++Champion+champion+=+new+Champion(root.point,Double.MAX_VALUE);
++++++++return+nearestInternal(p,+root,+champion,+1).champion;
++++}

++++private+Champion+nearestInternal(Point2D+targetPoint,+Node+node,
++++++++++++Champion+champion,+int+level)+{
++++++++if+(node+==+null)+{
++++++++++++return+champion;
++++++++}
++++++++double+dist+=+targetPoint.distanceSquaredTo(node.point);
++++++++int+newLevel+=+level+%2B+1;
++++++++if+(dist+<+champion.championDist)+{
++++++++++++champion.champion+=+node.point;
++++++++++++champion.championDist+=+dist;
++++++++}
++++++++boolean+goLeftOrBottom+=+false;
++++++++//We+will+decide+which+part+to+be+visited+first,+based+upon+in+which+part+point+lies.
++++++++//If+point+is+towards+left+or+bottom+part,+we+traverse+in+that+area+first,+and+later+on+decide
++++++++//if+we+need+to+search+in+other+part+too.
++++++++if(level+%25+2+==+0){
++++++++++++if(targetPoint.y()+<+node.y){
++++++++++++++++goLeftOrBottom+=+true;
++++++++++++}
++++++++}+else+{
++++++++++++if(targetPoint.x()+<+node.x){
++++++++++++++++goLeftOrBottom+=+true;
++++++++++++}
++++++++}
++++++++if(goLeftOrBottom){
++++++++++++nearestInternal(targetPoint,+node.lb,+champion,+newLevel);
++++++++++++Point2D+orientationPoint+=+createOrientationPoint(node.x,node.y,targetPoint,level);
++++++++++++double+orientationDist+=+orientationPoint.distanceSquaredTo(targetPoint);
++++++++++++//We+will+search+on+the+other+part+only,+if+the+point+is+very+near+to+partitioned+line
++++++++++++//and+champion+point+found+so+far+is+far+away+from+the+partitioned+line.
++++++++++++if(orientationDist+<+champion.championDist){
++++++++++++++++nearestInternal(targetPoint,+node.rt,+champion,+newLevel);
++++++++++++}
++++++++}+else+{
++++++++++++nearestInternal(targetPoint,+node.rt,+champion,+newLevel);
++++++++++++Point2D+orientationPoint+=+createOrientationPoint(node.x,node.y,targetPoint,level);
++++++++++++//We+will+search+on+the+other+part+only,+if+the+point+is+very+near+to+partitioned+line
++++++++++++//and+champion+point+found+so+far+is+far+away+from+the+partitioned+line.
++++++++++++double+orientationDist+=+orientationPoint.distanceSquaredTo(targetPoint);
++++++++++++if(orientationDist+<+champion.championDist){
++++++++++++++++nearestInternal(targetPoint,+node.lb,+champion,+newLevel);
++++++++++++}

++++++++}
++++++++return+champion;
++++}
++++/**
+++++*+Returns+the+point+from+a+partitioned+line,+which+can+be+directly+used+to+calculate
+++++*+distance+between+partitioned+line+and+the+target+point+for+which+neighbours+are+to+be+searched.
+++++*+@param+linePointX
+++++*+@param+linePointY
+++++*+@param+targetPoint
+++++*+@param+level
+++++*+@return
+++++*/
++++private+Point2D+createOrientationPoint(double+linePointX,+double+linePointY,+Point2D+targetPoint,+int+level){
++++++++if(level+%25+2+==+0){
++++++++++++return+new+Point2D(targetPoint.x(),linePointY);
++++++++}+else+{
++++++++++++return+new+Point2D(linePointX,targetPoint.y());
++++++++}
++++}

++++private+static+class+Champion{
++++++++public+Point2D+champion;
++++++++public+double+championDist;
++++++++public+Champion(Point2D+c,+double+d){
++++++++++++champion+=+c;
++++++++++++championDist+=+d;
++++++++}
++++}

++++public+static+void+main(String[]+args)+{
++++++++String+filename+=+"/home/raman/Downloads/kdtree/circle100.txt";
++++++++In+in+=+new+In(filename);
++++++++KdTree+kdTree+=+new+KdTree();
++++++++while+(!in.isEmpty())+{
++++++++++++double+x+=+in.readDouble();
++++++++++++double+y+=+in.readDouble();
++++++++++++Point2D+p+=+new+Point2D(x,+y);
++++++++++++kdTree.insert(p);
++++++++}
++++++++//+kdTree.print();
++++++++System.out.println(kdTree.size());
++++++++kdTree.draw();
++++++++System.out.println(kdTree.nearest(new+Point2D(0.4,+0.5)));
++++++++System.out.println(new+Point2D(0.7,+0.4).distanceSquaredTo(new+Point2D(0.9,0.5)));
++++++++System.out.println(new+Point2D(0.7,+0.4).distanceSquaredTo(new+Point2D(0.9,0.4)));

++++}
}|code-block|syntax|javascript|1701572|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

This is a full implementation for KD-Tree, I have used some libraries to store point and rectangle. These libraries are freely available. It is possible to do with these classes my making your own classes to store point and rectangle. Please share your feedback.

<pre><code>import java.util.ArrayList;
import java.util.List;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdDraw;
public class KdTree {
 private static class Node {
 public Point2D point; // the point
 public RectHV rect; // the axis-aligned rectangle corresponding to this
 public Node lb; // the left/bottom subtree
 public Node rt; // the right/top subtree
 public int size;
 public double x = 0;
 public double y = 0;
 public Node(Point2D p, RectHV rect, Node lb, Node rt) {
 super();
 this.point = p;
 this.rect = rect;
 this.lb = lb;
 this.rt = rt;
 x = p.x();
 y = p.y();
 }

 }
 private Node root = null;;

 public KdTree() {
 }

 public boolean isEmpty() {
 return root == null;
 }

 public int size() {
 return rechnenSize(root);
 }

 private int rechnenSize(Node node) {
 if (node == null) {
 return 0;
 } else {
 return node.size;
 }
 }

 public void insert(Point2D p) {
 if (p == null) {
 throw new NullPointerException();
 }
 if (isEmpty()) {
 root = insertInternal(p, root, 0);
 root.rect = new RectHV(0, 0, 1, 1);
 } else {
 root = insertInternal(p, root, 1);
 }
 }

 // at odd level we will compare x coordinate, and at even level we will
 // compare y coordinate
 private Node insertInternal(Point2D pointToInsert, Node node, int level) {
 if (node == null) {
 Node newNode = new Node(pointToInsert, null, null, null);
 newNode.size = 1;
 return newNode;
 }
 if (level % 2 == 0) {//Horizontal partition line
 if (pointToInsert.y() &lt; node.y) {//Traverse in bottom area of partition
 node.lb = insertInternal(pointToInsert, node.lb, level + 1);
 if(node.lb.rect == null){
 node.lb.rect = new RectHV(node.rect.xmin(), node.rect.ymin(),
 node.rect.xmax(), node.y);
 }
 } else {//Traverse in top area of partition
 if (!node.point.equals(pointToInsert)) {
 node.rt = insertInternal(pointToInsert, node.rt, level + 1);
 if(node.rt.rect == null){
 node.rt.rect = new RectHV(node.rect.xmin(), node.y,
 node.rect.xmax(), node.rect.ymax());
 }
 }
 }

 } else if (level % 2 != 0) {//Vertical partition line
 if (pointToInsert.x() &lt; node.x) {//Traverse in left area of partition
 node.lb = insertInternal(pointToInsert, node.lb, level + 1);
 if(node.lb.rect == null){
 node.lb.rect = new RectHV(node.rect.xmin(), node.rect.ymin(),
 node.x, node.rect.ymax());
 }
 } else {//Traverse in right area of partition
 if (!node.point.equals(pointToInsert)) {
 node.rt = insertInternal(pointToInsert, node.rt, level + 1);
 if(node.rt.rect == null){
 node.rt.rect = new RectHV(node.x, node.rect.ymin(),
 node.rect.xmax(), node.rect.ymax());
 }
 }
 }
 }
 node.size = 1 + rechnenSize(node.lb) + rechnenSize(node.rt);
 return node;
 }

 public boolean contains(Point2D p) {
 return containsInternal(p, root, 1);
 }

 private boolean containsInternal(Point2D pointToSearch, Node node, int level) {
 if (node == null) {
 return false;
 }
 if (level % 2 == 0) {//Horizontal partition line
 if (pointToSearch.y() &lt; node.y) {
 return containsInternal(pointToSearch, node.lb, level + 1);
 } else {
 if (node.point.equals(pointToSearch)) {
 return true;
 }
 return containsInternal(pointToSearch, node.rt, level + 1);
 }
 } else {//Vertical partition line
 if (pointToSearch.x() &lt; node.x) {
 return containsInternal(pointToSearch, node.lb, level + 1);
 } else {
 if (node.point.equals(pointToSearch)) {
 return true;
 }
 return containsInternal(pointToSearch, node.rt, level + 1);
 }
 }

 }

 public void draw() {
 StdDraw.clear();
 drawInternal(root, 1);
 }

 private void drawInternal(Node node, int level) {
 if (node == null) {
 return;
 }
 StdDraw.setPenColor(StdDraw.BLACK);
 StdDraw.setPenRadius(0.02);
 node.point.draw();
 double sx = node.rect.xmin();
 double ex = node.rect.xmax();
 double sy = node.rect.ymin();
 double ey = node.rect.ymax();
 StdDraw.setPenRadius(0.01);
 if (level % 2 == 0) {
 StdDraw.setPenColor(StdDraw.BLUE);
 sy = ey = node.y;
 } else {
 StdDraw.setPenColor(StdDraw.RED);
 sx = ex = node.x;
 }
 StdDraw.line(sx, sy, ex, ey);
 drawInternal(node.lb, level + 1);
 drawInternal(node.rt, level + 1);
 }

 /**
 * Find the points which lies in the rectangle as parameter
 * @param rect
 * @return
 */
 public Iterable&lt;Point2D&gt; range(RectHV rect) {
 List&lt;Point2D&gt; resultList = new ArrayList&lt;Point2D&gt;();
 rangeInternal(root, rect, resultList);
 return resultList;
 }

 private void rangeInternal(Node node, RectHV rect, List&lt;Point2D&gt; resultList) {
 if (node == null) {
 return;
 }
 if (node.rect.intersects(rect)) {
 if (rect.contains(node.point)) {
 resultList.add(node.point);
 }
 rangeInternal(node.lb, rect, resultList);
 rangeInternal(node.rt, rect, resultList);
 }

 }

 public Point2D nearest(Point2D p) {
 if(root == null){
 return null;
 }
 Champion champion = new Champion(root.point,Double.MAX_VALUE);
 return nearestInternal(p, root, champion, 1).champion;
 }

 private Champion nearestInternal(Point2D targetPoint, Node node,
 Champion champion, int level) {
 if (node == null) {
 return champion;
 }
 double dist = targetPoint.distanceSquaredTo(node.point);
 int newLevel = level + 1;
 if (dist &lt; champion.championDist) {
 champion.champion = node.point;
 champion.championDist = dist;
 }
 boolean goLeftOrBottom = false;
 //We will decide which part to be visited first, based upon in which part point lies.
 //If point is towards left or bottom part, we traverse in that area first, and later on decide
 //if we need to search in other part too.
 if(level % 2 == 0){
 if(targetPoint.y() &lt; node.y){
 goLeftOrBottom = true;
 }
 } else {
 if(targetPoint.x() &lt; node.x){
 goLeftOrBottom = true;
 }
 }
 if(goLeftOrBottom){
 nearestInternal(targetPoint, node.lb, champion, newLevel);
 Point2D orientationPoint = createOrientationPoint(node.x,node.y,targetPoint,level);
 double orientationDist = orientationPoint.distanceSquaredTo(targetPoint);
 //We will search on the other part only, if the point is very near to partitioned line
 //and champion point found so far is far away from the partitioned line.
 if(orientationDist &lt; champion.championDist){
 nearestInternal(targetPoint, node.rt, champion, newLevel);
 }
 } else {
 nearestInternal(targetPoint, node.rt, champion, newLevel);
 Point2D orientationPoint = createOrientationPoint(node.x,node.y,targetPoint,level);
 //We will search on the other part only, if the point is very near to partitioned line
 //and champion point found so far is far away from the partitioned line.
 double orientationDist = orientationPoint.distanceSquaredTo(targetPoint);
 if(orientationDist &lt; champion.championDist){
 nearestInternal(targetPoint, node.lb, champion, newLevel);
 }

 }
 return champion;
 }
 /**
 * Returns the point from a partitioned line, which can be directly used to calculate
 * distance between partitioned line and the target point for which neighbours are to be searched.
 * @param linePointX
 * @param linePointY
 * @param targetPoint
 * @param level
 * @return
 */
 private Point2D createOrientationPoint(double linePointX, double linePointY, Point2D targetPoint, int level){
 if(level % 2 == 0){
 return new Point2D(targetPoint.x(),linePointY);
 } else {
 return new Point2D(linePointX,targetPoint.y());
 }
 }

 private static class Champion{
 public Point2D champion;
 public double championDist;
 public Champion(Point2D c, double d){
 champion = c;
 championDist = d;
 }
 }

 public static void main(String[] args) {
 String filename = "/home/raman/Downloads/kdtree/circle100.txt";
 In in = new In(filename);
 KdTree kdTree = new KdTree();
 while (!in.isEmpty()) {
 double x = in.readDouble();
 double y = in.readDouble();
 Point2D p = new Point2D(x, y);
 kdTree.insert(p);
 }
 // kdTree.print();
 System.out.println(kdTree.size());
 kdTree.draw();
 System.out.println(kdTree.nearest(new Point2D(0.4, 0.5)));
 System.out.println(new Point2D(0.7, 0.4).distanceSquaredTo(new Point2D(0.9,0.5)));
 System.out.println(new Point2D(0.7, 0.4).distanceSquaredTo(new Point2D(0.9,0.4)));

 }
}
</code></pre>

blocks|key|1701649|text|也许有人会对它感兴趣。请参考我在java中实现的2D树的nearest()+(和KD+Tree类)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1701650|import+edu.princeton.cs.algs4.Point2D;
import+edu.princeton.cs.algs4.RectHV;
import+edu.princeton.cs.algs4.StdDraw;

import+java.util.ArrayList;
import+java.util.List;

public+class+KdTree+{
++++private+Node+root;
++++private+int+size;

++++private+static+class+Node+{
++++++++private+Point2D+p;++++++//+the+point
++++++++private+RectHV+rect;++++//+the+axis-aligned+rectangle+corresponding+to+this+node
++++++++private+Node+lb;++++++++//+the+left/bottom+subtree
++++++++private+Node+rt;++++++++//+the+right/top+subtree
++++++++public+Node(Point2D+p,+RectHV+rect)+{
++++++++++++this.p+=+p;
++++++++++++this.rect+=+rect;
++++++++}
++++}

++++public+KdTree()+{
++++}

++++public+boolean+isEmpty()+{
++++++++return+size+==+0;
++++}

++++public+int+size()+{
++++++++return+size;
++++}

++++public+boolean+contains(Point2D+p)+{
++++++++if+(p+==+null)+throw+new+IllegalArgumentException("argument+to+contains()+is+null");
++++++++return+contains(root,+p,+1);
++++}

++++private+boolean+contains(Node+node,+Point2D+p,+int+level)+{
++++++++if+(node+==+null)+return+false;+//+a+base+case+for+recursive+call

++++++++if+(node.p.equals(p))+return+true;

++++++++if+(level+%25+2+==+0)+{+//+search+by+y+coordinate+(node+with+horizontal+partition+line)
++++++++++++if+(p.y()+<+node.p.y())
++++++++++++++++return+contains(node.lb,+p,+level+%2B+1);
++++++++++++else
++++++++++++++++return+contains(node.rt,+p,+level+%2B+1);
++++++++}
++++++++else+{+//+search+by+x+coordinate+(node+with+vertical+partition+line)
++++++++++++if+(p.x()+<+node.p.x())
++++++++++++++++return+contains(node.lb,+p,+level+%2B+1);
++++++++++++else
++++++++++++++++return+contains(node.rt,+p,+level+%2B+1);
++++++++}
++++}

++++public+void+insert(Point2D+p)+{
++++++++if+(p+==+null)+throw+new+IllegalArgumentException("calls+insert()+with+a+null+point");
++++++++root+=+insert(root,+p,+1);
++++}

++++private+Node+insert(Node+x,+Point2D+p,+int+level)+{
++++++++if+(x+==+null)+{
++++++++++++size%2B%2B;
++++++++++++return+new+Node(p,+new+RectHV(0,+0,+1,+1));
++++++++}

++++++++if+(x.p.equals(p))+return+x;+//+if+we+try+to+insert+existed+point+just+return+its+node

++++++++if+(level+%25+2+==+0)+{+//+search+by+y+coordinate+(node+with+horizontal+partition+line)
++++++++++++if+(p.y()+<+x.p.y())+{
++++++++++++++++x.lb+=+insert(x.lb,+p,+level+%2B+1);
++++++++++++++++if+(x.lb.rect.equals(root.rect))
++++++++++++++++++++x.lb.rect+=+new+RectHV(x.rect.xmin(),+x.rect.ymin(),+x.rect.xmax(),+x.p.y());
++++++++++++}
++++++++++++else+{
++++++++++++++++x.rt+=+insert(x.rt,+p,+level+%2B+1);
++++++++++++++++if+(x.rt.rect.equals(root.rect))
++++++++++++++++++++x.rt.rect+=+new+RectHV(x.rect.xmin(),+x.p.y(),+x.rect.xmax(),+x.rect.ymax());
++++++++++++}
++++++++}
++++++++else+{+//+search+by+x+coordinate+(node+with+vertical+partition+line)
++++++++++++if+(p.x()+<+x.p.x())+{
++++++++++++++++x.lb+=+insert(x.lb,+p,+level+%2B+1);
++++++++++++++++if+(x.lb.rect.equals(root.rect))
++++++++++++++++++++x.lb.rect+=+new+RectHV(x.rect.xmin(),+x.rect.ymin(),+x.p.x(),+x.rect.ymax());
++++++++++++}
++++++++++++else+{
++++++++++++++++x.rt+=+insert(x.rt,+p,+level+%2B+1);
++++++++++++++++if+(x.rt.rect.equals(root.rect))
++++++++++++++++++++x.rt.rect+=+new+RectHV(x.p.x(),+x.rect.ymin(),+x.rect.xmax(),+x.rect.ymax());
++++++++++++}
++++++++}
++++++++return+x;
++++}

++++public+void+draw()+{
++++++++draw(root,+1);
++++}

++++private+void+draw(Node+node,+int+level)+{
++++++++if+(node+==+null)+return;

++++++++StdDraw.setPenColor(StdDraw.BLACK);
++++++++StdDraw.setPenRadius(0.01);
++++++++node.p.draw();
++++++++StdDraw.setPenRadius();

++++++++if+(level+%25+2+==+0)+{
++++++++++++StdDraw.setPenColor(StdDraw.BLUE);
++++++++++++StdDraw.line(node.rect.xmin(),+node.p.y(),+node.rect.xmax(),+node.p.y());
++++++++}
++++++++else+{
++++++++++++StdDraw.setPenColor(StdDraw.RED);
++++++++++++StdDraw.line(node.p.x(),+node.rect.ymin(),+node.p.x(),+node.rect.ymax());
++++++++}

++++++++draw(node.lb,+level+%2B+1);
++++++++draw(node.rt,+level+%2B+1);
++++}

++++public+Iterable<Point2D>+range(RectHV+rect)+{
++++++++if+(rect+==+null)+throw+new+IllegalArgumentException("calls+range()+with+a+null+rect");
++++++++List<Point2D>+points+=+new+ArrayList<>();+//+create+an+Iterable+object+with+all+points+we+found
++++++++range(root,+rect,+points);+//+call+helper+method+with+rects+intersects+comparing
++++++++
++++++++return+points;+//+return+an+Iterable+object+(It+could+be+any+type+-+Queue,+LinkedList+etc)
++++}

++++private+void+range(Node+node,+RectHV+rect,+List<Point2D>+points)+{
++++++++if+(node+==+null+%7C%7C+!node.rect.intersects(rect))+return;+//+a+base+case+for+recursive+call


++++++++if+(rect.contains(node.p))
++++++++++++++++points.add(node.p);
++++++++range(node.lb,+rect,+points);
++++++++range(node.rt,+rect,+points);

++++}++++

++++public+Point2D+nearest(Point2D+query)+{
+++++++++if+(isEmpty())+return+null;
++++++++if+(query+==+null)+throw+new+IllegalArgumentException("calls+nearest()+with+a+null+point");
++++++++//+set+the+start+distance+from+root+to+query+point
++++++++double+best+=+root.p.distanceSquaredTo(query);
++++++++//+StdDraw.setPenColor(StdDraw.BLACK);+//+just+for+debugging
++++++++//+StdDraw.setPenRadius(0.01);
++++++++//+query.draw();
++++++++return+nearest(root,+query,+root.p,+best,+1);+//+call+a+helper+method
++++}

++++private+Point2D+nearest(Node+node,+Point2D+query,+Point2D+champ,+double+best,+int+level)+{
++++++++//+a+base+case+for+the+recursive+call
++++++++if+(node+==+null+%7C%7C+best+<+node.rect.distanceSquaredTo(query))+return+champ;
++++++++//+we'll+need+to+set+an+actual+best+distance+when+we+recur
++++++++best+=+champ.distanceSquaredTo(query);
++++++++//+check+whether+a+distance+from+query+point+to+the+traversed+node+less+than
++++++++//+distance+from+current+champion+to+query+point
++++++++double+temp+=+node.p.distanceSquaredTo(query);
++++++++if+(temp+<+best)+{
++++++++++++best+=+temp;
++++++++++++champ+=+node.p;
++++++++}

++++++++if+(level+%25+2+==+0)+{+//+search+by+y+coordinate+(node+with+horizontal+partition+line)
++++++++++++//+we+compare+y+coordinate+and+decide+go+up+or+down
++++++++++++if+(node.p.y()+<+query.y())+{+//+if+true+go+up
++++++++++++++++champ+=+nearest(node.rt,+query,+champ,+best,+level+%2B+1);
++++++++++++++++//+important+case+-+when+we+traverse+node+and+go+back+up+through+the+tree
++++++++++++++++//+we+need+to+decide+whether+we+need+to+go+down(left)+in+this+node+or+not
++++++++++++++++//+we+just+check+our+bottom+(left)+node+on+null+&&+compare+distance
++++++++++++++++//+from+query+point+to+the+nearest+point+of+the+node's+rectangle+and
++++++++++++++++//+the+distance+from+current+champ+point+to+thr+query+point
++++++++++++++++if+(node.lb+!=+null+&&+node.lb.rect.distanceSquaredTo(query)+<+champ.distanceSquaredTo(query))+{
++++++++++++++++++++champ+=+nearest(node.lb,+query,+champ,+best,+level+%2B+1);
++++++++++++++++}

++++++++++++}
++++++++++++else+{+//+if+false+go+down
++++++++++++++++champ+=+nearest(node.lb,+query,+champ,+best,+level+%2B+1);
++++++++++++++++if+(node.rt+!=+null+&&+node.rt.rect.distanceSquaredTo(query)+<+champ.distanceSquaredTo(query))
++++++++++++++++++++//+when+we+traverse+node+and+go+back+up+through+the+tree
++++++++++++++++++++//+we+need+to+decide+whether+we+need+to+go+up(right)+in+this+node+or+not
++++++++++++++++++++//+we+just+check+our+top+(right)+node+on+null+&&+compare+distance
++++++++++++++++++++//+from+query+point+to+the+nearest+point+of+the+node's+rectangle+and
++++++++++++++++++++//+the+distance+from+current+champ+point+to+thr+query+point
++++++++++++++++++++champ+=+nearest(node.rt,+query,+champ,+best,+level+%2B+1);

++++++++++++}

++++++++}
++++++++else+{
++++++++++++//+search+by+x+coordinate+(node+with+vertical+partition+line)
++++++++++++if+(node.p.x()+<+query.x())+{+//+if+true+go+right
++++++++++++++++champ+=+nearest(node.rt,+query,+champ,+best,+level+%2B+1);
++++++++++++++++//+the+same+check+as+mentioned+above+when+we+search+by+y+coordinate
++++++++++++++++if+(node.lb+!=+null+&&+node.lb.rect.distanceSquaredTo(query)+<+champ.distanceSquaredTo(query))
++++++++++++++++++++champ+=+nearest(node.lb,+query,+champ,+best,+level+%2B+1);
++++++++++++}
++++++++++++else+{+//+if+false+go+left
++++++++++++++++champ+=+nearest(node.lb,+query,+champ,+best,+level+%2B+1);
++++++++++++++++++if+(node.rt+!=+null+&&+node.rt.rect.distanceSquaredTo(query)+<+champ.distanceSquaredTo(query))
+++++++++++++++++++++champ+=+nearest(node.rt,+query,+champ,+best,+level+%2B+1);
++++++++++++}
++++++++}
++++++++return+champ;
++++}



++++public+static+void+main(String[]+args)+{
++++++++//+unit+tests
++++++++KdTree+kd+=+new+KdTree();
++++++++Point2D+p1+=+new+Point2D(0.7,+0.2);
++++++++Point2D+p2+=+new+Point2D(0.5,+0.4);
++++++++Point2D+p3+=+new+Point2D(0.2,+0.3);
++++++++Point2D+p4+=+new+Point2D(0.4,+0.7);
++++++++Point2D+p5+=+new+Point2D(0.9,+0.6);
++++++++//+Point2D+query+=+new+Point2D(0.676,+0.736);
++++++++Point2D+query1+=+new+Point2D(0.972,+0.887);
++++++++//+RectHV+test+=+new+RectHV(0,+0,+0.7,+0.4);
++++++++//+Point2D+query+=+new+Point2D(0.331,+0.762);

++++++++//+Point2D+p6+=+new+Point2D(0.4,+0.4);
++++++++//+Point2D+p7+=+new+Point2D(0.1,+0.6);
++++++++//+RectHV+rect+=+new+RectHV(0.05,+0.1,+0.15,+0.6);

++++++++kd.insert(p1);
++++++++kd.insert(p2);
++++++++kd.insert(p3);
++++++++kd.insert(p4);
++++++++kd.insert(p5);
++++++++System.out.println(kd.nearest(query1));
++++++++//+System.out.println("Dist+query+to+0.4,0.7=+"+%2B+query.distanceSquaredTo(p4));
++++++++//+System.out.println("Dist+query+to+RectHV+0.2,0,3=+"+%2B+test.distanceSquaredTo(p4));
++++++++//+kd.insert(p6);
++++++++//+kd.insert(p7);
++++++++//+System.out.println(kd.size);
++++++++//+System.out.println(kd.contains(p3));
++++++++//+//+System.out.println(kd.range(rect));

++++++++kd.draw();
++++++++

++++}
}|code-block|syntax|javascript|1701651|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

May be it will be interest for someone. Please see my nearest() (and KD Tree class) implementation for 2D tree in java:
<pre><code>import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.RectHV;
import edu.princeton.cs.algs4.StdDraw;

import java.util.ArrayList;
import java.util.List;

public class KdTree {
 private Node root;
 private int size;

 private static class Node {
 private Point2D p; // the point
 private RectHV rect; // the axis-aligned rectangle corresponding to this node
 private Node lb; // the left/bottom subtree
 private Node rt; // the right/top subtree
 public Node(Point2D p, RectHV rect) {
 this.p = p;
 this.rect = rect;
 }
 }

 public KdTree() {
 }

 public boolean isEmpty() {
 return size == 0;
 }

 public int size() {
 return size;
 }

 public boolean contains(Point2D p) {
 if (p == null) throw new IllegalArgumentException(&quot;argument to contains() is null&quot;);
 return contains(root, p, 1);
 }

 private boolean contains(Node node, Point2D p, int level) {
 if (node == null) return false; // a base case for recursive call

 if (node.p.equals(p)) return true;

 if (level % 2 == 0) { // search by y coordinate (node with horizontal partition line)
 if (p.y() &lt; node.p.y())
 return contains(node.lb, p, level + 1);
 else
 return contains(node.rt, p, level + 1);
 }
 else { // search by x coordinate (node with vertical partition line)
 if (p.x() &lt; node.p.x())
 return contains(node.lb, p, level + 1);
 else
 return contains(node.rt, p, level + 1);
 }
 }

 public void insert(Point2D p) {
 if (p == null) throw new IllegalArgumentException(&quot;calls insert() with a null point&quot;);
 root = insert(root, p, 1);
 }

 private Node insert(Node x, Point2D p, int level) {
 if (x == null) {
 size++;
 return new Node(p, new RectHV(0, 0, 1, 1));
 }

 if (x.p.equals(p)) return x; // if we try to insert existed point just return its node

 if (level % 2 == 0) { // search by y coordinate (node with horizontal partition line)
 if (p.y() &lt; x.p.y()) {
 x.lb = insert(x.lb, p, level + 1);
 if (x.lb.rect.equals(root.rect))
 x.lb.rect = new RectHV(x.rect.xmin(), x.rect.ymin(), x.rect.xmax(), x.p.y());
 }
 else {
 x.rt = insert(x.rt, p, level + 1);
 if (x.rt.rect.equals(root.rect))
 x.rt.rect = new RectHV(x.rect.xmin(), x.p.y(), x.rect.xmax(), x.rect.ymax());
 }
 }
 else { // search by x coordinate (node with vertical partition line)
 if (p.x() &lt; x.p.x()) {
 x.lb = insert(x.lb, p, level + 1);
 if (x.lb.rect.equals(root.rect))
 x.lb.rect = new RectHV(x.rect.xmin(), x.rect.ymin(), x.p.x(), x.rect.ymax());
 }
 else {
 x.rt = insert(x.rt, p, level + 1);
 if (x.rt.rect.equals(root.rect))
 x.rt.rect = new RectHV(x.p.x(), x.rect.ymin(), x.rect.xmax(), x.rect.ymax());
 }
 }
 return x;
 }

 public void draw() {
 draw(root, 1);
 }

 private void draw(Node node, int level) {
 if (node == null) return;

 StdDraw.setPenColor(StdDraw.BLACK);
 StdDraw.setPenRadius(0.01);
 node.p.draw();
 StdDraw.setPenRadius();

 if (level % 2 == 0) {
 StdDraw.setPenColor(StdDraw.BLUE);
 StdDraw.line(node.rect.xmin(), node.p.y(), node.rect.xmax(), node.p.y());
 }
 else {
 StdDraw.setPenColor(StdDraw.RED);
 StdDraw.line(node.p.x(), node.rect.ymin(), node.p.x(), node.rect.ymax());
 }

 draw(node.lb, level + 1);
 draw(node.rt, level + 1);
 }

 public Iterable&lt;Point2D&gt; range(RectHV rect) {
 if (rect == null) throw new IllegalArgumentException(&quot;calls range() with a null rect&quot;);
 List&lt;Point2D&gt; points = new ArrayList&lt;&gt;(); // create an Iterable object with all points we found
 range(root, rect, points); // call helper method with rects intersects comparing
 
 return points; // return an Iterable object (It could be any type - Queue, LinkedList etc)
 }

 private void range(Node node, RectHV rect, List&lt;Point2D&gt; points) {
 if (node == null || !node.rect.intersects(rect)) return; // a base case for recursive call


 if (rect.contains(node.p))
 points.add(node.p);
 range(node.lb, rect, points);
 range(node.rt, rect, points);

 } 

 public Point2D nearest(Point2D query) {
 if (isEmpty()) return null;
 if (query == null) throw new IllegalArgumentException(&quot;calls nearest() with a null point&quot;);
 // set the start distance from root to query point
 double best = root.p.distanceSquaredTo(query);
 // StdDraw.setPenColor(StdDraw.BLACK); // just for debugging
 // StdDraw.setPenRadius(0.01);
 // query.draw();
 return nearest(root, query, root.p, best, 1); // call a helper method
 }

 private Point2D nearest(Node node, Point2D query, Point2D champ, double best, int level) {
 // a base case for the recursive call
 if (node == null || best &lt; node.rect.distanceSquaredTo(query)) return champ;
 // we'll need to set an actual best distance when we recur
 best = champ.distanceSquaredTo(query);
 // check whether a distance from query point to the traversed node less than
 // distance from current champion to query point
 double temp = node.p.distanceSquaredTo(query);
 if (temp &lt; best) {
 best = temp;
 champ = node.p;
 }

 if (level % 2 == 0) { // search by y coordinate (node with horizontal partition line)
 // we compare y coordinate and decide go up or down
 if (node.p.y() &lt; query.y()) { // if true go up
 champ = nearest(node.rt, query, champ, best, level + 1);
 // important case - when we traverse node and go back up through the tree
 // we need to decide whether we need to go down(left) in this node or not
 // we just check our bottom (left) node on null &amp;&amp; compare distance
 // from query point to the nearest point of the node's rectangle and
 // the distance from current champ point to thr query point
 if (node.lb != null &amp;&amp; node.lb.rect.distanceSquaredTo(query) &lt; champ.distanceSquaredTo(query)) {
 champ = nearest(node.lb, query, champ, best, level + 1);
 }

 }
 else { // if false go down
 champ = nearest(node.lb, query, champ, best, level + 1);
 if (node.rt != null &amp;&amp; node.rt.rect.distanceSquaredTo(query) &lt; champ.distanceSquaredTo(query))
 // when we traverse node and go back up through the tree
 // we need to decide whether we need to go up(right) in this node or not
 // we just check our top (right) node on null &amp;&amp; compare distance
 // from query point to the nearest point of the node's rectangle and
 // the distance from current champ point to thr query point
 champ = nearest(node.rt, query, champ, best, level + 1);

 }

 }
 else {
 // search by x coordinate (node with vertical partition line)
 if (node.p.x() &lt; query.x()) { // if true go right
 champ = nearest(node.rt, query, champ, best, level + 1);
 // the same check as mentioned above when we search by y coordinate
 if (node.lb != null &amp;&amp; node.lb.rect.distanceSquaredTo(query) &lt; champ.distanceSquaredTo(query))
 champ = nearest(node.lb, query, champ, best, level + 1);
 }
 else { // if false go left
 champ = nearest(node.lb, query, champ, best, level + 1);
 if (node.rt != null &amp;&amp; node.rt.rect.distanceSquaredTo(query) &lt; champ.distanceSquaredTo(query))
 champ = nearest(node.rt, query, champ, best, level + 1);
 }
 }
 return champ;
 }



 public static void main(String[] args) {
 // unit tests
 KdTree kd = new KdTree();
 Point2D p1 = new Point2D(0.7, 0.2);
 Point2D p2 = new Point2D(0.5, 0.4);
 Point2D p3 = new Point2D(0.2, 0.3);
 Point2D p4 = new Point2D(0.4, 0.7);
 Point2D p5 = new Point2D(0.9, 0.6);
 // Point2D query = new Point2D(0.676, 0.736);
 Point2D query1 = new Point2D(0.972, 0.887);
 // RectHV test = new RectHV(0, 0, 0.7, 0.4);
 // Point2D query = new Point2D(0.331, 0.762);

 // Point2D p6 = new Point2D(0.4, 0.4);
 // Point2D p7 = new Point2D(0.1, 0.6);
 // RectHV rect = new RectHV(0.05, 0.1, 0.15, 0.6);

 kd.insert(p1);
 kd.insert(p2);
 kd.insert(p3);
 kd.insert(p4);
 kd.insert(p5);
 System.out.println(kd.nearest(query1));
 // System.out.println(&quot;Dist query to 0.4,0.7= &quot; + query.distanceSquaredTo(p4));
 // System.out.println(&quot;Dist query to RectHV 0.2,0,3= &quot; + test.distanceSquaredTo(p4));
 // kd.insert(p6);
 // kd.insert(p7);
 // System.out.println(kd.size);
 // System.out.println(kd.contains(p3));
 // // System.out.println(kd.range(rect));

 kd.draw();
 

 }
}
</code></pre>

I'm looking for a KDTree implementation in Java. 
I've done a google search and the results seem pretty haphazard. There are actually lots of results, but they're mostly just little one-off implementations, and I'd rather find something with a little more "production value". Something like apache collections or the excellent C5 collection library for .NET. Something where I can see the public bug tracker and check to see when the last SVN commit happened. Also, in an ideal world, I'd find a nice well-designed API for spatial data structures, and the KDTree would be just one class in that library.

For this project, I'll only be working in either 2 or 3 dimensions, and I'm mostly just interested in a good nearest-neighbors implementation.

KDTree Implementation in Java

数据结构

Java

我正在寻找一个用Java语言实现的KDTree。我在谷歌上搜索了一下，结果看起来相当随意。实际上有很多结果，但它们大多只是一些一次性的小实现，我宁愿找到一些更有“生产价值”的东西。比如apache集合或者.NET优秀的C5集合库，在这里我可以看到公共的bug跟踪器，并查看最后一次提交SVN的时间。而且，在理想的情况下，...

问KDTree在Java中的实现
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问KDTree在Java中的实现EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问KDTree在Java中的实现
EN