• Documentation
  • Core API
  • SmartOpenHamburg API
  • Model Components API
  • Common API
Search Results for

    Show / Hide Table of Contents
    • Mars.Common
      • GeoHash
      • GeoHashDecoder
      • GeohashDecodeResult
      • GeoHashEncoder
      • GeoHashPrecision
      • Hyperrectangle
      • InputHashHelper
      • PositionHelper
    • Mars.Common.Collections
      • BinaryArrayHeap<T>
      • DoubleBits
      • FibonacciHeap<T, TKey>
      • FibonacciHeapDoubleKey<T>
      • FibonacciHeapNode<T, TKey>
      • FibonacciHeapNodeDoubleKey<T>
      • HeapNode
      • IntervalSize
      • K2DTree<T>
      • K2dTreeNode<T>
      • KdTree
      • KdTree<T>
      • KdTreeBase<TNode>
      • KdTreeNode
      • KdTreeNode<T>
      • KdTreeNodeBase<TNode>
      • KdTreeNodeCollection<TNode>
      • KdTreeNodeList<T>
      • Key
      • Node<T>
      • NodeBase<T>
      • NodeDataContainer<T>
      • NodeDistance<TNode>
      • QuadTree<T>
      • Root<T>
      • TreeDataContainer<T>
    • Mars.Common.Collections.CritBit
      • ICritBitTree<TValue>
    • Mars.Common.Collections.Graph
      • EdgeData
      • GraphData
      • GraphSerializer
      • ISpatialGraph
      • KeyContainer
      • NodeData
      • SpatialGraph
      • SpatialGraphHelper
    • Mars.Common.Collections.Graph.Algorithms
      • AStar
      • CompressedPathDatabase
      • ContractionSearch
      • DepthLimitedTraversal
    • Mars.Common.Collections.Graph.Helper
      • INodeFinder
      • KdTreeNodeFinder
      • RunLengthEncoder
    • Mars.Common.Collections.KNNGraph
      • DefaultRandomGenerator
      • DistanceUtils
      • EventSources
      • EventSources.GraphBuildEventSource
      • EventSources.GraphSearchEventSource
      • IProgressReporter
      • IProvideRandomValues
      • KnnGraph<TItem, TDistance>
      • KnnGraph<TItem, TDistance>.KnnSearchResult
      • KnnGraph<TItem, TDistance>.Parameters
      • Node
      • ReverseComparer<T>
      • ReverseComparerExtensions
      • SelectionKind
      • TravelingCosts<TItem, TDistance>
    • Mars.Common.Compat
      • FormatDecoderAttribute
      • FormatEncoderAttribute
      • FormatHandlerAttribute
      • IntegerAttribute
      • NegativeIntegerAttribute
      • NonnegativeIntegerAttribute
      • NonpositiveIntegerAttribute
      • PositiveIntegerAttribute
    • Mars.Common.Data
      • DomainDataImporter
    • Mars.Common.Data.Providers
      • AscDataProvider
      • GeoJsonFeatureCollectionConverter
      • GeoJsonFeatureConverter
      • GeometryDataProvider
      • GraphMlProvider
      • HttpDataProvider
      • IDataProvider<TInput>
      • JsonFileDataProvider
      • JsonTextDataProvider
      • XmlFileDataProvider
      • XmlTextDataProvider
    • Mars.Common.Exceptions
      • DimensionMismatchException
      • ParseException
    • Mars.Common.IO
      • ExtensionMethods
      • FileClientUtils
      • FileKeys
      • HttpClientUtils
      • ObjectSerialize
      • Serializer
      • SerializerCompression
      • SparseFormat
      • SparseReader
      • SparseWriter
    • Mars.Common.IO.Attributes
      • SerializationBinderAttribute
      • SurrogateSelectorAttribute
    • Mars.Common.IO.Console
      • ChildProgressBar
      • IProgressBar
      • ProgressBar
      • ProgressBarBase
      • ProgressBarHeight
      • ProgressBarOptions
      • ProgressBarSimple
    • Mars.Common.IO.Csv
      • CsvAnalyzer
      • CsvReader
      • CsvReader.RecordEnumerator
      • CsvWriter
      • MissingFieldAction
      • ParseErrorAction
      • ValueTrimmingOptions
    • Mars.Common.IO.Events
      • ParseErrorEventArgs
    • Mars.Common.IO.Exceptions
      • MalformedCsvException
      • MissingFieldCsvException
    • Mars.Common.IO.Mapped
      • Context
      • DefaultArrayFactory
      • Extensions
      • IArrayFactory
      • ISerializableToStream
      • MappedAccessor<T>
      • MemoryMap
      • MemoryMap.CreateAccessorFunc<T>
      • MemoryMap.ReadFromDelegate<T>
      • MemoryMap.WriteToDelegate<T>
      • MemoryMapDelegates
      • MemoryMapDelegates.CreateAccessorFunc<T>
      • MemoryMapStream
    • Mars.Common.IO.Mapped.Accessors
      • MappedAccessorByte
      • MappedAccessorDouble
      • MappedAccessorInt16
      • MappedAccessorInt32
      • MappedAccessorInt64
      • MappedAccessorSingle
      • MappedAccessorUInt16
      • MappedAccessorUInt32
      • MappedAccessorUInt64
      • MappedAccessorVariable<T>
    • Mars.Common.IO.Mapped.Arrays
      • Array<T>
      • ArrayBase<T>
      • ArrayProfile
      • MappedArray<TMapped, T>
      • MappedArray<TMapped, T>.MapFrom
      • MappedArray<TMapped, T>.MapTo
      • MemoryArray<T>
      • VariableArray<T>
    • Mars.Common.IO.Mapped.Collections
      • MemoryBackedDictionary<TKey, TValue>
      • MemoryBackedList<T>
    • Mars.Common.IO.Mapped.Indexes
      • Index<T>
    • Mars.Common.IO.Mapped.Streams
      • CappedStream
    • Mars.Common.Socket
      • ByteOrder
      • CloseEventArgs
      • CloseStatusCode
      • CompressionMethod
      • ErrorEventArgs
      • Ext
      • MessageEventArgs
      • WebSocket
      • WebSocketException
      • WebSocketState
    • Mars.Common.Socket.Server
      • IWebSocketSession
      • WebHeaderCollection
      • WebSocketBehavior
      • WebSocketContext
      • WebSocketServer
      • WebSocketServiceHost
      • WebSocketServiceManager
      • WebSocketSessionManager
    • Mars.Numerics
      • Classes
      • Combinatorics
      • Constants
      • Distance
      • Elementwise
      • Jagged
      • MathematicsException
      • MathHelper
      • Matrix
      • MatrixOrder
      • MatrixType
      • Norm
      • Sort
      • Sorting
      • Sparse
      • Sparse<T>
      • Tools
      • Vector
      • VectorHelper
      • VectorType
    • Mars.Numerics.Comparers
      • ArrayComparer<T>
      • ComparerDirection
      • CustomComparer<T>
      • ElementComparer
      • ElementComparer<T>
      • GeneralComparer
      • StableComparer<T>
    • Mars.Numerics.Distances
      • Angular
      • Chebyshev
      • Cosine
      • Dirac<T>
      • Euclidean
      • Hamming
      • Hamming<T>
      • Haversine
      • Jaccard
      • Jaccard<T>
      • Kulczynski
      • Levenshtein
      • Levenshtein<T>
      • Manhattan
      • Matching
      • Minkowski
      • SquareEuclidean
      • Vincenty
      • Vincenty.Ellipsoid
    • Mars.Numerics.Distances.Base
      • IDistance<T>
      • IDistance<TFirst, TSecond>
      • IMetric<T>
      • ISimilarity<T, TU>
      • ISimilarity<T>
    • Mars.Numerics.Exceptions
      • DimensionMismatchException
      • NonPositiveDefiniteMatrixException
      • SingularMatrixException
    • Mars.Numerics.Formats
      • DefaultMatrixFormatProvider
      • IMatrixFormatProvider
      • MatrixFormatProviderBase
      • MatrixFormatter
      • OctaveMatrixFormatProvider
    • Mars.Numerics.Ranges
      • ByteRange
      • DoubleRange
      • FloatRange
      • IntRange
      • IRange<T>
    • Mars.Numerics.Statistics
      • ConstValueDistribution<T>
      • Distribution<T>
      • FastGaussianDistributionD
      • FastGaussianDistributionF
      • IDistribution
      • UniformDiscreteDistribution
      • UniformDistributionD
      • UniformDistributionF
    • Mars.Numerics.Statistics.Base
      • BinarySearch
      • DistributionBase
      • ISampleableDistribution<TObservations>
      • IUnivariateDistribution
      • IUnivariateDistribution<TObservation>
      • UnivariateDiscreteDistribution

    Class KdTree<T>

    K-dimensional tree.
    Inheritance
    System.Object
    Mars.Common.Core.Collections.SimpleTree.BinaryTree<KdTreeNode<T>>
    KdTreeBase<KdTreeNode<T>>
    KdTree<T>
    Implements
    System.Collections.Generic.IEnumerable<KdTreeNode<T>>
    System.Collections.IEnumerable
    Inherited Members
    KdTreeBase<KdTreeNode<T>>.Dimensions
    KdTreeBase<KdTreeNode<T>>.Distance
    KdTreeBase<KdTreeNode<T>>.Count
    KdTreeBase<KdTreeNode<T>>.Leaves
    KdTreeBase<KdTreeNode<T>>.Nearest(Position, Double, Int32, Func<KdTreeNode<T>, Boolean>)
    KdTreeBase<KdTreeNode<T>>.Nearest(Double[], Double, Int32, Func<KdTreeNode<T>, Boolean>)
    KdTreeBase<KdTreeNode<T>>.Nearest(Double[], Double, Func<KdTreeNode<T>, Boolean>)
    KdTreeBase<KdTreeNode<T>>.Nearest(Double[], Int32, Func<KdTreeNode<T>, Boolean>)
    KdTreeBase<KdTreeNode<T>>.Nearest(Double[])
    KdTreeBase<KdTreeNode<T>>.Nearest(Double[], Double, Func<KdTreeNode<T>, Boolean>)
    KdTreeBase<KdTreeNode<T>>.Nearest<T1>(Double[], Double, Int32, Func<KdTreeNode<T>, T1, Boolean>, T1)
    KdTreeBase<KdTreeNode<T>>.Nearest<T1, T2>(Double[], Double, Int32, Func<KdTreeNode<T>, T1, T2, Boolean>, T1, T2)
    KdTreeBase<KdTreeNode<T>>.Nearest<T1, T2, T3>(Double[], Double, Int32, Func<KdTreeNode<T>, T1, T2, T3, Boolean>, T1, T2, T3)
    KdTreeBase<KdTreeNode<T>>.ApproximateNearest(Double[], Int32, Double)
    KdTreeBase<KdTreeNode<T>>.ApproximateNearest(Double[], Double, Double)
    KdTreeBase<KdTreeNode<T>>.ApproximateNearest(Double[], Double)
    KdTreeBase<KdTreeNode<T>>.ApproximateNearest(Double[], Int32, Int32)
    KdTreeBase<KdTreeNode<T>>.ApproximateNearest(Double[], Int32)
    KdTreeBase<KdTreeNode<T>>.InsideRegion(Hyperrectangle)
    KdTreeBase<KdTreeNode<T>>.Clear()
    KdTreeBase<KdTreeNode<T>>.CopyTo(KdTreeNode<T>[], Int32)
    KdTreeBase<KdTreeNode<T>>.CreateRoot(Double[][], Boolean, Int32)
    KdTreeBase<KdTreeNode<T>>.AddNode(Double[])
    Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.Root
    Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.GetEnumerator()
    Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.System.Collections.IEnumerable.GetEnumerator()
    Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.SerializeJson()
    Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.Deserialize(System.String)
    Mars.Common.Core.Collections.SimpleTree.BinaryTree<Mars.Common.Collections.KdTreeNode<T>>.Traverse(Mars.Common.Core.Collections.SimpleTree.BinaryTraversalMethod<Mars.Common.Collections.KdTreeNode<T>>)
    System.Object.Equals(System.Object)
    System.Object.Equals(System.Object, System.Object)
    System.Object.GetHashCode()
    System.Object.GetType()
    System.Object.MemberwiseClone()
    System.Object.ReferenceEquals(System.Object, System.Object)
    System.Object.ToString()
    Namespace: Mars.Common.Collections
    Assembly: Mars.Common.dll
    Syntax
    [Serializable]
    public class KdTree<T> : KdTreeBase<KdTreeNode<T>>, IEnumerable<KdTreeNode<T>>, IEnumerable
    Type Parameters
    Name Description
    T The type of the value being stored.
    Remarks

    A k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

    The k-d tree is a binary tree in which every node is a k-dimensional point. Every non- leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as half-spaces. Points to the left of this hyperplane represent the left subtree of that node and points right of the hyperplane are represented by the right subtree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right subtree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.

    References:

    • ScienceDirect, Log-logarithmic worst-case range queries are possible in space Θ(N). Available on: https://www.sciencedirect.com/science/article/pii/0020019083900753?via%3Dihub

    Examples
    // This is the same example found in Wikipedia page on
    // k-d trees: http://en.wikipedia.org/wiki/K-d_tree
    
    // Suppose we have the following set of points:
    
    double[][] points =
    {
    new double[] { 2, 3 },
    new double[] { 5, 4 },
    new double[] { 9, 6 },
    new double[] { 4, 7 },
    new double[] { 8, 1 },
    new double[] { 7, 2 },
    };
    
    
    // To create a tree from a set of points, we use
    KdTree<int> tree = KdTree.FromData<int>(points);
    
    // Now we can manually navigate the tree
    KdTreeNode<int> node = tree.Root.Left.Right;
    
    // Or traverse it automatically
    foreach (KdTreeNode<int> n in tree)
    {
    double[] location = n.Position;
    Assert.Equal(2, location.Length);
    }
    
    // Given a query point, we can also query for other
    // points which are near this point within a radius
    
    double[] query = new double[] { 5, 3 };
    
    // Locate all nearby points within an euclidean distance of 1.5
    // (answer should be be a single point located at position (5,4))
    KdTreeNodeCollection<int> result = tree.Nearest(query, radius: 1.5); 
    
    // We can also use alternate distance functions
    tree.Distance = Mars.Numerics.Distance.Manhattan;
    
    // And also query for a fixed number of neighbor points
    // (answer should be the points at (5,4), (7,2), (2,3))
    KdTreeNodeCollection<int> neighbors = tree.Nearest(query, neighbors: 3);

    Constructors

    KdTree(Int32)

    Creates a new KdTree<T>.
    Declaration
    public KdTree(int dimensions)
    Parameters
    Type Name Description
    System.Int32 dimensions The number of dimensions in the tree.

    KdTree(Int32, KdTreeNode<T>)

    Creates a new KdTree<T>.
    Declaration
    public KdTree(int dimension, KdTreeNode<T> root)
    Parameters
    Type Name Description
    System.Int32 dimension The number of dimensions in the tree.
    KdTreeNode<T> root The Root node, if already existent.

    KdTree(Int32, KdTreeNode<T>, Int32, Int32)

    Creates a new KdTree<T>.
    Declaration
    public KdTree(int dimension, KdTreeNode<T> root, int count, int leaves)
    Parameters
    Type Name Description
    System.Int32 dimension The number of dimensions in the tree.
    KdTreeNode<T> root The Root node, if already existent.
    System.Int32 count The number of elements in the Root node.
    System.Int32 leaves The number of leaves linked through the Root node.

    Methods

    Add(Position, T)

    Adds a new Position to this tree
    Declaration
    public void Add(Position position, T value)
    Parameters
    Type Name Description
    Position position A Position with respective coordinate, geospatial or not
    T value The value to be inserted

    Add(Double[], T)

    Inserts a value in the tree at the desired position.
    Declaration
    public void Add(double[] position, T value)
    Parameters
    Type Name Description
    System.Double[] position A double-vector with the same number of elements as dimensions in the tree.
    T value The value to be inserted.

    Create(Double[][], T[], Int32, Int32, Int32, Int32, ElementComparer, ref Int32)

    Creates a new KdTree<T> from given and associated .
    Declaration
    protected static KdTreeNode<T> Create(double[][] points, T[] values, int depth, int k, int start, int length, ElementComparer comparer, ref int leaves)
    Parameters
    Type Name Description
    System.Double[][] points
    T[] values
    System.Int32 depth
    System.Int32 k
    System.Int32 start
    System.Int32 length
    ElementComparer comparer
    System.Int32 leaves
    Returns
    Type Description
    KdTreeNode<T> Returns a new KdTree<T> filled by given and associated to respective .

    Implements

    System.Collections.Generic.IEnumerable<T>
    System.Collections.IEnumerable

    Extension Methods

    DomainDataImporter.Import(IEnumerable<Object>, InputConfiguration)
    DomainDataImporter.Import(Object, InputConfiguration)
    ObjectSerialize.Serialize(Object)
    Serializer.Save<T>(T, Stream, SerializerCompression)
    Serializer.Save<T>(T, BinaryFormatter, Stream, SerializerCompression)
    Serializer.Save<T>(T, String)
    Serializer.Save<T>(T, String, SerializerCompression)
    Serializer.Save<T>(T, out Byte[], SerializerCompression)
    Combinatorics.Subsets<T>(IEnumerable<T>, Boolean)
    Combinatorics.Subsets<T>(IEnumerable<T>, Int32, Boolean)
    Matrix.Replace<T>(T, Object, Object)
    Matrix.IsEqual(Object, Object, Decimal, Decimal)
    Matrix.SetEquals<T>(IEnumerable<T>, IEnumerable<T>)
    Matrix.Concatenate<T>(T, T[])
    In This Article
    Back to top © 2022 MARS GROUP