これは、「デルタ内の点Pのすべての近傍を検索する」を解決する必要があるC＃KdTree実装です。関数型プログラミング技術を多用します（はい、私はPythonが大好きです）。それはテストされていますが、私はまだ理解に疑問があります。「平均的な場合、O（n ^ 2）よりも良い〜=関係が与えられたn点の集合を分割する」という問題を解決するためのコード（または擬似コード）は、別の回答に掲載されています。_TreeFindNearest()
/*
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
}
