Как мне написать рекурсивный метод обхода Quadtree в Java? - PullRequest
Новая
       23

Как мне написать рекурсивный метод обхода Quadtree в Java?

0 голосов
/ 17 мая 2018

Я понимаю концепцию, но не знаю, как написать код в Java. Насколько я понимаю, вы спускаетесь вниз, чтобы проверить, является ли следующий узел листом, если нет, то вы продолжаете спускаться, затем вы возвращаетесь назад и делаете это для других. Но как мне это написать?

Вот мой конструктор для дерева quadtree 

public class QuadtreeBitmap {
// location
private final int x;
private final int y;
// height and width
private final int size;
// if leaf
private boolean leaf;
// either Colour.BLACK or Colour.WHITE
private Colour colour;
// otherwise
private QuadtreeBitmap northWest;
private QuadtreeBitmap northEast;
private QuadtreeBitmap southWest;
private QuadtreeBitmap southEast;

/**
 * Constructs a new quadtree bitmap with height and width equal to the specified size, and 
 * every pixel initialized to the given colour. The specified size must be a power of 2, 
 * and must be greater than zero.
 * 
 * @param size the height and width of this quadtree bitmap
 * @param colour the colour with which to initialize every pixel in this quadtree bitmap
 */
public QuadtreeBitmap(int size, Colour colour) {
    this(0, 0, size, colour);
}
/**
 * Constructs a new quadtree bitmap with height and width equal to the specified size, and 
 * every pixel initialized to white. The specified size must be a power of 2, and must be 
 * greater than zero.
 * 
 * @param size the height and width of this quadtree bitmap
 */
public QuadtreeBitmap(int size) {
    this(0, 0, size, Colour.WHITE);
}

// specifying location only supported internally
private QuadtreeBitmap(int x, int y, int size, Colour colour) {
    // only supporting power-of-2 dimensions
    if (!powerOfTwo(size)) {
        throw new IllegalArgumentException("Size not power of 2.");
    }
    this.x = x;
    this.y = y;
    this.size = size;
    this.leaf = true;
    this.colour = colour;
    this.northWest = null;
    this.northEast = null;
    this.southWest = null;
    this.southEast = null;
}
// combining quads to form tree only supported internally, assumes well-positioned
private QuadtreeBitmap(int x, int y, int size, List<QuadtreeBitmap> quads) {
    this(x, y, size, Colour.WHITE);
    northWest = quads.get(0);
    northEast = quads.get(1);
    southWest = quads.get(2);
    southEast = quads.get(3);
    this.leaf = false;
}

// for any basic task which needs to be repeated all four quadrants
private List<QuadtreeBitmap> quadrants() {
    return Arrays.asList(northWest, northEast, southWest, southEast);
}

// retrieves the quadrant within which the specified location lies
private QuadtreeBitmap quadrantOf(int x, int y) {
    for (QuadtreeBitmap quad : quadrants()) {
        if (quad.containsPoint(x, y)) {
            return quad;
        }
    }
    return null;
}


public int getSize() {
    return size;
}

По сути, мне нужно реализовать целый набор методов для назначения, таких как подсчет пикселей определенного цвета и т. Д., Но я не знаю, с чего начать

1 Ответ

0 голосов
/ 17 мая 2018

Давайте упростим.Как бы вы написали обход бинарного дерева?

Ну, вы бы написали такую ​​функцию, как 

public int CountNodes(){
    int leftcount = (this.left==null) ? 0 : this.left.CountNodes();
    int rightcount = (this.right==null) ? 0 : this.right.CountNodes();
   return 1 + leftcount + rightcount;
}

Так что вы хотите реализовать это с вашими фиксированными внутренними значениями northEast, northWest, southEast, southWest вместо 'left' и 'right».Обратите внимание, что значение +1 в значении узла учитывает сам узел, что делает явную «проверку листа» ненужной.

Следует отметить, что вам необходимо знать об ограничениях размера стека в вашей среде.Раньше у Foxpro была ограниченная высота стека, равная 32 вызовам, и подобные рекурсивные вызовы могут углубляться с очень большими объектами.

...