15,396,537 members
Articles / Programming Languages / C#
Article
Posted 3 Aug 2008

80.8K views
44 bookmarked

# Octree Search

Rate me:
An Octree Search Algorithm in C#

## 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:

C#
`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:

C#
```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:

C#
`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:

C#
```/// <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(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);

To remove a node:

C#
`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.

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

There are several methods to find a node:

C#
```// 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(double x, double y, double z, double radius);

// 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.

## Share

 Engineer United States
No Biography provided

 First Prev Next
 2D quadtree codes gdindrawan22-Dec-11 12:58 gdindrawan 22-Dec-11 12:58
 Re: I think your code has some significant bugs Kam17-Oct-08 20:04 Kam 17-Oct-08 20:04
 Re: I think your code has some significant bugs scosta_FST20-Oct-08 3:57 scosta_FST 20-Oct-08 3:57
 Any chance to have the fixed code? Maybe with Generics?
 Re: I think your code has some significant bugs Kam23-Oct-08 7:51 Kam 23-Oct-08 7:51
 Re: I think your code has some significant bugs scosta_FST23-Oct-08 20:09 scosta_FST 23-Oct-08 20:09
 Re: I think your code has some significant bugs [modified] gdindrawan23-Dec-11 13:04 gdindrawan 23-Dec-11 13:04
 whoops :D Emil - Gabriel28-Aug-08 2:25 Emil - Gabriel 28-Aug-08 2:25
 Re: whoops :D rcollina28-Aug-08 2:59 rcollina 28-Aug-08 2:59
 Re: whoops :D Emil - Gabriel28-Aug-08 3:34 Emil - Gabriel 28-Aug-08 3:34
 Re: whoops :D Kam28-Aug-08 11:09 Kam 28-Aug-08 11:09
 Re: whoops :D Emil - Gabriel29-Aug-08 5:19 Emil - Gabriel 29-Aug-08 5:19
 Good article! scosta_FST6-Aug-08 0:25 scosta_FST 6-Aug-08 0:25
 Re: Good article! Kam6-Aug-08 8:59 Kam 6-Aug-08 8:59
 Re: Good article! scosta_FST6-Aug-08 21:45 scosta_FST 6-Aug-08 21:45
 Last Visit: 31-Dec-99 18:00     Last Update: 16-Aug-22 0:53 Refresh 1