65.9K
CodeProject 正在变化。 阅读更多。
Home

八叉树搜索

Kam
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.55/5 (13投票s)

2008年8月3日

CPOL

3分钟阅读

viewsIcon

86070

downloadIcon

1463

C# 中的八叉树搜索算法。

引言

数据结构是一种在计算机中存储数据的方法，以便可以有效地访问数据。 一个巧妙的数据结构允许使用尽可能少的资源（包括执行时间和内存空间）来实现各种重要操作。 树是一种广泛使用的数据结构，它模拟具有一组链接节点的树结构。 八叉树是一种树数据结构，其中每个内部节点最多有八个子节点。 八叉树最常用于通过将三维空间递归地细分为八个八分体来对其进行划分。 八叉树是四叉树的三维类似物。

八叉树数据结构在许多情况下都很有用。 想象一下，您有一个巨大的string数据集，并且需要找到一个string。 您不知道它位于该数据集中的哪个位置，那么八叉树搜索（或2D中的四叉树）可能是找到您请求的string的最有效和最快的方法。 在我的特定项目中，我有大量的流体元素（在3D中，每个元素由另一个数据结构表示），通常约为数百万个，我需要找出哪个元素托管着固体颗粒（空间中的3D点）。 显然，一个接一个地搜索每个元素将花费很长时间，并且二分搜索也需要对数据集进行排序，效率不高。 在这种情况下，八叉树搜索效果很好。

此处发布的代码是来自开源软件包的几个2D四叉树代码的转换/升级，但已扩展到3D并添加了许多新工具，例如环形和方形搜索。 在本文中，我将简要介绍代码的用法。 希望此代码对您有所帮助。

Using the Code

随附的演示项目显示了如何使用octree模块。 第一步是实例化Octree类

Octree octreeDataset = new Octree();

您可以使用多个构造函数。 我强烈建议指定数据集的初始范围（最小，最大，最大节点数），这些通常是已知的。 这将加快搜索过程。 为此，请按以下方式调用Octree

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

下一步是用一堆节点填充此数据集。 这也很容易，只需编写

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

这会将一个节点添加到octree数据结构的x，y，z位置，并且此点存储的值是对象obj。 此模块具有32个重载，因此请相应使用。 这是当前的重载

/// <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);

要删除节点

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

此方法也有几个重载。

现在数据已准备就绪，让我们看看如何搜索项目。 此步骤也很容易，只需尝试GetNode或GetNodes方法即可。 以下命令查找位于x，y，z位置的对象。

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

有几种方法可以找到节点

// 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);

就这样！ 如果您有改进代码的新想法，请告诉我。

关注点

要获取有关Octree搜索算法的更多信息，请查看以下页面

历史

这是1.0版本。

如果您发现错误或有改进代码的建议，请告诉我。

© . All rights reserved.