Hey Leute,
hoffe ihr könnt mir helfen.
Ich versuche eine k-d Tree in Java zu implementieren, jedoch passt es nicht ganz (ich kriege einen Stack Overflow)
Hier mal meine Tree-Node (Also ein Knoten/Blatt im Baum)
Und hier der Algorithmus zum bauen des Baumes:
Und die Punktemenge die ich verwende:
Jedoch wiederholt er ab der 2ten Ebene immer den linken Teilbaum mit 2 Einträgen, und er verkleinert die Liste nicht.
Könnte mir jemand sagen wie ich das lösen kann?
mfg,
blawa
hoffe ihr könnt mir helfen.
Ich versuche eine k-d Tree in Java zu implementieren, jedoch passt es nicht ganz (ich kriege einen Stack Overflow)
Hier mal meine Tree-Node (Also ein Knoten/Blatt im Baum)
Java:
public class TreeNode {
public TreeNode left,right;
public Point2D punkt;
public String line_name="";
}
Und hier der Algorithmus zum bauen des Baumes:
Java:
public class MakeKDTree {
private static int line_cnt=0;
public static TreeNode makeKDTree(LinkedList<Point2D> sortiertePunkte, int tiefe) {
LinkedList<Point2D> punkte1 = new LinkedList<Point2D>();
LinkedList<Point2D> punkte2 = new LinkedList<Point2D>();
if(sortiertePunkte.size()==0) return null;
if(sortiertePunkte.size()==1) {
TreeNode tn = new TreeNode();
tn.punkt=sortiertePunkte.getFirst();
return tn;
}
splitTree(sortiertePunkte,punkte1,punkte2,sortiertePunkte.getFirst(),tiefe);
TreeNode tlinks = new TreeNode();
TreeNode trechts = new TreeNode();
tlinks = makeKDTree(punkte1,tiefe+1);
trechts = makeKDTree(punkte2,tiefe+1);
TreeNode v = new TreeNode();
line_cnt++;
v.line_name = "L"+line_cnt;
v.left=tlinks;
v.right=trechts;
return v;
}
private static void splitTree(LinkedList<Point2D> allePunkte, LinkedList<Point2D> punkte1, LinkedList<Point2D> punkte2, Point2D splitPunkt, int tiefe ) {
Iterator<Point2D> iter1 = allePunkte.iterator();
while(iter1.hasNext()) {
Point2D temp = iter1.next();
if(tiefe%2==0) {
if(temp.getX()<=splitPunkt.getX()) {
punkte1.add(temp);
}
else {
punkte2.add(temp);
}
}
else {
if(temp.getY()<=splitPunkt.getY()) {
punkte1.add(temp);
}
else {
punkte2.add(temp);
}
}
}
}
}
Und die Punktemenge die ich verwende:
Java:
Point2D p1 = new Point2D(3,4);
punktListe.add(p1);
Point2D p2 = new Point2D(5,5);
punktListe.add(p2);
Point2D p3 = new Point2D(1,6);
punktListe.add(p3);
Point2D p4 = new Point2D(2,2);
punktListe.add(p4);
Point2D p5 = new Point2D(6,1);
punktListe.add(p5);
Jedoch wiederholt er ab der 2ten Ebene immer den linken Teilbaum mit 2 Einträgen, und er verkleinert die Liste nicht.
Könnte mir jemand sagen wie ich das lösen kann?
mfg,
blawa