为什么这个 Quadtree Query 经常 returns 什么都没有？

Question

任何“W”均指半宽，任何“H”均指半高。任何“X”和“Y”都是指与坐标轴对齐的矩形的中心。

我正在尝试编写一些用于物理模拟和游戏设计的通用四叉树代码。起初它返回四叉树内容中的所有点，该四叉树完全被搜索区域包围。在添加了一堆 print() 语句来阐明我设法解决该问题的过程之后，但现在我有了一个我似乎无法弄清楚的新问题。出于某种原因，当我在四叉树中查询矩形区域内的“Placeables”时，我要么得到完全正确的结果，但通常我什么也得不到。 Placeables定义如下：

abstract class Placeable{ //things that can be stored in quadtree
  PVector pos;
  abstract void show();}

四叉树代码的重要部分：

class Quadtree{ //Data structure for storing objects in 2D
  Quadtree nw,ne,sw,se; //children
  Quadtree parent;
  ArrayList<Placeable> contents;//contents of THIS branch only, child object contents not included
  float x,y,w,h;//center point, half-width and half-height
  boolean divided;  //false if leaf node
  static final int capacity = 6; //controls maximum capacity all quadtree nodes for case-by-case tuning 
...

...
boolean intersects(float rX, float rY, float rW, float rH){//Do I intersect with the rectangle defined by rX,rY,rW,rH?
    return !(rX-rW >= x+w || rX+rW <= x-w 
          || rY-rH >= y+h || rY+rH <= y-h);}
      
  //return all Placeables inside a rectangular region
  ArrayList<Placeable> query(float X, float Y, float W, float H){
    return query(X,Y,W,H,new ArrayList<Placeable>());}
  ArrayList<Placeable> query(float X, float Y, float W, float H, ArrayList<Placeable> found){
    print("Querying:",contents.size(),"/",Integer.toString(capacity),"\t");
    
    if (!intersects(X,Y,W,H)){ //if no intersection, return arraylist unmodified
      print("Does Not Intersect\n");
      return found;
    } else {  //if intersection, check contents for Placeables within the region
      print("Does Intersect!\n");
      for (Placeable p : contents){
        if ( (p.pos.x <= X+W) && (p.pos.x >= X-W) //capitals refer to search region
          && (p.pos.y <= Y+H) && (p.pos.y >= Y-H) ){
          found.add(p);
          print("Found Point\t",p.pos.x,"\t",p.pos.y,"\n");}
      }
      if (divided){ //after checking own contents, recursively query children appending to same array
        print("Descending\n");
        print("NW ");
        nw.query(X,Y,W,H,found);
        print("NE ");
        ne.query(X,Y,W,H,found);
        print("SW ");
        sw.query(X,Y,W,H,found);
        print("SE ");
        se.query(X,Y,W,H,found);
        print("Raising\n");}
      return found;
    }
  }
.....
}

以下是在 1024x768 window 下正确输出的示例：

Querying: 6 / 6     Does Intersect!
Descending
NW Querying: 6 / 6  Does Not Intersect
NE Querying: 6 / 6  Does Intersect!
Descending
NW Querying: 4 / 6  Does Not Intersect
NE Querying: 3 / 6  Does Not Intersect
SW Querying: 6 / 6  Does Intersect!
Found Point  665.36365   379.79324 
Descending
NW Querying: 1 / 6  Does Not Intersect
NE Querying: 0 / 6  Does Not Intersect
SW Querying: 0 / 6  Does Intersect!
SE Querying: 0 / 6  Does Intersect!
Raising
SE Querying: 5 / 6  Does Intersect!
Found Point  772.9317    375.3352 
Raising
SW Querying: 6 / 6  Does Not Intersect
SE Querying: 6 / 6  Does Intersect!
Found Point  790.5205    386.4734 
Found Point  633.3443    390.43515 
Found Point  797.5499    397.1355 
Descending
NW Querying: 6 / 6  Does Intersect!
Found Point  723.5054    450.78967 
Found Point  741.98676   389.52292 
Found Point  683.0763    488.69083 
NE Querying: 4 / 6  Does Intersect!
Found Point  775.3038    432.92847 
SW Querying: 6 / 6  Does Not Intersect
SE Querying: 4 / 6  Does Not Intersect
Raising
Raising
Found: 9

正确的输出图像：

下面是同一个window中本应返回3分的错误输出示例：

Querying: 6 / 6     Does Intersect!
Descending
NW Querying: 6 / 6  Does Not Intersect
NE Querying: 6 / 6  Does Not Intersect
SW Querying: 6 / 6  Does Intersect!
Descending
NW Querying: 3 / 6  Does Not Intersect
NE Querying: 5 / 6  Does Not Intersect
SW Querying: 6 / 6  Does Not Intersect
SE Querying: 6 / 6  Does Not Intersect
Raising
SE Querying: 6 / 6  Does Not Intersect
Raising
Found: 0

这是伴随错误输出的 window。（找到的点变为纯绿色。）

我无法发现哪些区域产生正确输出的模式，但我的直觉告诉我左边的区域更经常不正确。

完整文件可用 here，因此您可以运行如果需要，但我很困惑，上周我已经多次回到这个问题。请帮忙。

Answer 1

哇，这个问题好难找（至少，我希望我解决了它）。

问题在于您在 setup() 中定义 rW 和 rH:

rW = constrain(randomGaussian(),-1,1)*width/6;
rH = constrain(randomGaussian(),-1,1)*height/6;

rW 或 rH 不能有负值。例如，假设我们测试以下值（假设 y 值也相交）：

rW = -100;
rX = 500
x = 256;
w = 256;

理想情况下，intersects() 将测试如下：

         !(400 >= 512 || 600 <= 512)
/*-->*/  !(false || false)
/*-->*/  true //(yes, they intersect)

但实际发生的是

         !(rX-rW >= x+w || rX+rW <= x-w)
/*-->*/  !(500-(-100) >= 256+256 || 500+(-100) <= 256-256)
/*-->*/  !(600 >= 512 || 400 <= 0)
/*-->*/  !(true || false)
/*-->*/  false //(no, they do not intersect)

这就像你在测试该地区错误的一面。

这是一个非常简单的修复，只需在定义 rW 和 rH:

时使用 abs()

rW = abs(constrain(randomGaussian(),-1,1))*width/6;
rH = abs(constrain(randomGaussian(),-1,1))*height/6;

为什么这个 Quadtree Query 经常 returns 什么都没有？

Why this Quadtree Query often returns nothing?

java

processing

search

collision-detection

quadtree