Welcome to locus’s documentation!

Note

If object is not listed in documentation it should be considered as implementation detail that can change and should not be relied upon.

kd module

class locus.kd.Tree(points: Sequence[ground.hints.Point], *, context: Optional[ground.base.Context] = None)[source]

Represents k-dimensional (aka kd) tree.

Reference:

https://en.wikipedia.org/wiki/K-d_tree

__init__(points: Sequence[ground.hints.Point], *, context: Optional[ground.base.Context] = None)None[source]

Initializes tree from points.

Time complexity:

O(dimension * size * log size)

Memory complexity:

O(dimension * size)

where dimension = len(points[0]), size = len(points).

property context: ground.base.Context

Returns context of the tree.

Time complexity:

O(1)

Memory complexity:

O(1)

property points: Sequence[ground.hints.Point]

Returns underlying points.

Time complexity:

O(1)

Memory complexity:

O(1)

>>> from ground.base import get_context
>>> context = get_context()
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.points == points
True
n_nearest_indices(n: int, point: ground.hints.Point)Sequence[int][source]

Searches for indices of points in the tree that are the nearest to the given point.

Time complexity:

O(min(n, size) * log size)

Memory complexity:

O(min(n, size) * log size)

where size = len(self.points).

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Parameters
  • n – positive upper bound for number of result indices.

  • point – input point.

Returns

indices of points in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.n_nearest_indices(2, Point(0, 0)) == [2, 3]
True
>>> (tree.n_nearest_indices(len(points), Point(0, 0))
...  == range(len(points)))
True
n_nearest_points(n: int, point: ground.hints.Point)Sequence[ground.hints.Point][source]

Searches for points in the tree the nearest to the given point.

Time complexity:

O(min(n, size) * log size)

Memory complexity:

O(min(n, size) * log size)

where size = len(self.points).

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Parameters
  • n – positive upper bound for number of result points.

  • point – input point.

Returns

points in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> (tree.n_nearest_points(2, Point(0, 0))
...  == [Point(-3, 2), Point(-2, 3)])
True
>>> tree.n_nearest_points(len(points), Point(0, 0)) == points
True
n_nearest_items(n: int, point: ground.hints.Point)Sequence[Tuple[int, ground.hints.Point]][source]

Searches for indices with points in the tree that are the nearest to the given point.

Time complexity:

O(min(n, size) * log size)

Memory complexity:

O(min(n, size) * log size)

where size = len(self.points).

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Parameters
  • n – positive upper bound for number of result indices.

  • point – input point.

Returns

indices with points in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> (tree.n_nearest_items(2, Point(0, 0))
...  == [(2, Point(-3, 2)), (3, Point(-2, 3))])
True
>>> (tree.n_nearest_items(len(points), Point(0, 0))
...  == list(enumerate(points)))
True
nearest_index(point: ground.hints.Point)int[source]

Searches for index of a point in the tree that is the nearest to the given point.

Time complexity:

O(log size)

Memory complexity:

O(log size)

where size = len(self.points).

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Parameters

point – input point.

Returns

index of a point in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.nearest_index(Point(0, 0)) == 2
True
>>> tree.nearest_index(Point(-3, 2)) == 2
True
nearest_point(point: ground.hints.Point)ground.hints.Point[source]

Searches for point in the tree that is the nearest to the given point.

Time complexity:

O(log size)

Memory complexity:

O(log size)

where size = len(self.points).

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Parameters

point – input point.

Returns

point in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.nearest_point(Point(0, 0)) == Point(-3, 2)
True
>>> tree.nearest_point(Point(-3, 2)) == Point(-3, 2)
True
nearest_item(point: ground.hints.Point)Tuple[int, ground.hints.Point][source]

Searches for index with point in the tree that is the nearest to the given point.

Time complexity:

O(log size)

Memory complexity:

O(log size)

where size = len(self.points).

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Parameters

point – input point.

Returns

index with point in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.nearest_item(Point(0, 0)) == (2, Point(-3, 2))
True
>>> tree.nearest_item(Point(-3, 2)) == (2, Point(-3, 2))
True
find_box_indices(box: ground.hints.Box)List[int][source]

Searches for indices of points that lie inside the given box.

Time complexity:

O(dimension * size ** (1 - 1 / dimension) + hits_count)

Memory complexity:

O(dimension * size ** (1 - 1 / dimension) + hits_count)

where dimension = len(self.points[0]), size = len(self.points), hits_count — number of found indices.

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Range_search

Parameters

box – box to search in.

Returns

