AABB.h

/*
  Copyright (c) 2009 Erin Catto http://www.box2d.org
  Copyright (c) 2016-2017 Lester Hedges <lester.hedges+aabbcc@gmail.com>

  This software is provided 'as-is', without any express or implied
  warranty. In no event will the authors be held liable for any damages
  arising from the use of this software.

  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:

  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.

  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.

  3. This notice may not be removed or altered from any source distribution.

  This code was adapted from parts of the Box2D Physics Engine,
  http://www.box2d.org
*/

#ifndef _AABB_H
#define _AABB_H

#include <algorithm>
#include <cassert>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <map>
#include <vector>

const unsigned int NULL_NODE = 0xffffffff;

namespace aabb
{
    class AABB
    {
    public:
        AABB();


        AABB(unsigned int);


        AABB(const std::vector<double>&, const std::vector<double>&);

        double computeSurfaceArea() const;

        double getSurfaceArea() const;


        void merge(const AABB&, const AABB&);


        bool contains(const AABB&) const;


        bool overlaps(const AABB&) const;


        std::vector<double> computeCentre();


        void setDimension(unsigned int);

        std::vector<double> lowerBound;

        std::vector<double> upperBound;

        std::vector<double> centre;

        double surfaceArea;
    };

    struct Node
    {
        Node();

        AABB aabb;

        unsigned int parent;

        unsigned int next;

        unsigned int left;

        unsigned int right;

        int height;

        unsigned int particle;


        bool isLeaf() const;
    };

    class Tree
    {
    public:

        Tree(unsigned int dimension_= 3, double skinThickness_ = 0.05, unsigned int nParticles = 16);


        Tree(unsigned int, double, const std::vector<bool>&, const std::vector<double>&, unsigned int nParticles = 16);


        void setPeriodicity(const std::vector<bool>&);


        void setBoxSize(const std::vector<double>&);


        void insertParticle(unsigned int, std::vector<double>&, double);


        void insertParticle(unsigned int, std::vector<double>&, std::vector<double>&);


        void removeParticle(unsigned int);


        bool updateParticle(unsigned int, std::vector<double>&, double);


        bool updateParticle(unsigned int, std::vector<double>&, std::vector<double>&);


        std::vector<unsigned int> query(unsigned int);


        std::vector<unsigned int> query(unsigned int, const AABB&);


        std::vector<unsigned int> query(const AABB&);


        const AABB& getAABB(unsigned int);


        unsigned int getHeight() const;


        unsigned int getNodeCount() const;


        unsigned int computeMaximumBalance() const;


        double computeSurfaceAreaRatio() const;

        void validate() const;

        void rebuild();

    private:
        unsigned int root;

        std::vector<Node> nodes;

        unsigned int nodeCount;

        unsigned int nodeCapacity;

        unsigned int freeList;

        unsigned int dimension;

        bool isPeriodic;

        double skinThickness;

        std::vector<bool> periodicity;

        std::vector<double> boxSize;

        std::vector<double> negMinImage;

        std::vector<double> posMinImage;

        std::map<unsigned int, unsigned int> particleMap;


        unsigned int allocateNode();


        void freeNode(unsigned int);


        void insertLeaf(unsigned int);


        void removeLeaf(unsigned int);


        unsigned int balance(unsigned int);


        unsigned int computeHeight() const;


        unsigned int computeHeight(unsigned int) const;


        void validateStructure(unsigned int) const;


        void validateMetrics(unsigned int) const;

        /* \param position
                The position vector.
         */
        void periodicBoundaries(std::vector<double>&);


        bool minimumImage(std::vector<double>&, std::vector<double>&);
    };
}

#endif /* _AABB_H */