• Documentation
  • Core API
  • SmartOpenHamburg API
  • Model Components API
  • Common API

    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 QuadTree<T>

    A Quadtree is a spatial index structure for efficient range querying of items bounded by 2D rectangles.
    s can be indexed by using their s.
    Any type of object can also be indexed, as long as it has an extent that can be represented by an .

    This Quadtree index provides a primary filter for range rectangle queries. The various query methods return a list of all items which may intersect the query rectangle. Note that it may thus return items which do not in fact intersect the query rectangle. A secondary filter is required to test for actual intersection between the query rectangle and the envelope of each candidate item. The secondary filter may be performed explicitly, or it may be provided implicitly by subsequent operations executed on the items (for instance, if the index query is followed by computing a spatial predicate between the query geometry and tree items, the envelope intersection check is performed automatically.

    This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accomodate any extent of dataset.

    This data structure is also known as an MX-CIF quadtree following the terminology usage of Samet and others.

    Inheritance
    System.Object
    QuadTree<T>
    Namespace: Mars.Common.Collections
    Assembly: Mars.Common.dll
    Syntax
    public class QuadTree<T> : object
    Type Parameters
    Name Description
    T

    Constructors

    QuadTree()

    Creates a new empty QuadTree<T>.
    Declaration
    public QuadTree()

    Properties

    Count

    Returns the number of items in the tree.
    Declaration
    public int Count { get; }
    Property Value
    Type Description
    System.Int32

    Depth

    Returns the number of levels in the tree.
    Declaration
    public int Depth { get; }
    Property Value
    Type Description
    System.Int32

    IsEmpty

    Tests whether the index contains any items.
    Declaration
    public bool IsEmpty { get; }
    Property Value
    Type Description
    System.Boolean

    Methods

    Insert(Envelope, T)

    Declaration
    public void Insert(Envelope itemEnv, T item)
    Parameters
    Type Name Description
    Envelope itemEnv
    T item

    Query(Envelope)

    Queries the tree and returns items which may lie in the given search envelope.
    Declaration
    public IList<T> Query(Envelope searchEnv)
    Parameters
    Type Name Description
    Envelope searchEnv The envelope of the desired query area.
    Returns
    Type Description
    IList<T> A List of items which may intersect the search envelope
    Remarks
    Precisely, the items that are returned are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be returned as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not returned - thus providing improved performance over a simple linear scan.

    Query(Envelope, Action<T>)

    Queries the tree and visits items which may lie in the given search envelope.
    Declaration
    public void Query(Envelope searchEnv, Action<T> visitor)
    Parameters
    Type Name Description
    Envelope searchEnv The envelope of the desired query area.
    Action<T> visitor A visitor object which is passed the visited items
    Remarks
    Precisely, the items that are visited are all items in the tree whose envelope may intersect the search Envelope. Note that some items with non-intersecting envelopes may be visited as well; the client is responsible for filtering these out. In most situations there will be many items in the tree which do not intersect the search envelope and which are not visited - thus providing improved performance over a simple linear scan.

    QueryAll()

    Return a list of all items in the QuadTree<T>.
    Declaration
    public IList<T> QueryAll()
    Returns
    Type Description
    IList<T>

    Remove(Envelope, T)

    Removes a single item from the tree.
    Declaration
    public bool Remove(Envelope itemEnv, T item)
    Parameters
    Type Name Description
    Envelope itemEnv The Envelope of the item to be removed.
    T item The item to remove.
    Returns
    Type Description
    System.Boolean true if the item was found (and thus removed).

    Extension Methods

    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)
    Matrix.Replace<T>(T, Object, Object)
    Matrix.IsEqual(Object, Object, Decimal, Decimal)
    Matrix.Concatenate<T>(T, T[])
    Back to top © 2022 MARS GROUP