## Introduction

A data structure is an approach of storing data in a computer in a way that it can be accessed efficiently. A clever data structure allows a variety of vital operations to be achieved, using as few resources, both execution time and memory space, as possible. A tree is a widely-used data structure that emulates a tree structure with a set of linked nodes. An `Octree `

is a tree data structure in which each inner node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees.

Octree data structures are useful in many scenarios. Imagine you have a huge data set of `string`

s, and you need to find a `string`

. You have no idea where it is located in that data set, then an `Octree `

search (or quadtree in 2D) is probably the most efficient and fastest method to find your requested `string`

. In my specific project, I have a huge number of fluid elements (in 3D and each element is represented by another data structure), usually in the order of a few million, and I need to find out which element is hosting a solid particle (a 3D point in space). Obviously, searching each element one by one would take forever, and binary searches require sorting of the data set which is not efficient as well. In this case, an `Octree `

search works great.

The code posted here is a conversion/upgrade of couple 2D quadtree codes taken from open source packages but has extended to 3D and added many new tools such as searching in rings and squares. In this article, I give a quick instruction on the code usage. Hope this code comes in handy for you.

## Using the Code

The demo project attached shows how to use the `octree `

module. The first step is to instantiate the `Octree `

class:

`Octree octreeDataset = new Octree(); `

There are several constructors that you can use. I highly recommend to specify the **initial** range of your dataset (min, max, maximum number of nodes) which are usually known. This will speed up the search process. To do so, call `Octree `

as follows:

Octree octreeDataset = Octree( float xMax, float xMin, float yMax, float yMin, float zMax, float zMin, int maxItems)

The next step is to fill this data set with a bunch of nodes. This is very easy as well, simply write:

octreeDataset.AddNode(x, y, z, obj);

This will add a node to the `octree `

data structure at location `x`

, `y`

, `z `

and the stored value at this point is object `obj`

. This module has 32 overloads, so use it accordingly. Here are the current overloads:

/// <summary> Add an object into the organizer at a location.</summary> /// <param name="x">up-down location x</param> /// <param name="y">left-right location y</param> /// <param name="z">front-back location z</param> /// <returns> true if the insertion worked. </returns> bool AddNode(float x, float y, float z, object obj); bool AddNode(float x, float y, float z, int obj); bool AddNode(float x, float y, float z, uint obj); bool AddNode(float x, float y, float z, short obj); bool AddNode(float x, float y, float z, long obj); bool AddNode(float x, float y, float z, float obj); bool AddNode(float x, float y, float z, double obj); bool AddNode(float x, float y, float z, bool obj); bool AddNode(Vector3f vector, object obj); bool AddNode(Vector3f vector, int obj); bool AddNode(Vector3f vector, uint obj); bool AddNode(Vector3f vector, short obj); bool AddNode(Vector3f vector, long obj); bool AddNode(Vector3f vector, float obj); bool AddNode(Vector3f vector, double obj); bool AddNode(Vector3f vector, bool obj); bool AddNode(double x, double y, double z, object obj); bool AddNode(double x, double y, double z, int obj); bool AddNode(double x, double y, double z, uint obj); bool AddNode(double x, double y, double z, short obj); bool AddNode(double x, double y, double z, long obj); bool AddNode(double x, double y, double z, float obj); bool AddNode(double x, double y, double z, double obj); bool AddNode(double x, double y, double z, bool obj); bool AddNode(Vector3d vector, object obj); bool AddNode(Vector3d vector, int obj); bool AddNode(Vector3d vector, uint obj); bool AddNode(Vector3d vector, short obj); bool AddNode(Vector3d vector, long obj); bool AddNode(Vector3d vector, float obj); bool AddNode(Vector3d vector, double obj); bool AddNode(Vector3d vector, bool obj);

To remove a node:

octreeDataset.RemoveNode(x, y, z, obj);

This method has several overloads as well.

Now the data set is ready, let's see how to search for an item. This step is easy too, simply try `GetNode `

or `GetNodes `

methods. The following command looks up for the object located at `x`

, `y`

, `z `

location.

`(object)octreeDataset.GetNode(x, y, z); `

There are several methods to find a node:

// Find an object closest to point x/y/z. object GetNode(float x, float y, float z); object GetNode(Vector3f vector); object GetNode(double x, double y, double z); object GetNode(Vector3d vector); //Find an object closest to point x/y/z within a distance. object GetNode(float x, float y, float z, double withinDistance); object GetNode(Vector3f vector, double withinDistance); object GetNode(double x, double y, double z, double withinDistance); object GetNode(Vector3d vector, double withinDistance); // Find a set of objects closest to point x/y/z within a given radius. ArrayList GetNodes(float x, float y, float z, double radius); ArrayList GetNodes(Vector3f vector, double radius); ArrayList GetNodes(double x, double y, double z, double radius); ArrayList GetNodes(Vector3d vector, double radius); ArrayList GetNodes(float x, float y, float z, double MinRadius, double MaxRadius); ArrayList GetNodes(Vector3f vector, double MinRadius, double MaxRadius); ArrayList GetNodes(double x, double y, double z, double MinRadius, double MaxRadius); ArrayList GetNodes(Vector3d vector, double MinRadius, double MaxRadius); // Find an object closest to point x/y/z, within a cube. ArrayList GetNode (float xMax, float xMin, float yMax, float yMin, float zMax, float zMin);

And that's it! Please let me know if you have new ideas to improve the code.

## Points of Interest

To get more information on `Octree `

search algorithm, check out the following pages:

## History

This is release 1.0.

Please let me know if you find bugs or have suggestions to improve the code.