Open In App

Octree | Insertion and Searching

Last Updated : 02 Feb, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Octree is a tree data structure in which each internal node can have at most 8 children. Like Binary tree which divides the space into two segments, Octree divides the space into at most eight-part which is called as octanes. It is used to store the 3-D point which takes a large amount of space. If all the internal node of the Octree contains exactly 8 children, then it is called full Octree. It is also useful for high-resolution graphics like 3D computer graphics.

The Octree can be formed from 3D volume by doing the following steps: 
 

  1. Divide the current 3D volume into eight boxes
  2. If any box has more than one point then divide it further into boxes
  3. Do not divide the box which has one or zero points in it
  4. Do this process repeatedly until all the box contains one or zero point in it


The above steps are shown in figure. 
 

Imagination of above algorithm


If S is the number of points in each dimension then the number of nodes that are formed in Octree is given by this formula (S^{3} -1)/7 . 
 

Insertion in Octree:


 

  • To insert a node in Octree, first of all, we check if a node exists or not if a node exists then return otherwise we go recursively
  • First, we start with the root node and mark it as current
  • Then we find the child node in which we can store the point
  • If the node is empty then it is replaced with the node we want to insert and make it a leaf node
  • If the node is the leaf node then make it an internal node and if it is an internal node then go to the child node, This process is performed recursively until an empty node is not found
  • The time complexity of this function is O(log(N)) where, N is the number of nodes


 

Search in Octree:


 

  • This function is used to search the point exist is the tree or not
  • Start with the root node and search recursively if the node with given point found then return true, if an empty node or boundary point or empty point is encountered then return false
  • If an internal node is found go that node. The time complexity of this function is also O(Log N) where, N is the number of nodes


Below is the implementation of the above approach
 

CPP14

// Implementation of Octree in c++
#include <iostream>
#include <vector>
using namespace std;
 
#define TopLeftFront 0
#define TopRightFront 1
#define BottomRightFront 2
#define BottomLeftFront 3
#define TopLeftBottom 4
#define TopRightBottom 5
#define BottomRightBack 6
#define BottomLeftBack 7
 
// Structure of a point
struct 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)
    {
    }
};
 
// Octree class
class Octree {
 
    // if point == NULL, node is internal node.
    // if point == (-1, -1, -1), node is empty.
    Point* point;
 
    // Represent the boundary of the cube
    Point *topLeftFront, *bottomRightBack;
    vector<Octree*> children;
 
public:
    // Constructor
    Octree()
    {
        // To declare empty node
        point = new Point();
    }
 
    // Constructor with three arguments
    Octree(int x, int y, int z)
    {
        // To declare point node
        point = new Point(x, y, z);
    }
 
    // Constructor with six arguments
    Octree(int x1, int y1, int z1, int x2, int y2, int z2)
    {
        // This use to construct Octree
        // with boundaries defined
        if (x2 < x1
            || y2 < y1
            || z2 < z1) {
            cout << "boundary points are not valid" << endl;
            return;
        }
 
        point = nullptr;
        topLeftFront
            = new Point(x1, y1, z1);
        bottomRightBack
            = new Point(x2, y2, z2);
 
        // Assigning null to the children
        children.assign(8, nullptr);
        for (int i = TopLeftFront;
             i <= BottomLeftBack;
             ++i)
            children[i] = new Octree();
    }
 
