Konstruktion eines 3D-KD-Baum

Question

So versuche ich, eine 3D-KD-Baum aus einer Liste zu konstruieren, der zufällig Punkte erzeugt. Ich versuche diese Aufgabe auch rekursiv zu erledigen. Aber bei meiner Rekursion sehe ich einen Fehler, wenn ich versuche, meine Punkteliste zu partitionieren. Mein Code ist wie folgt:

public class Scratch { 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 
     ArrayList<Point> points = new ArrayList<Point>(); 
     Random rand = new Random(System.currentTimeMillis()); 
     for (int i = 0; i < 100; i++) { 
      double x = rand.nextInt(100); 
      double y = rand.nextInt(100); 
      double z = rand.nextInt(100); 
      Point point = new Point(x, y, z); 
      points.add(point); 
     } 
     Node root = kdtree(points, 0); 
     System.out.println("Done"); 
    } 

    static class Node { 

     Node leftChild; 
     Node rightChild; 
     Point location; 

     Node() { 

     } 

     Node(Node leftChild, Node rightChild, Point location) { 
      this.leftChild = leftChild; 
      this.rightChild = rightChild; 
      this.location = location; 
     } 
    } 

    public static Node kdtree(ArrayList<Point> points, int depth) { 
     int axis = depth % 3; 
     switch (axis) { 
      case 0: 
       Collections.sort(points, Point.X_COMPARATOR); 
       break; 
      case 1: 
       Collections.sort(points, Point.Y_COMPARATOR); 
       break; 
      case 2: 
       Collections.sort(points, Point.Z_COMPARATOR); 
       break; 
      default: 
       break; 
     } 
     int middle = points.size()/2; 
     Point median = points.get(middle); 

     ArrayList<Point> greater = new ArrayList<Point>(points.subList(0, (middle - 1))); 
     ArrayList<Point> lesser = new ArrayList<Point>(points.subList((middle + 1), (points.size()))); 
     Node node = new Node(); 
     node.location = median; 
     if(greater.size() == 0 || lesser.size() == 0) { 
      node.leftChild = null; 
      node.rightChild = null; 
     } else { 
      node.leftChild = kdtree(lesser, depth + 1); 
      node.rightChild = kdtree(greater, depth + 1); 
     }   
     return node; 
    } 

} 

Der Klassenpunkt ist ein einfaches Objekt, das eine x, y und z-Koordinate enthält. Und drei Komparatoren verwendet basierend auf der Tiefe des Baumes. Der Fehler Ich erhalte ist wie folgt:

Exception in thread "main" java.lang.IllegalArgumentException: fromIndex(0) > toIndex(-1) 
    at java.util.ArrayList.subListRangeCheck(ArrayList.java:1006) 
    at java.util.ArrayList.subList(ArrayList.java:996) 
    at scratch.Scratch.kdtree(Scratch.java:71) 
    at scratch.Scratch.kdtree(Scratch.java:80) 
    at scratch.Scratch.kdtree(Scratch.java:79) 
    at scratch.Scratch.kdtree(Scratch.java:79) 
    at scratch.Scratch.kdtree(Scratch.java:79) 
    at scratch.Scratch.kdtree(Scratch.java:79) 
    at scratch.Scratch.main(Scratch.java:32) 

Answer 1

Im gehend, gehen Sie auf eine Vermutung hier und sagen, dass, wenn Sie nur einen Punkt (oder 0) auf dem Punkte-Array, wenn Sie Mitte tun = points.size/2, das gleich 0 ist (Ganzzahlige Division), und wenn Sie dann versuchen, eine Unterliste von 0 bis -1 zu erstellen, wird diese Ausnahme ausgelöst.