niko
553 lines
16 KiB
C#
553 lines
16 KiB
C#
using System;
|
|
using System.Collections;
|
|
using System.Collections.Generic;
|
|
using System.IO;
|
|
using System.Linq;
|
|
using System.Runtime.Serialization.Formatters.Binary;
|
|
using System.Text;
|
|
|
|
namespace KdTree
|
|
{
|
|
// Token: 0x02000009 RID: 9
|
|
[Serializable]
|
|
public class KdTree<TKey, TValue> : IKdTree<TKey, TValue>, IEnumerable<KdTreeNode<TKey, TValue>>, IEnumerable
|
|
{
|
|
// Token: 0x06000024 RID: 36 RVA: 0x000021D5 File Offset: 0x000003D5
|
|
public KdTree(int dimensions, ITypeMath<TKey> typeMath)
|
|
{
|
|
this.dimensions = dimensions;
|
|
this.typeMath = typeMath;
|
|
this.Count = 0;
|
|
}
|
|
|
|
// Token: 0x06000025 RID: 37 RVA: 0x000021F2 File Offset: 0x000003F2
|
|
public KdTree(int dimensions, ITypeMath<TKey> typeMath, AddDuplicateBehavior addDuplicateBehavior)
|
|
: this(dimensions, typeMath)
|
|
{
|
|
this.AddDuplicateBehavior = addDuplicateBehavior;
|
|
}
|
|
|
|
// Token: 0x1700000A RID: 10
|
|
// (get) Token: 0x06000026 RID: 38 RVA: 0x00002203 File Offset: 0x00000403
|
|
// (set) Token: 0x06000027 RID: 39 RVA: 0x0000220B File Offset: 0x0000040B
|
|
public AddDuplicateBehavior AddDuplicateBehavior { get; private set; }
|
|
|
|
// Token: 0x06000028 RID: 40 RVA: 0x00002214 File Offset: 0x00000414
|
|
public bool Add(TKey[] point, TValue value)
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode = new KdTreeNode<TKey, TValue>(point, value);
|
|
if (this.root == null)
|
|
{
|
|
this.root = new KdTreeNode<TKey, TValue>(point, value);
|
|
}
|
|
else
|
|
{
|
|
int num = -1;
|
|
KdTreeNode<TKey, TValue> kdTreeNode2 = this.root;
|
|
int num2;
|
|
for (;;)
|
|
{
|
|
num = (num + 1) % this.dimensions;
|
|
if (this.typeMath.AreEqual(point, kdTreeNode2.Point))
|
|
{
|
|
switch (this.AddDuplicateBehavior)
|
|
{
|
|
case AddDuplicateBehavior.Skip:
|
|
return false;
|
|
case AddDuplicateBehavior.Error:
|
|
goto IL_6D;
|
|
case AddDuplicateBehavior.Update:
|
|
kdTreeNode2.Value = value;
|
|
goto IL_90;
|
|
case AddDuplicateBehavior.Collect:
|
|
goto IL_7C;
|
|
}
|
|
break;
|
|
}
|
|
IL_90:
|
|
num2 = this.typeMath.Compare(point[num], kdTreeNode2.Point[num]);
|
|
if (kdTreeNode2[num2] == null)
|
|
{
|
|
goto Block_4;
|
|
}
|
|
kdTreeNode2 = kdTreeNode2[num2];
|
|
}
|
|
throw new Exception("Unexpected AddDuplicateBehavior");
|
|
IL_6D:
|
|
throw new DuplicateNodeError();
|
|
IL_7C:
|
|
kdTreeNode2.AddDuplicate(value);
|
|
return false;
|
|
Block_4:
|
|
kdTreeNode2[num2] = kdTreeNode;
|
|
}
|
|
int count = this.Count;
|
|
this.Count = count + 1;
|
|
return true;
|
|
}
|
|
|
|
// Token: 0x06000029 RID: 41 RVA: 0x00002304 File Offset: 0x00000504
|
|
private void ReadChildNodes(KdTreeNode<TKey, TValue> removedNode)
|
|
{
|
|
if (removedNode.IsLeaf)
|
|
{
|
|
return;
|
|
}
|
|
Queue<KdTreeNode<TKey, TValue>> queue = new Queue<KdTreeNode<TKey, TValue>>();
|
|
Queue<KdTreeNode<TKey, TValue>> queue2 = new Queue<KdTreeNode<TKey, TValue>>();
|
|
if (removedNode.LeftChild != null)
|
|
{
|
|
queue2.Enqueue(removedNode.LeftChild);
|
|
}
|
|
if (removedNode.RightChild != null)
|
|
{
|
|
queue2.Enqueue(removedNode.RightChild);
|
|
}
|
|
while (queue2.Count > 0)
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode = queue2.Dequeue();
|
|
queue.Enqueue(kdTreeNode);
|
|
for (int i = -1; i <= 1; i += 2)
|
|
{
|
|
if (kdTreeNode[i] != null)
|
|
{
|
|
queue2.Enqueue(kdTreeNode[i]);
|
|
kdTreeNode[i] = null;
|
|
}
|
|
}
|
|
}
|
|
while (queue.Count > 0)
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode2 = queue.Dequeue();
|
|
int count = this.Count;
|
|
this.Count = count - 1;
|
|
this.Add(kdTreeNode2.Point, kdTreeNode2.Value);
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600002A RID: 42 RVA: 0x000023CC File Offset: 0x000005CC
|
|
public void RemoveAt(TKey[] point)
|
|
{
|
|
if (this.root == null)
|
|
{
|
|
return;
|
|
}
|
|
KdTreeNode<TKey, TValue> kdTreeNode;
|
|
if (this.typeMath.AreEqual(point, this.root.Point))
|
|
{
|
|
kdTreeNode = this.root;
|
|
this.root = null;
|
|
int num = this.Count;
|
|
this.Count = num - 1;
|
|
this.ReadChildNodes(kdTreeNode);
|
|
return;
|
|
}
|
|
kdTreeNode = this.root;
|
|
int num2 = -1;
|
|
for (;;)
|
|
{
|
|
num2 = (num2 + 1) % this.dimensions;
|
|
int num3 = this.typeMath.Compare(point[num2], kdTreeNode.Point[num2]);
|
|
if (kdTreeNode[num3] == null)
|
|
{
|
|
break;
|
|
}
|
|
if (this.typeMath.AreEqual(point, kdTreeNode[num3].Point))
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode2 = kdTreeNode[num3];
|
|
kdTreeNode[num3] = null;
|
|
int num = this.Count;
|
|
this.Count = num - 1;
|
|
this.ReadChildNodes(kdTreeNode2);
|
|
}
|
|
else
|
|
{
|
|
kdTreeNode = kdTreeNode[num3];
|
|
}
|
|
if (kdTreeNode == null)
|
|
{
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600002B RID: 43 RVA: 0x000024B4 File Offset: 0x000006B4
|
|
public KdTreeNode<TKey, TValue>[] GetNearestNeighbours(TKey[] point, int count)
|
|
{
|
|
if (count > this.Count)
|
|
{
|
|
count = this.Count;
|
|
}
|
|
if (count < 0)
|
|
{
|
|
throw new ArgumentException("Number of neighbors cannot be negative");
|
|
}
|
|
if (count == 0)
|
|
{
|
|
return new KdTreeNode<TKey, TValue>[0];
|
|
}
|
|
new KdTreeNode<TKey, TValue>[count];
|
|
NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey> nearestNeighbourList = new NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey>(count, this.typeMath);
|
|
HyperRect<TKey> hyperRect = HyperRect<TKey>.Infinite(this.dimensions, this.typeMath);
|
|
this.AddNearestNeighbours(this.root, point, hyperRect, 0, nearestNeighbourList, this.typeMath.MaxValue);
|
|
count = nearestNeighbourList.Count;
|
|
KdTreeNode<TKey, TValue>[] array = new KdTreeNode<TKey, TValue>[count];
|
|
for (int i = 0; i < count; i++)
|
|
{
|
|
array[count - i - 1] = nearestNeighbourList.RemoveFurtherest();
|
|
}
|
|
return array;
|
|
}
|
|
|
|
// Token: 0x0600002C RID: 44 RVA: 0x00002558 File Offset: 0x00000758
|
|
private void AddNearestNeighbours(KdTreeNode<TKey, TValue> node, TKey[] target, HyperRect<TKey> rect, int depth, NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey> nearestNeighbours, TKey maxSearchRadiusSquared)
|
|
{
|
|
if (node == null)
|
|
{
|
|
return;
|
|
}
|
|
int num = depth % this.dimensions;
|
|
HyperRect<TKey> hyperRect = rect.Clone();
|
|
hyperRect.MaxPoint[num] = node.Point[num];
|
|
HyperRect<TKey> hyperRect2 = rect.Clone();
|
|
hyperRect2.MinPoint[num] = node.Point[num];
|
|
int num2 = this.typeMath.Compare(target[num], node.Point[num]);
|
|
HyperRect<TKey> hyperRect3 = ((num2 <= 0) ? hyperRect : hyperRect2);
|
|
HyperRect<TKey> hyperRect4 = ((num2 <= 0) ? hyperRect2 : hyperRect);
|
|
KdTreeNode<TKey, TValue> kdTreeNode = ((num2 <= 0) ? node.LeftChild : node.RightChild);
|
|
KdTreeNode<TKey, TValue> kdTreeNode2 = ((num2 <= 0) ? node.RightChild : node.LeftChild);
|
|
if (kdTreeNode != null)
|
|
{
|
|
this.AddNearestNeighbours(kdTreeNode, target, hyperRect3, depth + 1, nearestNeighbours, maxSearchRadiusSquared);
|
|
}
|
|
TKey[] closestPoint = hyperRect4.GetClosestPoint(target, this.typeMath);
|
|
TKey tkey = this.typeMath.DistanceSquaredBetweenPoints(closestPoint, target);
|
|
if (this.typeMath.Compare(tkey, maxSearchRadiusSquared) <= 0)
|
|
{
|
|
if (nearestNeighbours.IsCapacityReached)
|
|
{
|
|
if (this.typeMath.Compare(tkey, nearestNeighbours.GetFurtherestDistance()) < 0)
|
|
{
|
|
this.AddNearestNeighbours(kdTreeNode2, target, hyperRect4, depth + 1, nearestNeighbours, maxSearchRadiusSquared);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
this.AddNearestNeighbours(kdTreeNode2, target, hyperRect4, depth + 1, nearestNeighbours, maxSearchRadiusSquared);
|
|
}
|
|
}
|
|
tkey = this.typeMath.DistanceSquaredBetweenPoints(node.Point, target);
|
|
if (this.typeMath.Compare(tkey, maxSearchRadiusSquared) <= 0)
|
|
{
|
|
nearestNeighbours.Add(node, tkey);
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600002D RID: 45 RVA: 0x000026D0 File Offset: 0x000008D0
|
|
public KdTreeNode<TKey, TValue>[] RadialSearch(TKey[] center, TKey radius, int count)
|
|
{
|
|
NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey> nearestNeighbourList = new NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey>(count, this.typeMath);
|
|
this.AddNearestNeighbours(this.root, center, HyperRect<TKey>.Infinite(this.dimensions, this.typeMath), 0, nearestNeighbourList, this.typeMath.Multiply(radius, radius));
|
|
count = nearestNeighbourList.Count;
|
|
KdTreeNode<TKey, TValue>[] array = new KdTreeNode<TKey, TValue>[count];
|
|
for (int i = 0; i < count; i++)
|
|
{
|
|
array[count - i - 1] = nearestNeighbourList.RemoveFurtherest();
|
|
}
|
|
return array;
|
|
}
|
|
|
|
// Token: 0x1700000B RID: 11
|
|
// (get) Token: 0x0600002E RID: 46 RVA: 0x00002740 File Offset: 0x00000940
|
|
// (set) Token: 0x0600002F RID: 47 RVA: 0x00002748 File Offset: 0x00000948
|
|
public int Count { get; private set; }
|
|
|
|
// Token: 0x06000030 RID: 48 RVA: 0x00002754 File Offset: 0x00000954
|
|
public bool TryFindValueAt(TKey[] point, out TValue value)
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode = this.root;
|
|
int num = -1;
|
|
while (kdTreeNode != null)
|
|
{
|
|
if (this.typeMath.AreEqual(point, kdTreeNode.Point))
|
|
{
|
|
value = kdTreeNode.Value;
|
|
return true;
|
|
}
|
|
num = (num + 1) % this.dimensions;
|
|
int num2 = this.typeMath.Compare(point[num], kdTreeNode.Point[num]);
|
|
kdTreeNode = kdTreeNode[num2];
|
|
}
|
|
value = default(TValue);
|
|
return false;
|
|
}
|
|
|
|
// Token: 0x06000031 RID: 49 RVA: 0x000027CC File Offset: 0x000009CC
|
|
public TValue FindValueAt(TKey[] point)
|
|
{
|
|
TValue tvalue;
|
|
if (this.TryFindValueAt(point, out tvalue))
|
|
{
|
|
return tvalue;
|
|
}
|
|
return default(TValue);
|
|
}
|
|
|
|
// Token: 0x06000032 RID: 50 RVA: 0x000027F0 File Offset: 0x000009F0
|
|
public bool TryFindValue(TValue value, out TKey[] point)
|
|
{
|
|
if (this.root == null)
|
|
{
|
|
point = null;
|
|
return false;
|
|
}
|
|
Queue<KdTreeNode<TKey, TValue>> queue = new Queue<KdTreeNode<TKey, TValue>>();
|
|
queue.Enqueue(this.root);
|
|
while (queue.Count > 0)
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode = queue.Dequeue();
|
|
if (kdTreeNode.Value.Equals(value))
|
|
{
|
|
point = kdTreeNode.Point;
|
|
return true;
|
|
}
|
|
for (int i = -1; i <= 1; i += 2)
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode2 = kdTreeNode[i];
|
|
if (kdTreeNode2 != null)
|
|
{
|
|
queue.Enqueue(kdTreeNode2);
|
|
}
|
|
}
|
|
}
|
|
point = null;
|
|
return false;
|
|
}
|
|
|
|
// Token: 0x06000033 RID: 51 RVA: 0x00002874 File Offset: 0x00000A74
|
|
public TKey[] FindValue(TValue value)
|
|
{
|
|
TKey[] array;
|
|
if (this.TryFindValue(value, out array))
|
|
{
|
|
return array;
|
|
}
|
|
return null;
|
|
}
|
|
|
|
// Token: 0x06000034 RID: 52 RVA: 0x00002890 File Offset: 0x00000A90
|
|
private void AddNodeToStringBuilder(KdTreeNode<TKey, TValue> node, StringBuilder sb, int depth)
|
|
{
|
|
sb.AppendLine(node.ToString());
|
|
for (int i = -1; i <= 1; i += 2)
|
|
{
|
|
for (int j = 0; j <= depth; j++)
|
|
{
|
|
sb.Append("\t");
|
|
}
|
|
sb.Append((i == -1) ? "L " : "R ");
|
|
if (node[i] == null)
|
|
{
|
|
sb.AppendLine("");
|
|
}
|
|
else
|
|
{
|
|
this.AddNodeToStringBuilder(node[i], sb, depth + 1);
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000035 RID: 53 RVA: 0x00002910 File Offset: 0x00000B10
|
|
public override string ToString()
|
|
{
|
|
if (this.root == null)
|
|
{
|
|
return "";
|
|
}
|
|
StringBuilder stringBuilder = new StringBuilder();
|
|
this.AddNodeToStringBuilder(this.root, stringBuilder, 0);
|
|
return stringBuilder.ToString();
|
|
}
|
|
|
|
// Token: 0x06000036 RID: 54 RVA: 0x00002948 File Offset: 0x00000B48
|
|
private void AddNodesToList(KdTreeNode<TKey, TValue> node, List<KdTreeNode<TKey, TValue>> nodes)
|
|
{
|
|
if (node == null)
|
|
{
|
|
return;
|
|
}
|
|
nodes.Add(node);
|
|
for (int i = -1; i <= 1; i += 2)
|
|
{
|
|
if (node[i] != null)
|
|
{
|
|
this.AddNodesToList(node[i], nodes);
|
|
node[i] = null;
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000037 RID: 55 RVA: 0x0000298C File Offset: 0x00000B8C
|
|
private void SortNodesArray(KdTreeNode<TKey, TValue>[] nodes, int byDimension, int fromIndex, int toIndex)
|
|
{
|
|
for (int i = fromIndex + 1; i <= toIndex; i++)
|
|
{
|
|
int num = i;
|
|
for (;;)
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode = nodes[num - 1];
|
|
KdTreeNode<TKey, TValue> kdTreeNode2 = nodes[num];
|
|
if (this.typeMath.Compare(kdTreeNode2.Point[byDimension], kdTreeNode.Point[byDimension]) >= 0)
|
|
{
|
|
break;
|
|
}
|
|
nodes[num - 1] = kdTreeNode2;
|
|
nodes[num] = kdTreeNode;
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000038 RID: 56 RVA: 0x000029E8 File Offset: 0x00000BE8
|
|
private void AddNodesBalanced(KdTreeNode<TKey, TValue>[] nodes, int byDimension, int fromIndex, int toIndex)
|
|
{
|
|
if (fromIndex == toIndex)
|
|
{
|
|
this.Add(nodes[fromIndex].Point, nodes[fromIndex].Value);
|
|
nodes[fromIndex] = null;
|
|
return;
|
|
}
|
|
this.SortNodesArray(nodes, byDimension, fromIndex, toIndex);
|
|
int num = fromIndex + (int)Math.Round((double)((float)(toIndex + 1 - fromIndex) / 2f)) - 1;
|
|
this.Add(nodes[num].Point, nodes[num].Value);
|
|
nodes[num] = null;
|
|
int num2 = (byDimension + 1) % this.dimensions;
|
|
if (fromIndex < num)
|
|
{
|
|
this.AddNodesBalanced(nodes, num2, fromIndex, num - 1);
|
|
}
|
|
if (toIndex > num)
|
|
{
|
|
this.AddNodesBalanced(nodes, num2, num + 1, toIndex);
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000039 RID: 57 RVA: 0x00002A84 File Offset: 0x00000C84
|
|
public void Balance()
|
|
{
|
|
List<KdTreeNode<TKey, TValue>> list = new List<KdTreeNode<TKey, TValue>>();
|
|
this.AddNodesToList(this.root, list);
|
|
this.Clear();
|
|
this.AddNodesBalanced(list.ToArray(), 0, 0, list.Count - 1);
|
|
}
|
|
|
|
// Token: 0x0600003A RID: 58 RVA: 0x00002AC0 File Offset: 0x00000CC0
|
|
private void RemoveChildNodes(KdTreeNode<TKey, TValue> node)
|
|
{
|
|
for (int i = -1; i <= 1; i += 2)
|
|
{
|
|
if (node[i] != null)
|
|
{
|
|
this.RemoveChildNodes(node[i]);
|
|
node[i] = null;
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600003B RID: 59 RVA: 0x00002AF7 File Offset: 0x00000CF7
|
|
public void Clear()
|
|
{
|
|
if (this.root != null)
|
|
{
|
|
this.RemoveChildNodes(this.root);
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600003C RID: 60 RVA: 0x00002B10 File Offset: 0x00000D10
|
|
public void SaveToFile(string filename)
|
|
{
|
|
BinaryFormatter binaryFormatter = new BinaryFormatter();
|
|
using (FileStream fileStream = File.Create(filename))
|
|
{
|
|
binaryFormatter.Serialize(fileStream, this);
|
|
fileStream.Flush();
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600003D RID: 61 RVA: 0x00002B54 File Offset: 0x00000D54
|
|
public static KdTree<TKey, TValue> LoadFromFile(string filename)
|
|
{
|
|
BinaryFormatter binaryFormatter = new BinaryFormatter();
|
|
KdTree<TKey, TValue> kdTree;
|
|
using (FileStream fileStream = File.Open(filename, FileMode.Open))
|
|
{
|
|
kdTree = (KdTree<TKey, TValue>)binaryFormatter.Deserialize(fileStream);
|
|
}
|
|
return kdTree;
|
|
}
|
|
|
|
// Token: 0x0600003E RID: 62 RVA: 0x00002B9C File Offset: 0x00000D9C
|
|
public IEnumerator<KdTreeNode<TKey, TValue>> GetEnumerator()
|
|
{
|
|
Stack<KdTreeNode<TKey, TValue>> left = new Stack<KdTreeNode<TKey, TValue>>();
|
|
Stack<KdTreeNode<TKey, TValue>> right = new Stack<KdTreeNode<TKey, TValue>>();
|
|
Action<KdTreeNode<TKey, TValue>> addLeft = delegate(KdTreeNode<TKey, TValue> node)
|
|
{
|
|
if (node.LeftChild != null)
|
|
{
|
|
left.Push(node.LeftChild);
|
|
}
|
|
};
|
|
Action<KdTreeNode<TKey, TValue>> addRight = delegate(KdTreeNode<TKey, TValue> node)
|
|
{
|
|
if (node.RightChild != null)
|
|
{
|
|
right.Push(node.RightChild);
|
|
}
|
|
};
|
|
if (this.root != null)
|
|
{
|
|
yield return this.root;
|
|
addLeft(this.root);
|
|
addRight(this.root);
|
|
for (;;)
|
|
{
|
|
if (left.Any<KdTreeNode<TKey, TValue>>())
|
|
{
|
|
KdTreeNode<TKey, TValue> kdTreeNode = left.Pop();
|
|
addLeft(kdTreeNode);
|
|
addRight(kdTreeNode);
|
|
yield return kdTreeNode;
|
|
}
|
|
else
|
|
{
|
|
if (!right.Any<KdTreeNode<TKey, TValue>>())
|
|
{
|
|
break;
|
|
}
|
|
KdTreeNode<TKey, TValue> kdTreeNode2 = right.Pop();
|
|
addLeft(kdTreeNode2);
|
|
addRight(kdTreeNode2);
|
|
yield return kdTreeNode2;
|
|
}
|
|
}
|
|
}
|
|
yield break;
|
|
}
|
|
|
|
// Token: 0x0600003F RID: 63 RVA: 0x00002BAB File Offset: 0x00000DAB
|
|
IEnumerator IEnumerable.GetEnumerator()
|
|
{
|
|
return this.GetEnumerator();
|
|
}
|
|
|
|
// Token: 0x0400000A RID: 10
|
|
private int dimensions;
|
|
|
|
// Token: 0x0400000B RID: 11
|
|
private ITypeMath<TKey> typeMath;
|
|
|
|
// Token: 0x0400000C RID: 12
|
|
private KdTreeNode<TKey, TValue> root;
|
|
}
|
|
}
|