indices of points that lie inside the box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.find_box_indices(Box(-3, 3, 0, 1)) == []
True
>>> tree.find_box_indices(Box(-3, 3, 0, 2)) == [2]
True
>>> tree.find_box_indices(Box(-3, 3, 0, 3)) == [2, 3]
True
find_box_points(box: ground.hints.Box)List[ground.hints.Point][source]

Searches for points that lie inside the given box.

Time complexity:

O(dimension * size ** (1 - 1 / dimension) + hits_count)

Memory complexity:

O(dimension * size ** (1 - 1 / dimension) + hits_count)

where dimension = len(self.points[0]), size = len(self.points), hits_count — number of found points.

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Range_search

Parameters

box – box to search in.

Returns

points that lie inside the box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.find_box_points(Box(-3, 3, 0, 1)) == []
True
>>> tree.find_box_points(Box(-3, 3, 0, 2)) == [Point(-3, 2)]
True
>>> (tree.find_box_points(Box(-3, 3, 0, 3))
...  == [Point(-3, 2), Point(-2, 3)])
True
find_box_items(box: ground.hints.Box)List[Tuple[int, ground.hints.Point]][source]

Searches for indices with points in the tree that lie inside the given box.

Time complexity:

O(dimension * size ** (1 - 1 / dimension) + hits_count)

Memory complexity:

O(dimension * size ** (1 - 1 / dimension) + hits_count)

where dimension = len(self.points[0]), size = len(self.points), hits_count — number of found indices with points.

Reference:

https://en.wikipedia.org/wiki/K-d_tree#Range_search

Parameters

box – box to search in.

Returns

indices with points in the tree that lie inside the box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points)
>>> tree.find_box_items(Box(-3, 3, 0, 1)) == []
True
>>> tree.find_box_items(Box(-3, 3, 0, 2)) == [(2, Point(-3, 2))]
True
>>> (tree.find_box_items(Box(-3, 3, 0, 3))
...  == [(2, Point(-3, 2)), (3, Point(-2, 3))])
True

r module

class locus.r.Tree(boxes: Sequence[ground.hints.Box], *, max_children: int = 16, context: Optional[ground.base.Context] = None)[source]

Represents packed 2-dimensional Hilbert R-tree.

Reference:

https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees

__init__(boxes: Sequence[ground.hints.Box], *, max_children: int = 16, context: Optional[ground.base.Context] = None)None[source]

Initializes tree from boxes.

Time complexity:

O(size * log size)

Memory complexity:

O(size)

where size = len(boxes).

property boxes: Sequence[ground.hints.Box]

Returns underlying boxes.

Time complexity:

O(1)

Memory complexity:

O(1)

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.boxes == boxes
True
property context: ground.base.Context

Returns context of the tree.

Time complexity:

O(1)

Memory complexity:

O(1)

property max_children: int

Returns maximum number of children in each node.

Time complexity:

O(1)

Memory complexity:

O(1)

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.max_children == 16
True
find_subsets(box: ground.hints.Box)List[ground.hints.Box][source]

Searches for boxes that lie inside the given box.

Time complexity:

O(max_children * log size + hits_count)

Memory complexity:

O(max_children * log size + hits_count)

where size = len(self.boxes), max_children = self.max_children, hits_count — number of found boxes.

Parameters

box – input box.

Returns

boxes that lie inside the input box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.find_subsets(Box(-1, 1, 0, 1)) == [Box(-1, 1, 0, 1)]
True
>>> (tree.find_subsets(Box(-2, 2, 0, 2))
...  == [Box(-1, 1, 0, 1), Box(-2, 2, 0, 2)])
True
>>> (tree.find_subsets(Box(-3, 3, 0, 3))
...  == [Box(-1, 1, 0, 1), Box(-2, 2, 0, 2), Box(-3, 3, 0, 3)])
True
find_subsets_indices(box: ground.hints.Box)List[int][source]

Searches for indices of boxes that lie inside the given box.

Time complexity:

O(max_children * log size + hits_count)

Memory complexity:

O(max_children * log size + hits_count)

where size = len(self.boxes), max_children = self.max_children, hits_count — number of found indices.

Parameters

box – input box.

Returns

indices of boxes that lie inside the input box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.find_subsets_indices(Box(-1, 1, 0, 1)) == [0]
True
>>> tree.find_subsets_indices(Box(-2, 2, 0, 2)) == [0, 1]
True
>>> tree.find_subsets_indices(Box(-3, 3, 0, 3)) == [0, 1, 2]
True
find_subsets_items(box: ground.hints.Box)List[Tuple[int, ground.hints.Box]][source]

Searches for indices with boxes that lie inside the given box.

Time complexity:

