javaquadtreespace-partitioning

QuadTree for spatial partitioning (Java)

I'm currently trying to implement quadtrees to partition a map. I have done research for the past week and wasn't to successful. I am trying to divide the map up into various rectangles which will be different areas of the map depending on where the person is. I am stuck as I can't get past a depth of 3 in my tree for some reason. The code below is my quadtree class. I have attached the other two class, QuadNode and QuadRectangle. QuadNode is the node in the tree while QuadRectangle is the rectangle which will be the area around the player.

QuadTree:

import java.util.*;

public class QuadTree {


private QuadNode root;
private QuadNode prevNode;
private double[][] points;

private double mapMinX;
private double mapMinY;
private double mapMaxX;
private double mapMaxY;

private int treeDepth;

private List<QuadRectangle> rectangles;

public void insert( double x, double y ){
    QuadRectangle value = new QuadRectangle();
    value.setPoint(x, y);

    if( root == null ){
        //System.out.println("Root");
        QuadNode node = new QuadNode<>( value );
        node.getRect().setLines( mapMinX, mapMinY, mapMaxX, mapMaxY );
        root = node;
    }
    else {
        //System.out.println("New Branch");
        insertRec(root, value);
    }
}

private void insertRec( QuadNode latest, QuadRectangle value ){

    // Check to see if point is in NE -- x > x center AND y > y center
    if ( latest.getRect().getCenterX() < value.getPointX() && latest.getRect().getCenterY() < value.getPointY() ){

        if ( latest.getNE() == null ) {
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getCenterX(), latest.getRect().getCenterY(), latest.getRect().getMaxX(), latest.getRect().getMaxY());
            latest.setNE(temp);
        }
        else {
            insertRec( latest.getNE(), value );
        }

    }
    // Check to see if point is in NW -- x < x center AND y > y center
    else if( latest.getRect().getCenterX() > value.getPointX() && latest.getRect().getCenterY() < value.getPointY() ) {

        if ( latest.getNW() == null ){
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getMinX(), latest.getRect().getCenterY(), latest.getRect().getCenterX(), latest.getRect().getMaxY());
            latest.setNW(temp);
        }
        else {
            insertRec( latest.getNW(), value );
        }
    }
    // Check to see if point is in SE -- x > x center AND y < y center
    else if( latest.getRect().getCenterX() < value.getPointX() && latest.getRect().getCenterY() > value.getPointY() ) {

        if ( latest.getSE() == null ){
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getCenterX(), latest.getRect().getMinY(), latest.getRect().getMaxX(), latest.getRect().getCenterY());
            latest.setSE(temp);
        }
        else {
            insertRec( latest.getSE(), value );
        }
    }
    // Check to see if point is in SW -- x < x center AND y < y center
    else if( latest.getRect().getCenterX() > value.getPointX() && latest.getRect().getCenterY() > value.getPointY() ) {

        if ( latest.getSW() == null ){
            QuadNode temp = new QuadNode<>(value);
            temp.getRect().setLines(latest.getRect().getMinX(), latest.getRect().getMinY(), latest.getRect().getCenterX(), latest.getRect().getCenterY());
            latest.setSW(temp);
        }
        else {
            insertRec( latest.getSW(), value );
        }
    }
}

public QuadTree( double[][] vals, double minX, double minY, double maxX, double maxY ){

    rectangles = new ArrayList<>();

    points = vals.clone();

    mapMinX = minX;
    mapMinY = minY;
    mapMaxX = maxX;
    mapMaxY = maxY;

    //orderPointsCounterClock();

    for( int ii = 0; ii < vals[0].length; ii++){
        insert(vals[0][ii], vals[1][ii]);
    }

    treeDepth = getDepth(root);
    System.out.println(treeDepth);

    addToList(root);



    new DrawQuadTree( vals, rectangles ).setVisible(true);

}

private void orderPointsCounterClock(){
    double originX = (mapMaxX + mapMinX) / 2;
    double originY = (mapMaxY + mapMinY) / 2;

    List<double[]> pointsDistance = new ArrayList<>();

    boolean distFlag = true;

    for( int ii = 0; ii <  points[0].length; ii++){
        double sqX = Math.pow( originX - points[0][ii], 2);
        double sqY = Math.pow( originY - points[1][ii], 2);
        double pointToOriginDist = Math.sqrt( sqX + sqY );

        for(int jj = ii; jj < points[0].length; jj++){
            double tempDist = Math.sqrt( Math.pow( originX - points[0][ii], 2) + Math.pow( originY - points[1][ii], 2) );
            if( tempDist > pointToOriginDist ){
                distFlag = false;
            }
        }

        if( distFlag ){
            pointsDistance.add( new double[]{ points[0][ii], points[1][ii] });
        }
    }

    for( double[] l : pointsDistance ){
        System.out.println( l[0] + " :: " + l[1] );
    }

}

private int getDepth( QuadNode root ){
    if( root == null ){
        return 0;
    }
    else{
        List maxValues = new ArrayList<>();

        maxValues.add( 1 + getDepth( root.getNE() ));
        maxValues.add( 1 + getDepth( root.getNW() ));
        maxValues.add( 1 + getDepth( root.getSE() ));
        maxValues.add( 1 + getDepth( root.getSW() ));

        Collections.sort(maxValues);
        return (int)maxValues.get( maxValues.size() - 1 );
    }
}

public void addToList( QuadNode root ){
    if( root != null ){
        prevNode = root;
        if( !rectangles.contains( prevNode.getRect() )) {
            rectangles.add(prevNode.getRect());
        }
        addToList( root.getNE() );
        addToList( root.getNW() );
        addToList( root.getSE() );
        addToList( root.getSW() );
    }
    else{
        if( !rectangles.contains( prevNode.getRect() )) {
            rectangles.add(prevNode.getRect());
        }
    }
}
}

QuadNode:

public class QuadNode<T> {

private QuadRectangle rect;
private QuadNode NE, NW, SE, SW;

public QuadNode( QuadRectangle value ){
    this.rect = value;
    this.NE = null;
    this.NW = null;
    this.SE = null;
    this.SW = null;
}

public QuadRectangle getRect() {
    return rect;
}

public void setNE(QuadNode NE) {
    this.NE = NE;
}

public void setNW(QuadNode NW) {
    this.NW = NW;
}

public void setSE(QuadNode SE) {
    this.SE = SE;
}

public void setSW(QuadNode SW) {
    this.SW = SW;
}

public QuadNode getNE() {
    return NE;
}

public QuadNode getNW() {
    return NW;
}

public QuadNode getSE() {
    return SE;
}

public QuadNode getSW() {
    return SW;
}
}

QuadRectangle:

public class QuadRectangle {
private Point[] line1;
private Point[] line2;
private Point[] line3;
private Point[] line4;

private double pointX;
private double pointY;

private double centerX;
private double centerY;

public void setOnlyPoint(boolean onlyPoint) {
    this.onlyPoint = onlyPoint;
}

private double minX;
private double minY;
private double maxX;
private double maxY;

private boolean onlyPoint;


public QuadRectangle(){
    line1 = new Point[2];
    line2 = new Point[2];
    line3 = new Point[2];
    line4 = new Point[2];
}

public void setPoint( double x, double y ){
    this.pointX = x;
    this.pointY = y;
}

public void setLines( double minX, double minY, double maxX, double maxY ){
    this.minX = minX;
    this.minY = minY;
    this.maxX = maxX;
    this.maxY = maxY;

    Point tr = new Point();
    tr.setPoint( maxX, maxY );
    Point tl = new Point();
    tl.setPoint( minX, maxY );
    Point bl = new Point();
    bl.setPoint( minX, minY );
    Point br = new Point();
    br.setPoint( maxX, minY );

    line1[0] = tl;
    line1[1] = tr;
    line2[0] = tr;
    line2[1] = br;
    line3[0] = br;
    line3[1] = bl;
    line4[0] = bl;
    line4[1] = tl;

    centerX = (maxX + minX)/2;
    centerY = (maxY + minY)/2;
}

public boolean contains( double x, double y ){
    Point point = new Point();
    point.setPoint(x, y);
    if( line1[0].xCord < point.xCord && line1[1].xCord > point.xCord ){
        if( this.line2[0].yCord > point.yCord && this.line2[1].yCord < point.yCord ){
            return true;
        }
        else{
            return false;
        }
    }
    else{
        return false;
    }
}

public double getPointX(){
    return this.pointX;
}

public double getPointY(){
    return this.pointY;
}

public double getCenterX() {
    return centerX;
}

public double getCenterY() {
    return centerY;
}

public double getMinX() {
    return minX;
}

public double getMinY() {
    return minY;
}

public double getMaxX() {
    return maxX;
}

public double getMaxY() {
    return maxY;
}

public Point[] getLine1() {
    return line1;
}

public Point[] getLine2() {
    return line2;
}

public Point[] getLine3() {
    return line3;
}

public Point[] getLine4() {
    return line4;
}

I apologize for the amount of code here. I've been stuck for a few days and I'm not sure where to go from here.

Solution

  • There are many implementations. I just created one, you can take a look if it can clarify your thoughts: https://github.com/pvto/java-quadtree/blob/master/src/main/java/struct/quadtree/QuadTree.java .

    The idea is to make all comparisons in your QuadNode. You can remove QuadRectangle altogether and replace it by two pairs of coordinates, (x1,y1) (upper left corner), and (x2,y2) (lower right corner). When you create your QuadNode, you set x1,y1,x2,y2 then and there and never change them afterwards.

    You can either store only one item of some type in that QuadNode, or store a list of items like I did. If it has child QuadNodes created, then it should store no item, and the same other way round.

    Hopefully this helped a bit.