Вставка объекта в квадри в Java - PullRequest
1 голос
/ 20 октября 2011

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

У меня есть класс Quadtree, который содержит узел с именем root.Класс Node состоит из четырех узлов, которые составляют четыре четырехугольника.Корневой узел создается при создании дерева квадов, а четыре узла внутри каждого узла не создаются, пока я не вызову createChildrenQuads ().Однако для корневого узла этот метод вызывается при создании четырехугольного дерева.

Поэтому мой мысли о том, как вставить элемент в узел, выглядит следующим образом:

  1. Startв корневом узле
  2. Для каждого узла:
    1. Проверьте и посмотрите, к какому из четырех дочерних узлов текущего узла подходит текущий элемент
    2. Если он подходит к одному из них, вставьтев этот узел (вызовите рекурсивный метод и начните сначала)
    3. Если он не вписался ни в один, добавьте его в список объектов текущего узла и все будет сделано

Исходя из этого, я создал это:

public void insert(Entity e) {
    insert(root, e);
}

private void insert(Node n, Entity e){
    Rectangle temp = e.getRectangle();

    if (!n.childrenHaveBeenCreated())
        n.createChildrenQuads(n.m_quadRect);

    //first check which node it can go into

    if ( n.NW.m_quadRect.contains(temp)) {
        n.NW = insert(n.NW, e);
        return;
    }

    if ( n.NE.m_quadRect.contains(temp)) {
        n.NE = insert(n.NE, e);
        return;
    }

    if ( n.SW.m_quadRect.contains(temp)) {
        n.SW = insert(n.SW, e);
        return;
    }

    if ( n.SE.m_quadRect.contains(temp)) {
        n.SE = insert(n.SE, e);
        return;
    }

    n.m_objects.add(e);
}

Я думаю, что в квадратичном направлении логика у меня там хорошая.Когда я отлаживаю код, похоже, все работает как надо.Однако я считаю, что моя проблема в том, что Java передает параметры по значению, а не по ссылке, поэтому, хотя я добавляю их в нужное место, они не «сохраняются», потому что это просто локальная переменная.Я полагаю, что это проблема, но я могу ошибаться.

Поэтому я попытался немного изменить его, чтобы сделать так, чтобы метод вставки возвращал текущий узел, чтобы все правильно "сохранялось".Вот что я придумал:

public void insert(Entity e) {
    root = insert(root, e);
}

private Node insert(Node n, Entity e) {
    Rectangle temp = s.getRectangle();

    if (!n.childrenHaveBeenCreated())
        n.createChildrenQuads(n.m_quadRect);

    //first check which node it can go into

    if ( n.NW.m_quadRect.contains(temp)) {
        n.NW = insert(n.NW, e);
        return n;
    }

    if ( n.NE.m_quadRect.contains(temp)) {
        n.NE = insert(n.NE, e);
        return n;
    }

    if ( n.SW.m_quadRect.contains(temp)) {
        n.SW = insert(n.SW, e);
        return n;
    }

    if ( n.SE.m_quadRect.contains(temp)) {
        n.SE = insert(n.SE, e);
        return n;
    }

    n.m_objects.add(e);
    return n;
}

Однако у меня все еще остается та же проблема.Теперь я не уверен, в чем заключается моя проблема.

Я использую это для игры, и у меня это есть, так что он рисует контур вокруг всех квадов, и я могу нажать, чтобы добавитьСущность в квадри.Обе версии моего кода, кажется, действуют одинаково.Что происходит, когда я добавляю сущность в quadtree, она добавляется и остается там, поэтому я предполагаю, что моя теория о том, что она не «сохраняется» из-за того, как Java передает ссылки, неверна.

Однако мой код должен (по крайней мере, на мой взгляд) поместить каждую сущность в квадродерево так низко, насколько это возможно, создавая новые дочерние четырехугольники в каждом узле по мере его спуска в дерево.Однако на самом деле происходит то, что иногда кажется, что он просто добавляет новую сущность в текущий квад, не спускаясь по дереву вообще, или он спускается на один или два уровня, и это так, когда он может легко спуститься на несколькобольше уровней.

Кто-нибудь может увидеть что-нибудь не так с кодом или моей логикой вообще?

1 Ответ

2 голосов
/ 20 октября 2011

Я думаю, что именно так вы структурировали свою программу.Quadtree получает возможность тестировать каждый квадрант, но он также всегда добавляет элемент в конце ... Так что, даже несмотря на то, что он будет рекурсивно пробиваться ко дну, на обратном пути он всегда будет запускать ваш последний n.m_objects.add(e); , поэтому изменяясьгде это добавлено на пути назад через рекурсию.Вам нужно изменить его на более If (..) else if (...) else (...)

...