用C# 写一个八叉树算法
时间: 2024-05-04 07:20:29 浏览: 14
下面是一个简单的C#八叉树算法的示例代码:
```csharp
using System.Collections.Generic;
public class Octree {
private const int MAX_DEPTH = 10;
private readonly int depth;
private readonly float size;
private readonly Vector3 center;
private Octree[] children;
private List<Vector3> points;
public Octree(Vector3 center, float size, int depth = 0) {
this.center = center;
this.size = size;
this.depth = depth;
this.children = null;
this.points = new List<Vector3>();
}
public void Insert(Vector3 point) {
if (depth == MAX_DEPTH) {
points.Add(point);
return;
}
if (children == null) {
Split();
}
int index = GetChildIndex(point);
children[index].Insert(point);
}
public List<Vector3> GetPointsInRadius(Vector3 center, float radius) {
List<Vector3> result = new List<Vector3>();
if (Vector3.Distance(center, this.center) <= radius + size / 2) {
foreach (Vector3 point in points) {
if (Vector3.Distance(center, point) <= radius) {
result.Add(point);
}
}
if (children != null) {
for (int i = 0; i < 8; i++) {
result.AddRange(children[i].GetPointsInRadius(center, radius));
}
}
}
return result;
}
private void Split() {
children = new Octree[8];
float childSize = size / 2;
int childDepth = depth + 1;
Vector3 childCenter;
for (int i = 0; i < 8; i++) {
childCenter = center + new Vector3(
((i & 1) == 1) ? childSize / 2 : -childSize / 2,
((i & 2) == 2) ? childSize / 2 : -childSize / 2,
((i & 4) == 4) ? childSize / 2 : -childSize / 2
);
children[i] = new Octree(childCenter, childSize, childDepth);
}
}
private int GetChildIndex(Vector3 point) {
int index = 0;
if (point.x >= center.x) index |= 1;
if (point.y >= center.y) index |= 2;
if (point.z >= center.z) index |= 4;
return index;
}
}
```
这是一个基本的八叉树实现,它可以插入和查找点,并且可以查找给定半径内的所有点。请注意,该示例中的向量使用Unity的Vector3类,如果你在其他环境中使用此代码,则需要更改向量类。