为什么这个四叉树查询经常什么也不返回？

Question

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

我试图写一些通用的四叉树代码，用于物理模拟和游戏设计。首先，它返回四叉树内容中的所有点，这些内容被搜索区域完全包围。在添加了一堆print()语句来说明这个过程之后，我设法解决了这个问题，但是现在我有了一个新的问题，我似乎搞不清楚。由于某些原因，当我查询矩形区域内的“Placeable”四叉树时，我要么得到一个完全正确的结果，但更多的情况下，我没有得到任何返回。Placeable的定义如下：

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窗口中正确输出的示例：

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 

正确的输出图像：

​

下面是一个应该返回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 

这是与不正确的输出一起的窗口。(发现点变为纯绿色。)

​

我还没有发现一个区域产生正确输出的模式，但是我的直觉说左边的区域更多的是不正确的。

完整的文件是可用的这里，所以你可以运行它，如果你需要，但我很困惑，我已经回到这几次在过去一周。请帮帮忙。

Answer 1

哇，这是一个很难找到的问题(至少，我希望我解决了)。

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

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时只需使用rH

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