如何在 QuadTree 中的所有相交四边形中插入节点？

Question

我有一个四叉树，但插入方法无法正常工作。现在它只插入它看到的第一个相交四边形。目的是将所有节点插入与其相交的所有四边形中。例如：当一个节点在两个四边形的边界上时，它被插入到两个四边形中。有人可以帮助我将插入方法插入到所有相交四边形中吗？

这是我当前的实现：

这是插入节点的调用：

QuadTree = new QuadTreeNode < Artist > (new Rect(0, 0, Width, Height), 1);
foreach(Artist artist in Artists) {
  QuadTree.Insert(artist);
}

这是我的四叉树class:

public interface WithRect {
  Rect Rect {
    get;
  }
}

public class QuadTreeNode < T > where T: WithRect {
  Rect bounds;
  List < T > contents;
  int numberOfNodesInserted = 0;
  int max = 4;
  int depth = 0;
  int maxDepth = 6;
  bool divided;

  QuadTreeNode < T > TopLeft;
  QuadTreeNode < T > TopRight;
  QuadTreeNode < T > BottomLeft;
  QuadTreeNode < T > BottomRight;

  public QuadTreeNode(Rect _bounds, int _depth) {
    depth = _depth;
    bounds = _bounds;
    contents = new List < T > ();
    divided = false;
  }

  public void DivideQuad() {
    int newDepth = depth + 1;
    double x = bounds.X;
    double y = bounds.Y;
    double width = bounds.Width;
    double height = bounds.Height;

    TopLeft = new QuadTreeNode < T > (new Rect(x, y, width / 2, height / 2), newDepth);
    TopRight = new QuadTreeNode < T > (new Rect(x + width / 2, y, width / 2, height / 2), newDepth);
    BottomLeft = new QuadTreeNode < T > (new Rect(x, y + height / 2, width / 2, height / 2), newDepth);
    BottomRight = new QuadTreeNode < T > (new Rect(x + width / 2, y + height / 2, width / 2, height / 2), newDepth);
    divided = true;

    foreach(T item in contents) {
      Insert(item);
    }
    contents.Clear();
  }

  public bool Insert(T item) {
    if (!bounds.IntersectsWith(item.Rect)) return false;
    
    if (numberOfNodesInserted < max || depth == maxDepth) {
      contents.Add(item);
      numberOfNodesInserted++;
      return true;
    }
    else {
      if (!divided) {
        DivideQuad();
      }

      if (TopLeft.Insert(item)) return true;
      else if (TopRight.Insert(item)) return true;
      else if (BottomLeft.Insert(item)) return true;
      else if (BottomRight.Insert(item)) return true;
      else return false;
    }
  }

  public void GetBounds(ref List < Rect > results) {
    if (bounds != null) results.Add(bounds);

    if (TopLeft != null) TopLeft.GetBounds(ref results);
    if (TopRight != null) TopRight.GetBounds(ref results);
    if (BottomLeft != null) BottomLeft.GetBounds(ref results);
    if (BottomRight != null) BottomRight.GetBounds(ref results);
  }

  public void Query(T item, ref List < T > collisions, List < Square > squares, int squareWidth, int squareHeight) {
    if (item.Rect.IntersectsWith(bounds)) {
      if (divided) {
        TopLeft.Query(item, ref collisions, squares, squareWidth, squareHeight);
        TopRight.Query(item, ref collisions, squares, squareWidth, squareHeight);
        BottomLeft.Query(item, ref collisions, squares, squareWidth, squareHeight);
        BottomRight.Query(item, ref collisions, squares, squareWidth, squareHeight);
      }

      for (int i = 0; i < contents.Count; i++) {
        if (item.Rect != contents[i].Rect) {
          if (item.Rect.IntersectsWith(contents[i].Rect)) {
            if (!collisions.Contains(contents[i])) {
              collisions.Add(contents[i]);
            }
          }
        }
        foreach(Square square in squares) {
          if (square.IsVisited) {
            if (item.Rect.IntersectsWith(new Rect(square.X * squareWidth, square.Y * squareHeight, squareWidth, squareHeight))) {
              if (!collisions.Contains(contents[i])) {
                collisions.Add(contents[i]);
              }
            }
          }
        }
      }
    }
  }
}

Answer 1

从 else if 中删除 else 以确保将项目插入到其每个子节点。

if (TopLeft.Insert(item)) return true;
else if (TopRight.Insert(item)) return true;
else if (BottomLeft.Insert(item)) return true;
else if (BottomRight.Insert(item)) return true;
else return false;

应该是

var result = TopLeft.Insert(item);
result  |= TopRight.Insert(item);
result  |= BottomLeft.Insert(item);
result  |= BottomRight.Insert(item);
return result;

另一个问题是

if (numberOfNodesInserted < max || depth == maxDepth)

如果节点被分割，你不应该向节点插入项目，所以它应该是：

if (!divided && (numberOfNodesInserted < max || depth == maxDepth))

也就是说，假设您只在叶节点中存储项目。

如何在 QuadTree 中的所有相交四边形中插入节点？

How to insert node in all intersecting quads in QuadTree?

c#

quadtree