/[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 2596 by torben, Sun Jun 14 14:28:21 2015 UTC revision 2597 by torben, Mon Jul 13 10:16:41 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        
61        private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) {
62            int direction = search.getComparator(depth % 3).compare( search, currentNode.location );
63            KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right;
64            KDNode<T> other = (direction < 0) ? currentNode.right : currentNode.left;
65            KDNode<T> best = (next == null) ? currentNode : findNearest(next, search, depth + 1); // Go to a leaf
66            if ( currentNode.location.squaredDistance(search) < best.location.squaredDistance(search)  ) {
67                best = currentNode; // Set best as required
68            }
69            if ( other != null ) {
70                if ( currentNode.location.axisSquaredDistance(search, depth % 3) < best.location.squaredDistance(search) ) {
71                    KDNode<T> possibleBest = findNearest( other, search, depth + 1 );
72                    if (  possibleBest.location.squaredDistance(search) < best.location.squaredDistance(search) ) {
73                        best = possibleBest;
74                    }
75                }
76            }
77            return best; // Work back up
78        }
79    
80        /* backup af udgave med isNodeCompatible
81      private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) {      private KDNode<T> findNearest(KDNode<T> currentNode, T search, int depth) {
82          int direction = search.getComparator(depth % 3).compare( search, currentNode.location );          int direction = search.getComparator(depth % 3).compare( search, currentNode.location );
83          KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right;          KDNode<T> next = (direction < 0) ? currentNode.left : currentNode.right;
# Line 74  public class KDTree<T extends KDNodeComp Line 95  public class KDTree<T extends KDNodeComp
95              }              }
96          }          }
97          return best; // Work back up          return best; // Work back up
98      }      }*/
99  }  }
Legend:
Removed from v.2596  
changed lines
  Added in v.2597
  ViewVC Help
Powered by ViewVC 1.1.20