Внедрение KDTree в Java

Question

Я ищу реализацию KDTree в Java.
Я сделал поиск в Google, и результаты кажутся довольно случайными. На самом деле есть много результатов, но в основном это просто небольшие одноразовые реализации, и я бы скорее нашел что-то с чуть более «производственной ценностью». Что-то вроде коллекций apache или отличная библиотека коллекции C5 для .NET. Что-то, где я могу увидеть публичный трекер ошибок и проверить, когда произошло последнее событие SVN. Кроме того, в идеальном мире я бы нашел хороший хорошо разработанный API для пространственных структур данных, а KDTree будет всего лишь одним классом в этой библиотеке.

Для этого проекта я буду работать только в 2 или 3 измерениях, и меня в основном интересует только реализация ближайших соседей.

Answer 1

В книге Algorithms in a Nutshell реализована реализация дерева kd в java наряду с несколькими вариантами. Весь код находится на oreilly.com, и сама книга также проведет вас по алгоритму, чтобы вы могли создать его самостоятельно.

Answer 2

Возможно, Nearest Neighbor Search и KD-trees из хранилища алгоритмов Stony-Brook могут помочь.

Answer 3

У меня был успех с внедрением профессора Леви here. Я понимаю, что вы ищете более сертифицированную продукцию, поэтому это, вероятно, не очень подходит.

Однако примечание для любых прохожих, я использовал это какое-то время в моем проекте фотомозаики без проблем. Нет гарантии, но лучше, чем ничего :)

Answer 4

для будущих искателей. В библиотеке Java-ml реализована реализация kd-tree, которая отлично работает. http://java-ml.sourceforge.net/

Answer 5

Я создал реализацию KD-Tree как часть автономному обратного геокодирования библиотека

https://github.com/AReallyGoodName/OfflineReverseGeocode

Answer 6

Существует также JTS Topology Suite

Реализация KdTree только обеспечивает поиск диапазоном (ближайших соседей).

Если ближайший сосед ваша вещи смотреть на STRtree

Answer 7

Вы правильно, там не так много сайтов с реализацией сушилок для Java! В любом случае, kd tree - это, в основном, двоичное дерево поиска, среднее значение которого обычно вычисляется каждый раз для этого измерения. Вот простой метод 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; 
} 

Answer 8

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

Answer 9

Это полная реализация для 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))); 

    } 
}