    // Function to insert a point in the octree
    void insert(int x,
                int y,
                int z)
    {
 
        // If the point already exists in the octree
        if (find(x, y, z)) {
            cout << "Point already exist in the tree" << endl;
            return;
        }
 
        // If the point is out of bounds
        if (x < topLeftFront->x
            || x > bottomRightBack->x
            || y < topLeftFront->y
            || y > bottomRightBack->y
            || z < topLeftFront->z
            || z > bottomRightBack->z) {
            cout << "Point is out of bound" << endl;
            return;
        }
 
        // Binary search to insert the point
        int midx = (topLeftFront->x
                    + bottomRightBack->x)
                   / 2;
        int midy = (topLeftFront->y
                    + bottomRightBack->y)
                   / 2;
        int midz = (topLeftFront->z
                    + bottomRightBack->z)
                   / 2;
 
        int pos = -1;
 
        // Checking the octant of
        // the point
        if (x <= midx) {
            if (y <= midy) {
                if (z <= midz)
                    pos = TopLeftFront;
                else
                    pos = TopLeftBottom;
            }
            else {
                if (z <= midz)
                    pos = BottomLeftFront;
                else
                    pos = BottomLeftBack;
            }
        }
        else {
            if (y <= midy) {
                if (z <= midz)
                    pos = TopRightFront;
                else
                    pos = TopRightBottom;
            }
            else {
                if (z <= midz)
                    pos = BottomRightFront;
                else
                    pos = BottomRightBack;
            }
        }
 
        // If an internal node is encountered
        if (children[pos]->point == nullptr) {
            children[pos]->insert(x, y, z);
            return;
        }
 
        // If an empty node is encountered
        else if (children[pos]->point->x == -1) {
            delete 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 == TopLeftFront) {
                children[pos] = new Octree(topLeftFront->x,
                                           topLeftFront->y,
                                           topLeftFront->z,
                                           midx,
                                           midy,
                                           midz);
            }
 
            else if (pos == TopRightFront) {
                children[pos] = new Octree(midx + 1,
                                           topLeftFront->y,
                                           topLeftFront->z,
                                           bottomRightBack->x,
                                           midy,
                                           midz);
            }
            else if (pos == BottomRightFront) {
                children[pos] = new Octree(midx + 1,
                                           midy + 1,
                                           topLeftFront->z,
                                           bottomRightBack->x,
                                           bottomRightBack->y,
                                           midz);
            }
            else if (pos == BottomLeftFront) {
                children[pos] = new Octree(topLeftFront->x,
                                           midy + 1,
                                           topLeftFront->z,
                                           midx,
                                           bottomRightBack->y,
                                           midz);
            }
            else if (pos == TopLeftBottom) {
                children[pos] = new Octree(topLeftFront->x,
                                           topLeftFront->y,
                                           midz + 1,
                                           midx,
                                           midy,
                                           bottomRightBack->z);
            }
            else if (pos == TopRightBottom) {
                children[pos] = new Octree(midx + 1,
                                           topLeftFront->y,
                                           midz + 1,
                                           bottomRightBack->x,
                                           midy,
                                           bottomRightBack->z);
            }
            else if (pos == BottomRightBack) {
                children[pos] = new Octree(midx + 1,
                                           midy + 1,
                                           midz + 1,
                                           bottomRightBack->x,
                                           bottomRightBack->y,
                                           bottomRightBack->z);
            }
            else if (pos == BottomLeftBack) {
                children[pos] = new Octree(topLeftFront->x,
                                           midy + 1,
                                           midz + 1,
                                           midx,
                                           bottomRightBack->y,
                                           bottomRightBack->z);
            }
            children[pos]->insert(x_, y_, z_);
            children[pos]->insert(x, y, z);
        }
    }
 
    // Function that returns true if the point
    // (x, y, z) exists in the octree
    bool find(int x, int y, int z)
    {
        // If point is out of bound
        if (x < topLeftFront->x
            || x > bottomRightBack->x
            || y < topLeftFront->y
            || y > bottomRightBack->y
            || z < topLeftFront->z
            || z > bottomRightBack->z)
            return 0;
 
        // Otherwise perform binary search
        // for each ordinate
        int midx = (topLeftFront->x
                    + bottomRightBack->x)
                   / 2;
        int midy = (topLeftFront->y
                    + bottomRightBack->y)
                   / 2;
        int midz = (topLeftFront->z
                    + bottomRightBack->z)
                   / 2;
 
        int pos = -1;
 
        // Deciding the position
        // where to move
        if (x <= midx) {
            if (y <= midy) {
                if (z <= midz)
                    pos = TopLeftFront;
                else
                    pos = TopLeftBottom;
            }
            else {
                if (z <= midz)
                    pos = BottomLeftFront;
                else
                    pos = BottomLeftBack;
            }
        }
        else {
            if (y <= midy) {
                if (z <= midz)
                    pos = TopRightFront;
                else
                    pos = TopRightBottom;
            }
            else {
                if (z <= midz)
                    pos = BottomRightFront;
                else
                    pos = BottomRightBack;
            }
        }
 
        // If an internal node is encountered
        if (children[pos]->point == nullptr) {
            return children[pos]->find(x, y, z);
        }
 
        // If an empty node is encountered
        else if (children[pos]->point->x == -1) {
            return 0;
        }
        else {
 
            // If node is found with
            // the given value
            if (x == children[pos]->point->x
                && y == children[pos]->point->y
                && z == children[pos]->point->z)
                return 1;
        }
        return 0;
    }
};
 
// Driver code
int main()
{
    Octree tree(1, 1, 1, 5, 5, 5);
 
    tree.insert(1, 2, 3);
    tree.insert(1, 2, 3);
    tree.insert(6, 5, 5);
 
    cout << (tree.find(1, 2, 3)
                 ? "Found\n"
                 : "Not Found\n");
 
    cout << (tree.find(3, 4, 4)
                 ? "Found\n"
                 : "Not Found\n");
    tree.insert(3, 4, 4);
 
    cout << (tree.find(3, 4, 4)
                 ? "Found\n"
                 : "Not Found\n");
 
    return 0;
}

                    

                    

                        
                        
 
                    

                

                



