Sorry If Im too generic.
It can change completely at any time, either in number of points or size.
So I’ve started writing a class that allows for more flexibility, Ill show you what I have so far.
[quote]class QuadTreeNode{
private QuadTreeNode[] children;
private double x, y, width, height;
private Setcontents;
private BoundingBox boundingBox;
public QuadTreeNode(double x, double y, double width, double height){
this.x = x;
this.y = y;
this.width = width;
this.height = height;
boundingBox = new BoundingBox(x,y,x + width, y + height);
contents = new ArraySet<Point>();
children = new QuadTreeNode[4];
}
public int size(){
return contents.size();
}
public boolean isInside(double x, double y){
return boundingBox.isInside(x, y);
}
public void split(double x, double y){
double halfW = width / 2;
double halfH = height / 2;
children[0] = new QuadTreeNode(x - halfW, y - halfH, width/2, height/2);
children[1] = new QuadTreeNode(x - halfW, y, width/2, height/2);
children[2] = new QuadTreeNode(x, y - halfH, width/2, height/2);
children[3] = new QuadTreeNode(x, y, width/2, height/2);
}
public void add(Point point){
if(children[0].isInside(point.getX(), point.getY())
&& children[0] != null){
if(children[0].size()>0){
children[0].split(point.getX(),point.getY());
}
children[0].add(point);
} else
if(children[1].isInside(point.getX(), point.getY())
&& children[1] != null){
if(children[1].size()>0){
children[1].split(point.getX(),point.getY());
}
children[1].add(point);
} else
if(children[2].isInside(point.getX(), point.getY())
&& children[2] != null){
if(children[2].size()>0){
children[2].split(point.getX(),point.getY());
}
children[2].add(point);
} else
if(children[3].isInside(point.getX(), point.getY())
&& children[3] != null){
if(children[3].size()>0){
children[3].split(point.getX(),point.getY());
}
children[3].add(point);
} else {
contents.add(point);
}
}
private class BoundingBox{
private double minX, minY;
private double maxX, maxY;
BoundingBox(double minX, double minY, double maxX, double maxY){
this.minX = minX;
this.minY = minY;
this.maxX = maxX;
this.maxY = maxY;
}
public boolean isInside(double x, double y){
if(x > minX && x < maxX)
if(y > minY && y < maxY)
return true;
return false;
}
}
}
[/quote]
Its not finished yet but it should give you an idea. I need tio figure out how to get and alter the tree as data changes.
So now I have my tree if I have an x and y coordinate how would I go about using the tree to find the closest point in an efficient way?
EDIT: I have also come across another problem, I do not have set extents to the active area so if I setup a quadTree and then a point is added outside its extents Im abit stuffed…
