Nearest Neighbors

This module provides nearest-neighbor backends used during roadmap growth. The backend is selected by solver infrastructure and can be swapped without changing solver logic.

Typical usage

from discopygal.solvers_infra.nearest_neighbors import NearestNeighbors_sklearn

nn = NearestNeighbors_sklearn()
nn.fit(points)
nearest = nn.k_nearest(sample, k=10)

See also

class discopygal.solvers_infra.nearest_neighbors.NearestNeighbors(metric: Metric)

Abstract class represeting the interface a nearest neighbors algorithm should comply.

Parameters:

metric (Metric) – metric to compute nearest neighbors

fit(points: list[Point_2 | Point_d])

Get a list of points (in CGAL Point_2 or Point_d format) and fit some kind of data structure on them.

Parameters:

points (list<Point_2> or list<Point_d>) – list of points

get_points() → list[Point_2]

Return the list of inner points

Returns:

list of points

Return type:

list<Point_2> or list<Point_d>

k_nearest(point: list[Point_2 | Point_d], k: int) → list[Point_2 | Point_d]

Given a point, return the k-nearest neighbors to that point.

Parameters:

  • point (Point_2 or Point_d) – query point

  • k (int) – number of neighbors to return (k)

Returns:

k nearest neighbors

Return type:

list<Point_2> or list<Point_d>

nearest_in_radius(point: list[Point_2 | Point_d], radius: FT) → list[Point_2 | Point_d]

Given a point and a radius, return all the neighbors that have distance <= radius

Parameters:

  • point (Point_2 or Point_d) – query point

  • radius (FT) – radius of neighborhood

Returns:

nearest neighbors in radius

Return type:

list<Point_2> or list<Point_d>

class discopygal.solvers_infra.nearest_neighbors.NearestNeighborsCached(nn: NearestNeighbors, max_cache: int = 100)

Wrapper for a nearest neighbor object that also uses cache, and allows for insertion of points in real time. This allows adding points lazily, and only when cache is full then rebuilding the underlying data structure.

Example:
>>> nn = NearestNeighborsCached(NearestNeighbors_sklearn(metric=Metric_Euclidean))
>>> nn.add_point(Point_d(8, [...]))
Parameters:

  • nn (NearestNeighbors) – nearest neigbors object to wrap

  • max_cache – maximum cache size

add_point(point: list[Point_2 | Point_d])

Add a point to the nearest neighbor search

Parameters:

point (Point_2 or Point_d) – point to add

fit(points: list[Point_2 | Point_d])

Get a list of points (in CGAL Point_2 or Point_d format) and fit some kind of data structure on them.

Parameters:

points (list<Point_2> or list<Point_d>) – list of points

get_points()

Return the list of inner points

Returns:

list of points

Return type:

list<Point_2> or list<Point_d>

k_nearest(point: list[Point_2 | Point_d], k: int) → list[Point_2 | Point_d]

Given a point, return the k-nearest neighbors to that point.

Parameters:

  • point (Point_2 or Point_d) – query point

  • k (int) – number of neighbors to return (k)

Returns:

k nearest neighbors

Return type:

list<Point_2> or list<Point_d>

nearest_in_radius(point: list[Point_2 | Point_d], radius: FT) → list[Point_2 | Point_d]

Given a point and a radius, return all the neighbors that have distance <= radius

Parameters:

  • point (Point_2 or Point_d) – query point

  • radius (FT) – radius of neighborhood

Returns:

nearest neighbors in radius

Return type:

list<Point_2> or list<Point_d>

class discopygal.solvers_infra.nearest_neighbors.NearestNeighbors_CGAL(metric: ~discopygal.solvers_infra.metrics.Metric = <class 'discopygal.solvers_infra.metrics.Metric_Euclidean'>)

CGAL implementation of nearest neighbors

Parameters:

metric (Metric) – metric to compute nearest neighbors

fit(points: list[Point_2 | Point_d])

Get a list of points (in CGAL Point_2 or Point_d format) and fit some kind of data structure on them.

Parameters:

points (list<Point_2> or list<Point_d>) – list of points

k_nearest(point: Point_2 | Point_d, k: int)

Given a point, return the k-nearest neighbors to that point.

Parameters:

  • point (Point_2 or Point_d) – query point

  • k (int) – number of neighbors to return (k)

Returns:

k nearest neighbors

Return type:

list<Point_2> or list<Point_d>

nearest_in_radius(point: Point_2, radius: FT) → Point_2

Given a point and a radius, return all the neighbors that have distance <= radius

Parameters:

  • point (Point_2) – query point

  • radius (FT) – radius of neighborhood

Returns:

nearest neighbors in radius

Return type:

list<Point_2>

class discopygal.solvers_infra.nearest_neighbors.NearestNeighbors_sklearn(metric: ~discopygal.solvers_infra.metrics.Metric = <class 'discopygal.solvers_infra.metrics.Metric_Euclidean'>)

Sklearn implementation of nearest neighbors

Parameters:

metric (Metric) – metric to compute nearest neighbors

fit(points)

Get a list of points (in CGAL Point_2 or Point_d format) and fit some kind of data structure on them.

Parameters:

points (list<Point_2> or list<Point_d>) – list of points

k_nearest(point: Point_2 | Point_d, k: int)

Given a point, return the k-nearest neighbors to that point.

Parameters:

  • point (Point_2 or Point_d) – query point

  • k (int) – number of neighbors to return (k)

Returns:

k nearest neighbors

Return type:

list<Point_2> or list<Point_d>

nearest_in_radius(point: Point_2, radius: FT) → Point_2

Given a point and a radius, return all the neighbors that have distance <= radius

Parameters:

  • point (Point_2) – query point

  • radius (FT) – radius of neighborhood

Returns:

nearest neighbors in radius

Return type:

list<Point_2>

class discopygal.solvers_infra.nearest_neighbors.NeighborsFinder
fit(points)

Get a list of points (in CGAL Point_2 or Point_d format) and fit some kind of data structure on them.

Parameters:

points (list<Point_2> or list<Point_d>) – list of points