QuadTree для пространственного разбиения (Java)

Question

В настоящее время я пытаюсь реализовать квадранты для разбиения карты. Я провел исследования на прошлой неделе и не был успешным. Я пытаюсь разделить карту на различные прямоугольники, которые будут разными областями карты в зависимости от того, где находится человек. Я застрял, потому что по какой-то причине я не могу пройти глубину 3 в моем дереве. Код ниже - мой класс квадрантов. Я добавил два других класса: 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()); 
     } 
    } 
} 
} 

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

Я извиняюсь за количество кода здесь. Я застрял в течение нескольких дней, и я не уверен, куда идти отсюда.

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, либо сохранить список элементов, как я. Если у него есть дочерние QuadNodes, то он не должен хранить ни одного элемента, а также наоборот.

Надеюсь, это немного помогло.