Это реализация C # KdTree, которая должна решить «Найти всех соседей точки P в пределах дельта ». Он интенсивно использует методы функционального программирования (да, я люблю Python). Это проверено , но у меня все еще есть сомнения в понимании _TreeFindNearest(). Код (или псевдокод) для решения проблемы «Разделить набор из n точек с отношением ~ = лучше, чем O (n ^ 2) в среднем случае» размещен в другом ответе.
/*
Stripped C# 2.0 port of ``kdtree'', a library for working with kd-trees.
Copyright (C) 2007-2009 John Tsiombikas <nuclear@siggraph.org>
Copyright (C) 2010 Francesco Pretto <ceztko@gmail.com>
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
3. The name of the author may not be used to endorse or promote products
derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
OF SUCH DAMAGE.
*/
using System;
using System.Collections.Generic;
using System.Text;
namespace ITR.Data.NET
{
public class KdTree<T>
{
#region Fields
private Node _Root;
private int _Count;
private int _Dimension;
private CoordinateGetter<T>[] _GetCoordinate;
#endregion // Fields
#region Constructors
public KdTree(params CoordinateGetter<T>[] coordinateGetters)
{
_Dimension = coordinateGetters.Length;
_GetCoordinate = coordinateGetters;
}
#endregion // Constructors
#region Public methods
public void Insert(T location)
{
_TreeInsert(ref _Root, 0, location);
_Count++;
}
public void InsertAll(IEnumerable<T> locations)
{
foreach (T location in locations)
Insert(location);
}
public IEnumerable<T> FindNeighborsRange(T location, double range)
{
return _TreeFindNeighborsRange(_Root, 0, location, range);
}
#endregion // Public methods
#region Tree traversal
private void _TreeInsert(ref Node current, int currentPlane, T location)
{
if (current == null)
{
current = new Node(location);
return;
}
int nextPlane = (currentPlane + 1) % _Dimension;
if (_GetCoordinate[currentPlane](location) <
_GetCoordinate[currentPlane](current.Location))
_TreeInsert(ref current._Left, nextPlane, location);
else
_TreeInsert(ref current._Right, nextPlane, location);
}
private IEnumerable<T> _TreeFindNeighborsRange(Node current, int currentPlane,
T referenceLocation, double range)
{
if (current == null)
yield break;
double squaredDistance = 0;
for (int it = 0; it < _Dimension; it++)
{
double referenceCoordinate = _GetCoordinate[it](referenceLocation);
double currentCoordinate = _GetCoordinate[it](current.Location);
squaredDistance +=
(referenceCoordinate - currentCoordinate)
* (referenceCoordinate - currentCoordinate);
}
if (squaredDistance <= range * range)
yield return current.Location;
double coordinateRelativeDistance =
_GetCoordinate[currentPlane](referenceLocation)
- _GetCoordinate[currentPlane](current.Location);
Direction nextDirection = coordinateRelativeDistance <= 0.0
? Direction.LEFT : Direction.RIGHT;
int nextPlane = (currentPlane + 1) % _Dimension;
IEnumerable<T> subTreeNeighbors =
_TreeFindNeighborsRange(current[nextDirection], nextPlane,
referenceLocation, range);
foreach (T location in subTreeNeighbors)
yield return location;
if (Math.Abs(coordinateRelativeDistance) <= range)
{
subTreeNeighbors =
_TreeFindNeighborsRange(current.GetOtherChild(nextDirection),
nextPlane, referenceLocation, range);
foreach (T location in subTreeNeighbors)
yield return location;
}
}
#endregion // Tree traversal
#region Node class
public class Node
{
#region Fields
private T _Location;
internal Node _Left;
internal Node _Right;
#endregion // Fields
#region Constructors
internal Node(T nodeValue)
{
_Location = nodeValue;
_Left = null;
_Right = null;
}
#endregion // Contructors
#region Children Indexers
public Node this[Direction direction]
{
get { return direction == Direction.LEFT ? _Left : Right; }
}
public Node GetOtherChild(Direction direction)
{
return direction == Direction.LEFT ? _Right : _Left;
}
#endregion // Children Indexers
#region Properties
public T Location
{
get { return _Location; }
}
public Node Left
{
get { return _Left; }
}
public Node Right
{
get { return _Right; }
}
#endregion // Properties
}
#endregion // Node class
#region Properties
public int Count
{
get { return _Count; }
set { _Count = value; }
}
public Node Root
{
get { return _Root; }
set { _Root = value; }
}
#endregion // Properties
}
#region Enums, delegates
public enum Direction
{
LEFT = 0,
RIGHT
}
public delegate double CoordinateGetter<T>(T location);
#endregion // Enums, delegates
}