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[Point[ScalarT]], /, *, context: Context[ScalarT])[source]

Represents k-dimensional (aka kd) tree.

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

__init__(points: Sequence[Point[ScalarT]], /, *, context: Context[ScalarT]) → 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).

__repr__() → str: Return repr(self).

property context: Context[ScalarT]

Returns context of the tree.

Time complexity:: O(1)
Memory complexity:: O(1)

property points: Sequence[Point[ScalarT]]

Returns underlying points.

Time complexity:: O(1)
Memory complexity:: O(1)

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> tree.points == points
True

n_nearest_indices(n: int, point: Point[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> 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: Point[ScalarT], /) → Sequence[Point[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> (
...     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: Point[ScalarT], /) → Sequence[tuple[int, Point[ScalarT]]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> (
...     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: Point[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> tree.nearest_index(Point(0, 0)) == 2
True
>>> tree.nearest_index(Point(-3, 2)) == 2
True

nearest_point(point: Point[ScalarT], /) → Point[ScalarT][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> tree.nearest_point(Point(0, 0)) == Point(-3, 2)
True
>>> tree.nearest_point(Point(-3, 2)) == Point(-3, 2)
True

nearest_item(point: Point[ScalarT], /) → tuple[int, Point[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Point = context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> 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: Box[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> 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: Box[ScalarT], /) → list[Point[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> 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: Box[ScalarT], /) → list[tuple[int, Point[ScalarT]]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> points = list(map(Point, range(-5, 6), range(10)))
>>> tree = Tree(points, context=context)
>>> 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

__subclasshook__()

Abstract classes can override this to customize issubclass().

This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).

r module

class locus.r.Tree(boxes: Sequence[Box[ScalarT]], /, *, context: Context[ScalarT], max_children: int = 16)[source]

Represents packed 2-dimensional Hilbert R-tree.

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

__init__(boxes: Sequence[Box[ScalarT]], /, *, context: Context[ScalarT], max_children: int = 16) → None[source]

Initializes tree from boxes.

Time complexity:: O(size * log size)
Memory complexity:: O(size)

where size = len(boxes).

__repr__() → str: Return repr(self).

property boxes: Sequence[Box[ScalarT]]

Returns underlying boxes.

Time complexity:: O(1)
Memory complexity:: O(1)

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> tree.boxes == boxes
True

property context: Context[ScalarT]

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)

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> tree.max_children == 16
True

find_subsets(box: Box[ScalarT], /) → list[Box[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> 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: Box[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> 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: Box[ScalarT], /) → list[tuple[int, Box[ScalarT]]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> (
...     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: Box[ScalarT], /) → list[Box[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> 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: Box[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> 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: Box[ScalarT], /) → list[tuple[int, Box[ScalarT]]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box = context.box_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> (
...     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: Point[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> 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: Point[ScalarT], /) → Sequence[Box[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> (
...     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: Point[ScalarT], /) → Sequence[tuple[int, Box[ScalarT]]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> (
...     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: Point[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> tree.nearest_index(Point(0, 0)) == 9
True

nearest_box(point: Point[ScalarT], /) → Box[ScalarT][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> tree.nearest_box(Point(0, 0)) == Box(-10, 10, 0, 10)
True

nearest_item(point: Point[ScalarT], /) → tuple[int, Box[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> Box, Point = context.box_cls, context.point_cls
>>> boxes = [Box(-index, index, 0, index) for index in range(1, 11)]
>>> tree = Tree(boxes, context=context)
>>> 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

__subclasshook__()

Abstract classes can override this to customize issubclass().

This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).

segmental module

class locus.segmental.Tree(segments: Sequence[Segment[ScalarT]], /, *, context: Context[ScalarT], max_children: int = 16)[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[Segment[ScalarT]], /, *, context: Context[ScalarT], max_children: int = 16) → None[source]

Initializes tree from segments.

Time complexity:: O(size * log size)
Memory complexity:: O(size)

where size = len(segments).

__repr__() → str: Return repr(self).

property context: Context[ScalarT]

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)

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> tree.max_children == 16
True

property segments: Sequence[Segment[ScalarT]]

Returns underlying segments.

Time complexity:: O(1)
Memory complexity:: O(1)

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> tree.segments == segments
True

n_nearest_indices(n: int, segment: Segment[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     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: Segment[ScalarT], /) → Sequence[tuple[int, Segment[ScalarT]]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     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: Segment[ScalarT], /) → Sequence[Segment[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     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: Point[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> 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: Point[ScalarT], /) → Sequence[tuple[int, Segment[ScalarT]]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     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: Point[ScalarT], /) → Sequence[Segment[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     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: Segment[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> tree.nearest_index(Segment(Point(0, 0), Point(10, 0))) == 0
True

nearest_item(segment: Segment[ScalarT], /) → tuple[int, Segment[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     tree.nearest_item(Segment(Point(0, 0), Point(10, 0)))
...     == (0, Segment(Point(0, 1), Point(1, 1)))
... )
True

nearest_segment(segment: Segment[ScalarT], /) → Segment[ScalarT][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     tree.nearest_segment(Segment(Point(0, 0), Point(10, 0)))
...     == Segment(Point(0, 1), Point(1, 1))
... )
True

nearest_to_point_index(point: Point[ScalarT], /) → 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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> tree.nearest_to_point_index(Point(0, 0)) == 0
True

nearest_to_point_item(point: Point[ScalarT], /) → tuple[int, Segment[ScalarT]][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     tree.nearest_to_point_item(Point(0, 0))
...     == (0, Segment(Point(0, 1), Point(1, 1)))
... )
True

nearest_to_point_segment(point: Point[ScalarT], /) → Segment[ScalarT][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.

>>> import math
>>> from fractions import Fraction
>>> from ground.context import Context
>>> context = Context(coordinate_factory=Fraction, sqrt=math.sqrt)
>>> 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, context=context)
>>> (
...     tree.nearest_to_point_segment(Point(0, 0))
...     == Segment(Point(0, 1), Point(1, 1))
... )
True

__subclasshook__()

Abstract classes can override this to customize issubclass().

This is invoked early on by abc.ABCMeta.__subclasscheck__(). It should return True, False or NotImplemented. If it returns NotImplemented, the normal algorithm is used. Otherwise, it overrides the normal algorithm (and the outcome is cached).