QuadTree不能处理许多元素

Question

我目前正在C++中实现自己的C++。它运行良好的100项，但一旦你开始增加更多，它减慢。remove、getAll和insert都被描述为需要一段时间。如有任何建议，敬请谅解！

class QuadTree {
private:
    const static int MAX_OBJECTS = 20;
    AABB bounds;

    std::vector<QuadTree> children;
    std::set<Locatable*> entities;
    std::set<Locatable*> allEntities;

    // Internal methods
    void split() {
        children.clear();

        double width = (bounds.getWidth() / 2);
        double height = (bounds.getHeight() / 2);
        double x = bounds.getX();
        double y = bounds.getY();

        children.push_back(QuadTree(AABB(x + width, y, width, height)));
        children.push_back(QuadTree(AABB(x, y, width, height)));
        children.push_back(QuadTree(AABB(x, y + height, width, height)));
        children.push_back(QuadTree(AABB(x + width, y + height, width, height)));
    }

    int getIndex(AABB& aabb) {
        double vertMid = bounds.getVertMid();
        double horzMid = bounds.getHorzMid();

        // Fits in top
        bool topQuadrant = aabb.getY() + aabb.getHeight() < horzMid;
        // Fits in botom
        bool bottomQuadrant = aabb.getY() > horzMid;

        // Fits in left
        if (aabb.getX() + aabb.getWidth() < vertMid) {
            if (topQuadrant) {
                return 1;
            } else if (bottomQuadrant) {
                return 2;
            }
        }
        // Fits in right
        else if (aabb.getX() > vertMid) {
            if (topQuadrant) {
                return 0;
            } else if (bottomQuadrant) {
                return 3;
            }
        }

        return -1;
    }

    void merge(std::set<Locatable*>& one, std::set<Locatable*> two) {
        one.insert(two.begin(), two.end());
    }
    // End Internal methods
public:
    QuadTree(AABB bounds) : bounds(bounds) {
        children.reserve(4);
    }

    // Base
    void clear() {
        entities.clear();
        allEntities.clear();

        for (auto it = children.begin(); it != children.end(); it++) {
            it->clear();
        }

        children.clear();
    }

void insert(Locatable* object) {
    AABB aabb = object->getAABB();

    allEntities.insert(object);

    if (entities.size() > MAX_OBJECTS) {
        if (children.empty()) {
            split();

            auto it = entities.begin();
            while (it != entities.end()) {
                int index = getIndex((*it)->getAABB());
                if (index != -1) {
                    children.at(index).insert(*it);
                    it = entities.erase(it);
                }
                else {
                    it++;
                }
            }
        }

        int index = getIndex(aabb);
        if (index != -1) {
            children.at(index).insert(object);
        }
        else {
            entities.insert(object);
        }
    }
    else {
        entities.insert(object);
    }
}

    void remove(Locatable* object, AABB aabb) {
        auto it = allEntities.find(object);
        if (it == allEntities.end()) {
            return;
        }
        allEntities.erase(it);

        it = entities.find(object);
        if (it == entities.end()) {
            if (!children.empty()) {
                int index = getIndex(aabb);

                if (index != -1) {
                    children.at(index).remove(object, aabb);
                }
            }
        }
        else {
            entities.erase(it);
        }
    }

    QuadTree* getLowestRoot(AABB aabb) {
        int index = getIndex(aabb);
        if (index == -1 || children.empty()) {
            return this;
        }
        return children.at(index).getLowestRoot(aabb);
    }

    std::set<Locatable*> getAll() {
        std::set<Locatable*> result;
        if (children.empty()) {
            return entities;
        }

        result = entities;
        for (auto it = children.begin(); it != children.end(); it++) {
            merge(result, it->getAll());
        }

        return result;
    }
    // End Base
};

Answer 1

通用说明

• 如果不需要对象的副本，则传递引用而不是值。如果不希望函数更改对象，请使用const引用。
• 如果成员函数不更改对象的状态，则将其声明为const。
• 基于范围的循环比显式使用迭代器更容易读取。
• 单独的头文件和实现文件可以更容易地查看类的概述，而不必费力地浏览血淋淋的详细信息。
• 比较要设置的unordered_set的性能。
• 在下面发布的代码中，我改变了编码风格。你的编码风格没有错。我只是很烦躁，太懒了，不想把它改回来。

AABB

• 用角来定义AABB比一个角落和一个大小更直观。后者并不是错误的，但您可能需要考虑这一选择。
• 我将getIndex()移到AABB类中，因为它更符合逻辑。
• 我简化了getIndex()。

