Java中的KDTree实现

我正在寻找Java中的KDTree实现。
我做了谷歌search，结果似乎很随意。 实际上有很多结果，但它们大多只是一次性的实现，我宁愿find一些具有更多“产品价值”的东西。 就像apache集合或者用于.NET的优秀的C5集合库。 我可以看到公共bug跟踪器，并查看最后一次SVN提交发生的时间。 另外，在一个理想的世界里，我会find一个精心devise的空间数据结构API，而KDTree只是该库中的一个类。

对于这个项目，我只能在2维或3维上工作，而且我大多只对一个好的最近邻居实现感兴趣。

Answer 1

在“ 果壳algorithm”一书中，有java中的kd树实现以及一些变体。 所有的代码都在oreilly.com上 ，书本身也会引导你通过algorithm，所以你可以自己创build一个。

Answer 2

为未来的求职者。 Java-ml库有一个很好的kd-tree实现。 http://java-ml.sourceforge.net/

Answer 3

我在这里find了 Levy教授的实施，取得了成功。 我意识到你正在寻找更多的生产authentication实施，所以这可能不是一个好的select。

然而，请注意任何路人，我已经在我的photomosaic项目中使用了一段时间，没有任何问题。 没有保证，但比没有好:)

Answer 4

也许最近邻search和来自Stony-Brookalgorithm库的KD树可以提供帮助。

Answer 5

我创build了一个KD-Tree实现作为离线反向地理编码库的一部分

https://github.com/AReallyGoodName/OfflineReverseGeocode

Answer 6

你是正确的，有没有很多网站与KD实施为Java！ 无论如何，kd树基本上是一个二叉search树，通常每次计算一个中间值的那个维度。 这里是简单的KDNode，并在最近邻方法或全面实施方面看看这个github项目。 这是我能find的最好的一个。 希望这可以帮助你。

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; } 

Answer 7

还有JTS拓扑套件

KdTree实现仅提供范围search（无最近邻居）。

如果最近邻居是你的东西看STRtree

Answer 8

这是KD-Tree的完整实现，我用一些库来存储点和矩形。 这些库免费提供。 这些类可以做我自己的类来存储点和矩形。 请分享您的反馈。

 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 = px(); y = py(); } } 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() < 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() < 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() < 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() < 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<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 + 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 % 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 % 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))); } } 

Answer 9

 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++) 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+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] && x[1]==t.data[1]) return true; }else if(x[cd]<t.data[cd]){ found = search(x,t.left,(cd+1)%DIM); }else if(x[cd]>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)); } }