O(max_children * log size + hits_count)

Memory complexity:

O(max_children * log size + hits_count)

where size = len(self.boxes), max_children = self.max_children, hits_count — number of found indices with boxes.

Parameters

box – input box.

Returns

indices with boxes that lie inside the input box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> (tree.find_subsets_items(Box(-1, 1, 0, 1))
...  == [(0, Box(-1, 1, 0, 1))])
True
>>> (tree.find_subsets_items(Box(-2, 2, 0, 2))
...  == [(0, Box(-1, 1, 0, 1)), (1, Box(-2, 2, 0, 2))])
True
>>> (tree.find_subsets_items(Box(-3, 3, 0, 3))
...  == [(0, Box(-1, 1, 0, 1)), (1, Box(-2, 2, 0, 2)),
...      (2, Box(-3, 3, 0, 3))])
True
find_supersets(box: ground.hints.Box)List[ground.hints.Box][source]

Searches for boxes that contain the given box.

Time complexity:

O(max_children * log size + hits_count)

Memory complexity:

O(max_children * log size + hits_count)

where size = len(self.boxes), max_children = self.max_children, hits_count — number of found boxes.

Parameters

box – input box.

Returns

boxes that contain the input box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.find_supersets(Box(-10, 10, 0, 10)) == [Box(-10, 10, 0, 10)]
True
>>> (tree.find_supersets(Box(-9, 9, 0, 9))
...  == [Box(-9, 9, 0, 9), Box(-10, 10, 0, 10)])
True
>>> (tree.find_supersets(Box(-8, 8, 0, 8))
...  == [Box(-8, 8, 0, 8), Box(-9, 9, 0, 9), Box(-10, 10, 0, 10)])
True
find_supersets_indices(box: ground.hints.Box)List[int][source]

Searches for indices of boxes that contain the given box.

Time complexity:

O(max_children * log size + hits_count)

Memory complexity:

O(max_children * log size + hits_count)

where size = len(self.boxes), max_children = self.max_children, hits_count — number of found indices.

Parameters

box – input box.

Returns

indices of boxes that contain the input box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.find_supersets_indices(Box(-10, 10, 0, 10)) == [9]
True
>>> tree.find_supersets_indices(Box(-9, 9, 0, 9)) == [8, 9]
True
>>> tree.find_supersets_indices(Box(-8, 8, 0, 8)) == [7, 8, 9]
True
find_supersets_items(box: ground.hints.Box)List[Tuple[int, ground.hints.Box]][source]

Searches for indices with boxes that contain the given box.

Time complexity:

O(max_children * log size + hits_count)

Memory complexity:

O(max_children * log size + hits_count)

where size = len(self.boxes), max_children = self.max_children, hits_count — number of found indices with boxes.

Parameters

box – input box.

Returns

indices with boxes that contain the input box.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> (tree.find_supersets_items(Box(-10, 10, 0, 10))
...  == [(9, Box(-10, 10, 0, 10))])
True
>>> (tree.find_supersets_items(Box(-9, 9, 0, 9))
...  == [(8, Box(-9, 9, 0, 9)), (9, Box(-10, 10, 0, 10))])
True
>>> (tree.find_supersets_items(Box(-8, 8, 0, 8))
...  == [(7, Box(-8, 8, 0, 8)), (8, Box(-9, 9, 0, 9)),
...      (9, Box(-10, 10, 0, 10))])
True
n_nearest_indices(n: int, point: ground.hints.Point)Sequence[int][source]

Searches for indices of boxes in the tree the nearest to the given point.

Time complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

where size = len(self.boxes), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result indices.

  • point – input point.

Returns

indices of boxes in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.n_nearest_indices(2, Point(0, 0)) == [9, 8]
True
>>> (tree.n_nearest_indices(len(boxes), Point(0, 0))
...  == range(len(boxes)))
True
n_nearest_boxes(n: int, point: ground.hints.Point)Sequence[ground.hints.Box][source]

Searches for boxes in the tree the nearest to the given point.

Time complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

where size = len(self.boxes), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result boxes.

  • point – input point.

Returns

boxes in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> (tree.n_nearest_boxes(2, Point(0, 0))
...  == [Box(-10, 10, 0, 10), Box(-9, 9, 0, 9)])
True
>>> tree.n_nearest_boxes(len(boxes), Point(0, 0)) == boxes
True
n_nearest_items(n: int, point: ground.hints.Point)Sequence[Tuple[int, ground.hints.Box]][source]

Searches for indices with boxes in the tree the nearest to the given point.

Time complexity:

O(n * max_children * log size) if n < size, O(size) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(size) otherwise