Output: 
Point already exist in the tree
Point is out of bound
found
not found
found

 
Applications:
  1. It is used in 3D computer graphics games
  2. It is also used to find nearest neighboring objects in 3D space
  3. It is also used for color quantization




                                    


                                                                        

                                        

                                            

                                                

                                                    
P

        

            
        

        

                                                

                                                

                                                    ParthManiyar                                                

                                            

                                            

            
                                        

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                            
 
                                

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Insertion in a B+ tree
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Insertion, Searching and Deletion in AVL trees containing a parent node pointer

                
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. The insertion and deletion in AVL trees have been discussed in the previous article. In this article, insert, search, and delete operations are discussed on AVL trees that also have a parent po

            

            
            

                
                15+ min read
            

        
    
        
            

                
Difference between Searching and Sorting Algorithms

                
Prerequisite: Searching and Sorting Algorithms Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is used. Based on the type of operations these algorithms are generally classified into two categories: Sequential Search: The Sequential Search is the basic and simple Searching Algorithm.

            

            
            

                
                4 min read
            

        
    
        
            

                
Searching For Characters and Substring in a String in Java

                
Strings are a very important aspect from a programming perspective as many questions can be framed out among strings. There arise wide varied sets of concepts and questions that are pivotal to understanding strings. Now over here will be discussing different ways to play with strings where we will be playing with characters with strings and substri

            

            
            

                
                6 min read
            

        
    
        
            

                
Skip List | Set 3 (Searching and Deletion)

                
In previous article Skip List | Set 2 (Insertion) we discussed the structure of skip nodes and how to insert an element in the skip list. In this article we will discuss how to search and delete an element from skip list. Searching an element in Skip list Searching an element is very similar to approach for searching a spot for inserting an element

            

            
            

                
                15+ min read
            

        
    
        
            

                
Insertion sort to sort even and odd positioned elements in different orders

                
We are given an array. We need to sort the even positioned elements in the ascending order and the odd positioned elements in the descending order. We must apply insertion sort to sort them.Examples: Input : a[] = {7, 10, 11, 3, 6, 9, 2, 13, 0} Output : 11 3 7 9 6 10 2 13 0 Even positioned elements after sorting int ascending order : 3 9 10 13 Odd

            

            
            

                
                7 min read
            

        
    
        
            

                
Fibonacci Heap - Insertion and Union

                
Fibonacci Heap is a collection of trees with min-heap or max-heap property. In Fibonacci Heap, trees can have any shape even all trees can be single nodes (This is unlike Binomial Heap where every tree has to be a Binomial Tree). In this article, we will discuss Insertion and Union operation on Fibonacci Heap. Prerequisites: Fibonacci Heap (Introdu

            

            
            

                
                7 min read
            

        
    
        
            

                
Proto Van Emde Boas Tree | Set 3 | Insertion and isMember Query

                
Please see previous articles on Proto Van Emde Boas Tree to understand these properly. Procedure for Insert: Base Case: If the size of Proto-VEB is 2 then assign true to the bit array( Here we in code we assign Proto-VEB(1) due to recursive structure and so now it is not nullptr and it act as true ) at the position of key.Until we reach at the base

            

            
            

                
                9 min read
            

        
    
        
            

                
Insertion in n-ary tree in given order and Level order traversal

                
Given a set of parent nodes where the index of the array is the child of each Node value, the task is to insert the nodes as a forest(multiple trees combined together) where each parent could have more than two children. After inserting the nodes, print each level in a sorted format. Example: Input: arr[] = {5, 3, -1, 2, 5, 3} Output:-1 231 5Input:

            

            
            

                
                10 min read
            

        
    
        
            

                
Van Emde Boas Tree | Set 2 | Insertion, Find, Minimum and Maximum Queries

                
It is highly recommended to see previous articles on Van Emde Boas Tree first. Procedure for Insert : If no keys are present in the tree then simply assign minimum and maximum of the tree to the key.Otherwise we will go deeper in the tree and do the following:If the key we want to insert is less than the current minimum of the tree, then we swap bo

            

            
            

                
                15+ min read
            

        
    
        
            

                
m-Way Search Tree | Set-2 | Insertion and Deletion

                
Insertion in an m-Way search tree: The insertion in an m-Way search tree is similar to binary trees but there should be no more than m-1 elements in a node. If the node is full then a child node will be created to insert the further elements. Let us see the example given below to insert an element in an m-Way search tree.Example: To insert a new el

            

            
            

                
                15+ min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
three90RightbarBannerImg

	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox