用于空间分区的四叉树 (Java)

Question

我目前正在尝试实现四叉树来划分地图。过去一周我做了研究，但没有成功。我试图将地图分成不同的矩形，这些矩形将根据人所在的位置成为地图的不同区域。由于某种原因，我无法在树中超过 3 的深度，因此我被卡住了。下面的代码是我的四叉树class。我附上了另外两个 class，QuadNode 和 QuadRectangle。 QuadNode 是树中的节点，而 QuadRectangle 是将成为玩家周围区域的矩形。

四叉树：

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());
        }
    }
}
}

四元节点：

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;
}
}

四边形：

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;
}

对于这里的代码量，我深表歉意。我已经被困了几天，我不知道从这里去哪里。

Answer 1

有很多实现。我刚刚创建了一个，你可以看看它是否可以阐明你的想法：https://github.com/pvto/java-quadtree/blob/master/src/main/java/struct/quadtree/QuadTree.java .

我们的想法是在您的 QuadNode 中进行所有比较。您可以完全删除 QuadRectangle 并将其替换为两对坐标，(x1,y1)（左上角）和 (x2,y2)（右下角）。当您创建您的 QuadNode 时，您会在那里设置 x1、y1、x2、y2，之后永远不会更改它们。

您可以在该 QuadNode 中仅存储某种类型的一个项目，也可以像我一样存储项目列表。如果它创建了子 QuadNode，那么它不应该存储任何项目，反之亦然。

希望这对您有所帮助。

用于空间分区的四叉树 (Java)

QuadTree for spatial partitioning (Java)

java

quadtree

space-partitioning