。

class AABB
{
public:
  AABB(double minX,double minY,double maxX,double maxY);
  double getMinX() const;
  double getMinY() const;
  double getMaxX() const;
  double getMaxY() const;
  double getMidX() const;
  double getMidY() const;
  int getQuad(const AABB& aabb) const;
private:
  int getQuad(double x,double y) const;
private:
  double minX;
  double minY;
  double maxX;
  double maxY;
  double midX;
  double midY;
};

AABB::AABB(double minX_,double minY_,double maxX_,double maxY_)
  :minX(minX_),
  minY(minY_),
  maxX(maxX_),
  maxY(maxY_),
  midX((minX_+maxX_)/2.0),
  midY((minY_+maxY_)/2.0)
{}

double AABB::getMinX() const
{
  return minX;
}

double AABB::getMinY() const
{
  return minY;
}

double AABB::getMaxX() const
{
  return maxX;
}

double AABB::getMaxY() const
{
  return maxY;
}

double AABB::getMidX() const
{
  return midX;
}

double AABB::getMidY() const
{
  return midY;
}

int AABB::getQuad(const AABB& aabb) const
{
  int tl = getQuad(aabb.getMinX(),aabb.getMinY());
  int br = getQuad(aabb.getMaxX(),aabb.getMaxY());
  if(tl==br)
    return tl;
  return -1;
}

int AABB::getQuad(double x,double y) const
{
  if(y<getMidY())
  {
    if(x<getMidX())
      return 1;
    else
      return 0;
  }
  else
  {
    if(x<getMidX())
      return 2;
    else
      return 3;
  }
}

可定位

const AABB& getAABB() const;

clear()

• 你不需要给所有的孩子打电话。当你清除病媒时，孩子们就会被消灭。

插入()/拆分()

• 改进后的insert()比原始版本要好得多。
• 不要复制AABB的副本，只是通过参考传递。
• 在insert()中，重新插入实体的代码只在split()之后运行。将代码移到split()中，这样我们就可以使insert()更简单一些。

remove()

• 传递给该函数的AABB与object->getAABB()不同吗？
• 您可以乐观地调用擦除()并读取返回值，而不是使用迭代器。

getAll()

• 通过维护allEntities，您正在做大量的工作。它有你需要的一切。
• 除非有必要，否则不要复制。

getLowestRoot()

• 这个函数很好，但是除了调用getAll()之外，您对返回的对象做任何事情吗？如果没有，请用getAllIn()替换它。

消除实体或allEntities

这些变量是多余的，维护它们都需要太多的开销。与getAll()相比，您应该消除的调用频率取决于调用insert()getAll()的频率。这两个版本都在下面。我对正确性所做的测试很少，所以您可能希望确保这些测试具有与当前版本相同的输出。

class QuadTree
{
private:
  static const int MAX_OBJECTS = 20;
public:
  QuadTree(const AABB& bounds);
  void clear();
  void insert(Locatable* object);
  void remove(Locatable* object);
  void remove(Locatable* object,const AABB& aabb);
  QuadTree* getLowestRoot(const AABB& aabb);
  const std::unordered_set<Locatable*>& getAll() const;
  const std::unordered_set<Locatable*>& getAllIn(const AABB& aabb) const;
private:
  void split();
private:
  AABB bounds;
  std::vector<QuadTree> children;
  std::unordered_set<Locatable*> allEntities;
};

QuadTree::QuadTree(const AABB& bounds)
  :bounds(bounds)
{
  children.reserve(4);
}

void QuadTree::clear()
{
  allEntities.clear();
  children.clear();
}

void QuadTree::insert(Locatable* object)
{
  allEntities.emplace(object);
  if(children.empty())
  {
    if(allEntities.size() > MAX_OBJECTS)
      split();
  }
  else
  {
    int index = bounds.getQuad(object->getAABB());
    if(index!=-1)
      children.at(index).insert(object);
  }
}

void QuadTree::remove(Locatable* object)
{
  if(allEntities.erase(object)!=0 && !children.empty())
  {
    int index = bounds.getQuad(object->getAABB());
    if (index != -1)
      children.at(index).remove(object);
  }
}

void QuadTree::remove(Locatable* object,const AABB& aabb)
{
  if(allEntities.erase(object)!=0 && !children.empty())
  {
    int index = bounds.getQuad(aabb);
    if (index != -1)
      children.at(index).remove(object),aabb;
  }
}

QuadTree* QuadTree::getLowestRoot(const AABB& aabb)
{
  if(children.empty())
    return this;
  int index = bounds.getQuad(aabb);
  if(index == -1)
    return this;
  return children.at(index).getLowestRoot(aabb);
}

