0
私はランダムに生成されたポイントのリストから3D KDツリーを構築しようとしています。私はこのタスクを再帰的にも達成しようとしています。しかし私の再帰では、ポイントのリストを分割しようとしているときにエラーに直面しています。私のコードは次の通りです：3D KDツリーを構築する
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;
}
}
クラスポイントは、x、y、z座標を含む単純なオブジェクトです。ツリーの深さに基づいて3つのコンパレータが使用されました。次のように私は取得しています エラーがある：あなたが真ん中= points.sizeを行う際
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)