/[projects]/dao/FuldDaekningWorker/src/geocode/kdtree/KDTree.java
ViewVC logotype

Diff of /dao/FuldDaekningWorker/src/geocode/kdtree/KDTree.java

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 2602 by torben, Mon Jul 13 10:16:41 2015 UTC revision 2603 by torben, Tue Jul 14 05:03:24 2015 UTC
# Line 56  public class KDTree<T extends KDNodeComp Line 56  public class KDTree<T extends KDNodeComp
56          int currentIndex = items.size()/2;          int currentIndex = items.size()/2;
57          return new KDNode<T>(createKDTree(new ArrayList<T>(items.subList(0, currentIndex)), depth+1), createKDTree(new ArrayList<T>(items.subList(currentIndex + 1, items.size())), depth+1), items.get(currentIndex));          return new KDNode<T>(createKDTree(new ArrayList<T>(items.subList(0, currentIndex)), depth+1), createKDTree(new ArrayList<T>(items.subList(currentIndex + 1, items.size())), depth+1), items.get(currentIndex));
58      }      }
59        
       
60      private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) {      private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) {
61          int direction = search.getComparator(depth % 3).compare( search, currentNode.location );          int direction = search.getComparator(depth % 3).compare( search, currentNode.location );
62          KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right;          KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right;
63          KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left;          KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left;
64          KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf          KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf
65          if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search)  ) {          if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search) ) {
66              best = currentNode; // Set best as required              best = currentNode; // Set best as required
67          }          }
68          if ( other != null ) {          if ( other != null ) {
# Line 76  public class KDTree<T extends KDNodeComp Line 75  public class KDTree<T extends KDNodeComp
75          }          }
76          return best; // Work back up          return best; // Work back up
77      }      }
   
     /* backup af udgave med isNodeCompatible  
     private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) {  
         int direction = search.getComparator(depth % 3).compare( search, currentNode.location );  
         KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right;  
         KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left;  
         KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf  
         if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search) && search.isNodeCompatible(currentNode.location) ) {  
             best = currentNode; // Set best as required  
         }  
         if ( other != null ) {  
             if ( currentNode.location.axisSquaredDistance(search, depth % 3) < best.location.squaredDistance(search) ) {  
                 KDNode<T> possibleBest = findNearest( other, search, depth + 1 );  
                 if (  possibleBest.location.squaredDistance(search) < best.location.squaredDistance(search)  && search.isNodeCompatible(possibleBest.location)) {  
                     best = possibleBest;  
                 }  
             }  
         }  
         return best; // Work back up  
     }*/  
78  }  }
Legend:
Removed from v.2602  
changed lines
  Added in v.2603
  ViewVC Help
Powered by ViewVC 1.1.20