const std::unordered_set<Locatable*>& QuadTree::getAll() const
{
  return allEntities;
}

const std::unordered_set<Locatable*>& QuadTree::getAllIn(const AABB& aabb) const
{
  if(children.empty())
    return allEntities;
  int index = bounds.getQuad(aabb);
  if(index == -1)
    return allEntities;
  return children.at(index).getAllIn(aabb);
}

void QuadTree::split()
{
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMinY(),bounds.getMaxX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMinY(),bounds.getMidX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMidY(),bounds.getMidX(),bounds.getMaxY()));
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMidY(),bounds.getMaxX(),bounds.getMaxY()));

  for(Locatable* l : allEntities)
  {
    int index = bounds.getQuad(l->getAABB());
    if(index!=-1)
      children.at(index).insert(l);
  }
}

。

class QuadTree
{
private:
  static const int MAX_OBJECTS = 20;
public:
  QuadTree(const AABB& bounds);
  void clear();
  void insert(Locatable* object);
  void remove(Locatable* object);
  void remove(Locatable* object,const AABB& aabb);
  QuadTree* getLowestRoot(const AABB& aabb);
  void getAll(std::unordered_set<Locatable*>& all) const;
  void getAllIn(std::unordered_set<Locatable*>& all,const AABB& aabb) const;
private:
  void split();
private:
  AABB bounds;
  std::vector<QuadTree> children;
  std::unordered_set<Locatable*> entities;
};

QuadTree::QuadTree(const AABB& bounds)
  :bounds(bounds)
{
  children.reserve(4);
}

void QuadTree::clear()
{
  entities.clear();
  children.clear();
}

void QuadTree::insert(Locatable* object)
{
  if(children.empty())
  {
    entities.emplace(object);
    if(entities.size() > MAX_OBJECTS)
      split();
  }
  else
  {
    int index = bounds.getQuad(object->getAABB());
    if(index==-1)
      entities.emplace(object);
    else
      children.at(index).insert(object);
  }
}

void QuadTree::remove(Locatable* object)
{
  if(entities.erase(object)==0 && !children.empty())
  {
    int index = bounds.getQuad(object->getAABB());
    if(index!=-1)
      children.at(index).remove(object);
  }
}

void QuadTree::remove(Locatable* object,const AABB& aabb)
{
  if(entities.erase(object)==0 && !children.empty())
  {
    int index = bounds.getQuad(aabb);
    if(index!=-1)
      children.at(index).remove(object,aabb);
  }
}

QuadTree* QuadTree::getLowestRoot(const AABB& aabb)
{
  if(children.empty())
    return this;
  int index = bounds.getQuad(aabb);
  if(index == -1)
    return this;
  return children.at(index).getLowestRoot(aabb);
}

void QuadTree::getAll(std::unordered_set<Locatable*>& all) const
{
  for(Locatable* l : entities)
    all.emplace(l);
  if(!children.empty())
  {
    children.at(0).getAll(all);
    children.at(1).getAll(all);
    children.at(2).getAll(all);
    children.at(3).getAll(all);
  }
}

void QuadTree::getAllIn(std::unordered_set<Locatable*>& all,const AABB& aabb) const
{
  if(children.empty())
  {
    getAll(all);
    return;
  }
  int index = bounds.getQuad(aabb);
  if(index == -1)
  {
    getAll(all);
    return;
  }
  return children.at(index).getAllIn(all,aabb);
}

void QuadTree::split()
{
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMinY(),bounds.getMaxX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMinY(),bounds.getMidX(),bounds.getMidY()));
  children.emplace_back(AABB(bounds.getMinX(),bounds.getMidY(),bounds.getMidX(),bounds.getMaxY()));
  children.emplace_back(AABB(bounds.getMidX(),bounds.getMidY(),bounds.getMaxX(),bounds.getMaxY()));

  auto cit = entities.cbegin();
  while(cit!=entities.cend())
  {
    int index = bounds.getQuad((*cit)->getAABB());
    if(index!=-1)
    {
      children.at(index).insert(*cit);
      cit = entities.erase(cit);
    }
    else
      ++cit;
  }
}

其他优化

• 考虑其他数据结构，如k-d树。通过移动枢轴点，可以使树更加平衡。
• 调音MAX_OBJECTS。
• 重新构造代码，以减少调用insert()、remove()和getAll()的次数。
• 拆分后，如果无法将实体插入到任何子实体中，则将其放入不同的数据结构中。