where size = len(self.boxes), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result indices with boxes.

  • point – input point.

Returns

indices with boxes in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> (tree.n_nearest_items(2, Point(0, 0))
...  == [(9, Box(-10, 10, 0, 10)), (8, Box(-9, 9, 0, 9))])
True
>>> (tree.n_nearest_items(len(boxes), Point(0, 0))
...  == list(enumerate(boxes)))
True
nearest_index(point: ground.hints.Point)int[source]

Searches for index of box in the tree the nearest to the given point.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.boxes), max_children = self.max_children.

Parameters

point – input point.

Returns

index of box in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.nearest_index(Point(0, 0)) == 9
True
nearest_box(point: ground.hints.Point)ground.hints.Box[source]

Searches for box in the tree the nearest to the given point.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.boxes), max_children = self.max_children.

Parameters

point – input point.

Returns

box in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.nearest_box(Point(0, 0)) == Box(-10, 10, 0, 10)
True
nearest_item(point: ground.hints.Point)Tuple[int, ground.hints.Box][source]

Searches for index with box in the tree the nearest to the given point.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.boxes), max_children = self.max_children.

Parameters

point – input point.

Returns

index with box in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes)
>>> tree.nearest_item(Point(0, 0)) == (9, Box(-10, 10, 0, 10))
True
>>> tree.nearest_item(Point(-10, 0)) == (9, Box(-10, 10, 0, 10))
True
>>> tree.nearest_item(Point(-10, 10)) == (9, Box(-10, 10, 0, 10))
True
>>> tree.nearest_item(Point(10, 0)) == (9, Box(-10, 10, 0, 10))
True
>>> tree.nearest_item(Point(10, 10)) == (9, Box(-10, 10, 0, 10))
True

segmental module

class locus.segmental.Tree(segments: Sequence[ground.hints.Segment], *, max_children: int = 16, context: Optional[ground.base.Context] = None)[source]

Represents packed 2-dimensional segmental Hilbert R-tree.

Reference:

https://en.wikipedia.org/wiki/Hilbert_R-tree#Packed_Hilbert_R-trees

__init__(segments: Sequence[ground.hints.Segment], *, max_children: int = 16, context: Optional[ground.base.Context] = None)None[source]

Initializes tree from segments.

Time complexity:

O(size * log size)

Memory complexity:

O(size)

where size = len(segments).

property context: ground.base.Context

Returns context of the tree.

Time complexity:

O(1)

Memory complexity:

O(1)

property max_children: int

Returns maximum number of children in each node.

Time complexity:

O(1)

Memory complexity:

O(1)

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> tree.max_children == 16
True
property segments: Sequence[ground.hints.Segment]

Returns underlying segments.

Time complexity:

O(1)

Memory complexity:

O(1)

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> tree.segments == segments
True
n_nearest_indices(n: int, segment: ground.hints.Segment)Sequence[int][source]

Searches for indices of segments in the tree the nearest to the given segment.

Time complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

where size = len(self.segments), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result indices.

  • segment – input segment.

Returns

indices of segments in the tree the nearest to the input segment.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.n_nearest_indices(2, Segment(Point(0, 0), Point(10, 0)))
...  == [0, 1])
True
>>> (tree.n_nearest_indices(10, Segment(Point(0, 0), Point(10, 0)))
...  == range(len(segments)))
True
n_nearest_items(n: int, segment: ground.hints.Segment)Sequence[Tuple[int, ground.hints.Segment]][source]

Searches for indices with segments in the tree the nearest to the given segment.

Time complexity:

O(n * max_children * log size) if n < size, O(size) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(size) otherwise

where size = len(self.segments), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result indices with segments.

  • segment – input segment.

Returns

indices with segments in the tree the nearest to the input segment.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.n_nearest_items(2, Segment(Point(0, 0), Point(10, 0)))
...  == [(0, Segment(Point(0, 1), Point(1, 1))),
...      (1, Segment(Point(0, 2), Point(2, 2)))])
True
>>> (tree.n_nearest_items(10, Segment(Point(0, 0), Point(10, 0)))
...  == list(enumerate(segments)))
True
n_nearest_segments(n: int, segment: ground.hints.Segment)Sequence[ground.hints.Segment][source]

Searches for segments in the tree the nearest to the given segment.

Time complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

where size = len(self.segments), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result segments.

  • segment – input segment.

Returns

