原文链接：Octree data structure
#include <string>
#include <iostream>/** Code for an octree that demonstrates insertion and search*/
#include <iostream>
#include <vector>#define TLF 0 // top left front
#define TRF 1 // top right front
#define BRF 2 // bottom right front
#define BLF 3 // bottom left front
#define TLB 4 // top left back
#define TRB 5 // top right back
#define BRB 6 // bottom right back
#define BLB 7 // bottom left backstruct Point {
int x;int y;int z;Point() : x(-1), y(-1), z(-1) {
}Point(int a, int b, int c) : x(a), y(b), z(c) {
}
};class Octree {
// if point == NULL, node is regional.// if point == (-1, -1, -1), node is empty.Point *point;Point *top_left_front, *bottom_right_back; // represents the space.std::vector<Octree *> children;public:Octree() {
// to declare empty nodepoint = new Point();}Octree(int x, int y, int z) {
// to declare point nodepoint = new Point(x, y, z);}Octree(int x1, int y1, int z1, int x2, int y2, int z2) {
if(x2 < x1 || y2 < y1 || z2 < z1)return;point = nullptr;top_left_front = new Point(x1, y1, z1);bottom_right_back = new Point(x2, y2, z2);children.assign(8, nullptr);for(int i = TLF; i <= BLB; ++i)children[i] = new Octree();}void insert(int x, int y, int z) {
if(x < top_left_front->x || x > bottom_right_back->x|| y < top_left_front->y || y > bottom_right_back->y|| z < top_left_front->z || z > bottom_right_back->z)return;int midx = (top_left_front->x + bottom_right_back->x) >> 1,midy = (top_left_front->y + bottom_right_back->y) >> 1,midz = (top_left_front->z + bottom_right_back->z) >> 1;int pos = -1;if(x <= midx) {
if(y <= midy) {
if(z <= midz)pos = TLF;elsepos = TLB;} else {
if(z <= midz)pos = BLF;elsepos = BLB;}} else {
if(y <= midy) {
if(z <= midz)pos = TRF;elsepos = TRB;} else {
if(z <= midz)pos = BRF;elsepos = BRB;}}if(children[pos]->point == nullptr) {
// if region nodechildren[pos]->insert(x, y, z);return;} else if(children[pos]->point->x == -1) {
// if empty nodedelete children[pos];children[pos] = new Octree(x, y, z);return;} else {
int x_ = children[pos]->point->x,y_ = children[pos]->point->y,z_ = children[pos]->point->z;delete children[pos];children[pos] = nullptr;if(pos == TLF) {
children[pos] = new Octree(top_left_front->x, top_left_front->y, top_left_front->z,midx, midy, midz);} else if(pos == TRF) {
children[pos] = new Octree(midx + 1, top_left_front->y, top_left_front->z,bottom_right_back->x, midy, midz);} else if(pos == BRF) {
children[pos] = new Octree(midx + 1, midy + 1, top_left_front->z,bottom_right_back->x, bottom_right_back->y, midz);} else if(pos == BLF) {
children[pos] = new Octree(top_left_front->x, midy + 1, top_left_front->z,midx, bottom_right_back->y, midz);} else if(pos == TLB) {
children[pos] = new Octree(top_left_front->x, top_left_front->y, midz + 1,midx, midy, bottom_right_back->z);} else if(pos == TRB) {
children[pos] = new Octree(midx + 1, top_left_front->y, midz + 1,bottom_right_back->x, midy, bottom_right_back->z);} else if(pos == BRB) {
children[pos] = new Octree(midx + 1, midy + 1, midz + 1,bottom_right_back->x, bottom_right_back->y, bottom_right_back->z);} else if(pos == BLB) {
children[pos] = new Octree(top_left_front->x, midy + 1, midz + 1,midx, bottom_right_back->y, bottom_right_back->z);}children[pos]->insert(x_, y_, z_);children[pos]->insert(x, y, z);}}bool find(int x, int y, int z) {
if(x < top_left_front->x || x > bottom_right_back->x|| y < top_left_front->y || y > bottom_right_back->y|| z < top_left_front->z || z > bottom_right_back->z)return 0;int midx = (top_left_front->x + bottom_right_back->x) >> 1,midy = (top_left_front->y + bottom_right_back->y) >> 1,midz = (top_left_front->z + bottom_right_back->z) >> 1;int pos = -1;if(x <= midx) {
if(y <= midy) {
if(z <= midz)pos = TLF;elsepos = TLB;} else {
if(z <= midz)pos = BLF;elsepos = BLB;}} else {
if(y <= midy) {
if(z <= midz)pos = TRF;elsepos = TRB;} else {
if(z <= midz)pos = BRF;elsepos = BRB;}}if(children[pos]->point == nullptr) {
// if region nodereturn children[pos]->find(x, y, z);} else if(children[pos]->point->x == -1) {
// if empty nodereturn 0;} else {
if(x == children[pos]->point->x && y == children[pos]->point->y&& z == children[pos]->point->z)return 1;}return 0;}
};int main() {
Octree tree(1, 1, 1, 4, 4, 4);std::cout << "Insert (3, 3, 3)\n";tree.insert(3, 3, 3);std::cout << "Insert (3, 3, 4)\n";tree.insert(3, 3, 4);std::cout << "Find (3, 3, 3):\n";std::cout << (tree.find(3, 3, 3) ? "True\n" : "False\n");std::cout << "Find (3, 4, 4):\n";std::cout << (tree.find(3, 4, 4) ? "True\n" : "False\n");std::cout << "Insert (3, 4, 4)\n";tree.insert(3, 4, 4);std::cout << "Find (3, 4, 4):\n";std::cout << (tree.find(3, 4, 4) ? "True\n" : "False\n");return 0;
}
补充：2019年11月8日
今天在 Github 上又发现一个写的比较好的八叉树，链接：brandonpelfrey/SimpleOctree
核心代码：
#ifndef Octree_H
#define Octree_H#include <cstddef>
#include <vector>
#include "OctreePoint.h"namespace brandonpelfrey {
/**!**/class Octree {
// Physical position/size. This implicitly defines the bounding// box of this nodeVec3 origin; //! The physical center of this nodeVec3 halfDimension; //! Half the width/height/depth of this node// The tree has up to eight children and can additionally store// a point, though in many applications only, the leaves will store data.Octree *children[8]; //! Pointers to child octantsOctreePoint *data; //! Data point to be stored at a node/*Children follow a predictable pattern to make accesses simple.Here, - means less than 'origin' in that dimension, + means greater than.child: 0 1 2 3 4 5 6 7x: - - - - + + + +y: - - + + - - + +z: - + - + - + - +*/public:Octree(const Vec3 &origin, const Vec3 &halfDimension): origin(origin), halfDimension(halfDimension), data(NULL) {
// Initially, there are no childrenfor(int i = 0; i < 8; ++i)children[i] = NULL;}Octree(const Octree ©): origin(copy.origin), halfDimension(copy.halfDimension), data(copy.data) {
}~Octree() {
// Recursively destroy octantsfor(int i = 0; i < 8; ++i)delete children[i];}// Determine which octant of the tree would contain 'point'int getOctantContainingPoint(const Vec3 &point) const {
int oct = 0;if(point.x >= origin.x) oct |= 4;if(point.y >= origin.y) oct |= 2;if(point.z >= origin.z) oct |= 1;return oct;}bool isLeafNode() const {
// This is correct, but overkill. See below./*for(int i=0; i<8; ++i)if(children[i] != NULL)return false;return true;*/// We are a leaf iff we have no children. Since we either have none, or// all eight, it is sufficient to just check the first.return children[0] == NULL;}void insert(OctreePoint *point) {
// If this node doesn't have a data point yet assigned// and it is a leaf, then we're done!if(isLeafNode()) {
if(data == NULL) {
data = point;return;} else {
// We're at a leaf, but there's already something here// We will split this node so that it has 8 child octants// and then insert the old data that was here, along with// this new data point// Save this data point that was here for a later re-insertOctreePoint *oldPoint = data;data = NULL;// Split the current node and create new empty trees for each// child octant.for(int i = 0; i < 8; ++i) {
// Compute new bounding box for this childVec3 newOrigin = origin;newOrigin.x += halfDimension.x * (i & 4 ? .5f : -.5f);newOrigin.y += halfDimension.y * (i & 2 ? .5f : -.5f);newOrigin.z += halfDimension.z * (i & 1 ? .5f : -.5f);children[i] = new Octree(newOrigin, halfDimension * .5f);}// Re-insert the old point, and insert this new point// (We wouldn't need to insert from the root, because we already// know it's guaranteed to be in this section of the tree)children[getOctantContainingPoint(oldPoint->getPosition())]->insert(oldPoint);children[getOctantContainingPoint(point->getPosition())]->insert(point);}} else {
// We are at an interior node. Insert recursively into the// appropriate child octantint octant = getOctantContainingPoint(point->getPosition());children[octant]->insert(point);}}// This is a really simple routine for querying the tree for points// within a bounding box defined by min/max points (bmin, bmax)// All results are pushed into 'results'void getPointsInsideBox(const Vec3 &bmin, const Vec3 &bmax, std::vector<OctreePoint *> &results) {
// If we're at a leaf node, just see if the current data point is inside// the query bounding boxif(isLeafNode()) {
if(data != NULL) {
const Vec3 &p = data->getPosition();if(p.x > bmax.x || p.y > bmax.y || p.z > bmax.z) return;if(p.x < bmin.x || p.y < bmin.y || p.z < bmin.z) return;results.push_back(data);}} else {
// We're at an interior node of the tree. We will check to see if// the query bounding box lies outside the octants of this node.for(int i = 0; i < 8; ++i) {
// Compute the min/max corners of this child octantVec3 cmax = children[i]->origin + children[i]->halfDimension;Vec3 cmin = children[i]->origin - children[i]->halfDimension;// If the query rectangle is outside the child's bounding box,// then continueif(cmax.x < bmin.x || cmax.y < bmin.y || cmax.z < bmin.z) continue;if(cmin.x > bmax.x || cmin.y > bmax.y || cmin.z > bmax.z) continue;// At this point, we've determined that this child is intersecting// the query bounding boxchildren[i]->getPointsInsideBox(bmin, bmax, results);}}}};}
#endif