Java中的KDTree实现

KDTree Implementation in Java

提问by benjismith

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.

我正在寻找 Java 中的 KDTree 实现。
我已经进行了谷歌搜索，结果似乎很随意。实际上有很多结果，但它们大多只是一次性的小实现，我宁愿找到具有更多“生产价值”的东西。类似于 apache 集合或用于 .NET 的优秀 C5 集合库。在那里我可以看到公共错误跟踪器并检查上次 SVN 提交发生的时间。此外，在理想的世界中，我会为空间数据结构找到一个设计良好的 API，而 KDTree 只是该库中的一个类。

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.

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

采纳答案by Ichorus

In the book Algorithms in a Nutshellthere is a kd tree implementation in java along with a few variations. All of the code is on oreilly.comand the book itself also walk you through the algorithm so you could build one yourself.

在Nutshell 中的算法一书中，Java 中有一个 kd 树实现以及一些变体。所有代码都在oreilly.com 上，这本书本身也会引导您完成算法，这样您就可以自己构建一个。

回答by Yuval F

Maybe Nearest Neighbor Searchand KD-treesfrom the Stony-Brook algorithm repository can help.

也许来自 Stony-Brook 算法存储库的最近邻搜索和KD 树可以提供帮助。

回答by Brian Harris

I've had success with Professor Levy's implementation found here. I realize you're looking for a more production-certified implementation so this is probably not a good fit.

我在此处找到了Levy 教授的实施取得了成功。我意识到您正在寻找经过生产认证的实现，因此这可能不合适。

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 :)

但是请注意任何路人，我已经在我的马赛克照片项目中使用它一段时间了，没有任何问题。不能保证，但总比没有好:)

回答by theosem

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

对于未来的寻求者。Java-ml 库有一个运行良好的 kd-tree 实现。 http://java-ml.sourceforge.net/

回答by AReallyGoodName

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

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

https://github.com/AReallyGoodName/OfflineReverseGeocode

https://github.com/AReallyGoodName/OfflineReverseGeocode

回答by Ryan

There is also JTS Topology Suite

还有JTS 拓扑套件

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

KdTree 实现仅提供范围搜索（没有最近邻）。

If nearest-neighbor is your thing look at STRtree

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

回答by grepit

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 githubproject. It was the best one I could find for you. Hope this helps you.

你是对的，没有多少网站有 java 的 kd 实现！无论如何，kd 树基本上是一个二叉搜索树，通常每次都会为该维度计算一个中值。这是简单的 KDNode，就最近邻方法或完整实现而言，请查看此github项目。这是我能为你找到的最好的。希望这对你有帮助。

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

回答by Gayathri

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

回答by Raman Sharma

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.

这是 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 = 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() < 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)));

    }
}