Я создаю квадродерево и мне нужно помочь вставить объект в него.Я понимаю концепцию этого, но я не очень хорош в рекурсии и в том, как Java передает переменные.
У меня есть класс Quadtree, который содержит узел с именем root.Класс Node состоит из четырех узлов, которые составляют четыре четырехугольника.Корневой узел создается при создании дерева квадов, а четыре узла внутри каждого узла не создаются, пока я не вызову createChildrenQuads ().Однако для корневого узла этот метод вызывается при создании четырехугольного дерева.
Поэтому мой мысли о том, как вставить элемент в узел, выглядит следующим образом:
- Startв корневом узле
- Для каждого узла:
- Проверьте и посмотрите, к какому из четырех дочерних узлов текущего узла подходит текущий элемент
- Если он подходит к одному из них, вставьтев этот узел (вызовите рекурсивный метод и начните сначала)
- Если он не вписался ни в один, добавьте его в список объектов текущего узла и все будет сделано
Исходя из этого, я создал это:
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 передает ссылки, неверна.
Однако мой код должен (по крайней мере, на мой взгляд) поместить каждую сущность в квадродерево так низко, насколько это возможно, создавая новые дочерние четырехугольники в каждом узле по мере его спуска в дерево.Однако на самом деле происходит то, что иногда кажется, что он просто добавляет новую сущность в текущий квад, не спускаясь по дереву вообще, или он спускается на один или два уровня, и это так, когда он может легко спуститься на несколькобольше уровней.
Кто-нибудь может увидеть что-нибудь не так с кодом или моей логикой вообще?