자바에서 KDTree 구현

자바에서 KDTree 구현

---

Java에서 KDTree 구현을 찾고 있습니다.
나는 구글 검색을했고 그 결과는 꽤 무의미 해 보인다. 실제로 많은 결과가 있지만 대부분은 일회성 구현 일 뿐이며 오히려 "생산 가치"가 약간 더있는 무언가를 찾고 싶습니다. 아파치 컬렉션이나 .NET 용 우수한 C5 컬렉션 라이브러리와 같은 것입니다. 공개 버그 추적기를보고 마지막 SVN 커밋이 언제 발생했는지 확인할 수있는 것입니다. 또한 이상적인 세계에서는 공간 데이터 구조를 위해 잘 설계된 API를 찾을 수 있으며 KDTree는 해당 라이브러리에서 하나의 클래스에 불과합니다.

이 프로젝트의 경우 2 차원 또는 3 차원에서만 작업 할 것이며, 대부분의 경우 가장 가까운 이웃 구현에 관심이 있습니다.

---

책 Algorithms in a Nutshell 에는 몇 가지 변형과 함께 Java로 된 kd 트리 구현이 있습니다. 모든 코드는 oreilly.com에 있으며 책 자체도 알고리즘을 안내하므로 직접 빌드 할 수 있습니다.

---

미래를 구하는 사람들을 위해. Java-ml 라이브러리에는 제대로 작동하는 kd-tree 구현이 있습니다. http://java-ml.sourceforge.net/

---

여기 에서 Levy 교수의 구현으로 성공했습니다 . 나는 당신이 더 많은 프로덕션 인증 구현을 찾고 있다는 것을 알고 있으므로 이것은 아마도 적합하지 않을 것입니다.

그러나 지나가는 사람들에게 유의하십시오. 나는 지금까지 문제없이 포토 모자이크 프로젝트에서 그것을 사용하고 있습니다. 보장은 없지만 아무것도없는 것보다 낫습니다. :)

---

오프라인 역 지오 코딩 라이브러리의 일부로 KD-Tree 구현을 만들었습니다.

https://github.com/AReallyGoodName/OfflineReverseGeocode

---

아마 가장 가까운 이웃 검색 및 KD-나무 스토니 - 브룩 알고리즘 저장소 캔 도움말에서.

---

도 있습니다 JTS 토폴로지 스위트

KdTree 구현은 범위 검색 만 제공합니다 (가장 가까운 이웃 없음).

가장 가까운 이웃이 당신의 일 이라면 STRtree 를 보십시오

---

당신이 맞습니다, 자바에 대한 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;
}

---

이것은 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)));

    }
}

---

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

참조 URL : https://stackoverflow.com/questions/253767/kdtree-implementation-in-java