segments in the tree the nearest to the input segment.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.n_nearest_segments(2, Segment(Point(0, 0), Point(10, 0)))
...  == [Segment(Point(0, 1), Point(1, 1)),
...      Segment(Point(0, 2), Point(2, 2))])
True
>>> (tree.n_nearest_segments(10, Segment(Point(0, 0), Point(10, 0)))
...  == segments)
True
n_nearest_to_point_indices(n: int, point: ground.hints.Point)Sequence[int][source]

Searches for indices of segments in the tree the nearest to the given point.

Time complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

where size = len(self.segments), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result indices.

  • point – input point.

Returns

indices of segments in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> tree.n_nearest_to_point_indices(2, Point(0, 0)) == [0, 1]
True
>>> (tree.n_nearest_to_point_indices(10, Point(0, 0))
...  == range(len(segments)))
True
n_nearest_to_point_items(n: int, point: ground.hints.Point)Sequence[Tuple[int, ground.hints.Segment]][source]

Searches for indices with segments in the tree the nearest to the given point.

Time complexity:

O(n * max_children * log size) if n < size, O(size) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(size) otherwise

where size = len(self.segments), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result indices with segments.

  • point – input point.

Returns

indices with segments in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.n_nearest_to_point_items(2, Point(0, 0))
...  == [(0, Segment(Point(0, 1), Point(1, 1))),
...      (1, Segment(Point(0, 2), Point(2, 2)))])
True
>>> (tree.n_nearest_to_point_items(10, Point(0, 0))
...  == list(enumerate(segments)))
True
n_nearest_to_point_segments(n: int, point: ground.hints.Point)Sequence[ground.hints.Segment][source]

Searches for segments in the tree the nearest to the given point.

Time complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

Memory complexity:

O(n * max_children * log size) if n < size, O(1) otherwise

where size = len(self.segments), max_children = self.max_children.

Parameters
  • n – positive upper bound for number of result segments.

  • point – input point.

Returns

segments in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.n_nearest_to_point_segments(2, Point(0, 0))
...  == [Segment(Point(0, 1), Point(1, 1)),
...      Segment(Point(0, 2), Point(2, 2))])
True
>>> tree.n_nearest_to_point_segments(10, Point(0, 0)) == segments
True
nearest_index(segment: ground.hints.Segment)int[source]

Searches for index of segment in the tree the nearest to the given segment.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.segments), max_children = self.max_children.

Parameters

segment – input segment.

Returns

index of segment in the tree the nearest to the input segment.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> tree.nearest_index(Segment(Point(0, 0), Point(10, 0))) == 0
True
nearest_item(segment: ground.hints.Segment)Tuple[int, ground.hints.Segment][source]

Searches for index with segment in the tree the nearest to the given segment.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.segments), max_children = self.max_children.

Parameters

segment – input segment.

Returns

index with segment in the tree the nearest to the input segment.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.nearest_item(Segment(Point(0, 0), Point(10, 0)))
...  == (0, Segment(Point(0, 1), Point(1, 1))))
True
nearest_segment(segment: ground.hints.Segment)ground.hints.Segment[source]

Searches for segment in the tree the nearest to the given segment.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.segments), max_children = self.max_children.

Parameters

segment – input segment.

Returns

segment in the tree the nearest to the input segment.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.nearest_segment(Segment(Point(0, 0), Point(10, 0)))
...  == Segment(Point(0, 1), Point(1, 1)))
True
nearest_to_point_index(point: ground.hints.Point)int[source]

Searches for index of segment in the tree the nearest to the given point.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.segments), max_children = self.max_children.

Parameters

point – input point.

Returns

index of segment in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> tree.nearest_to_point_index(Point(0, 0)) == 0
True
nearest_to_point_item(point: ground.hints.Point)Tuple[int, ground.hints.Segment][source]

Searches for index with segment in the tree the nearest to the given point.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.segments), max_children = self.max_children.

Parameters

point – input point.

Returns

index with segment in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.nearest_to_point_item(Point(0, 0))
...  == (0, Segment(Point(0, 1), Point(1, 1))))
True
nearest_to_point_segment(point: ground.hints.Point)ground.hints.Segment[source]

Searches for segment in the tree the nearest to the given point.

Time complexity:

O(max_children * log size)

Memory complexity:

O(max_children * log size)

where size = len(self.segments), max_children = self.max_children.

Parameters

point – input point.

Returns

segment in the tree the nearest to the input point.

>>> from ground.base import get_context
>>> context = get_context()
>>> Point, Segment = context.point_cls, context.segment_cls
>>> segments = [Segment(Point(0, index), Point(index, index))
...             for index in range(1, 11)]
>>> tree = Tree(segments)
>>> (tree.nearest_to_point_segment(Point(0, 0))
...  == Segment(Point(0, 1), Point(1, 1)))
True