meshpy.geometric_search

 1# The MIT License (MIT)
 2#
 3# Copyright (c) 2018-2025 MeshPy Authors
 4#
 5# Permission is hereby granted, free of charge, to any person obtaining a copy
 6# of this software and associated documentation files (the "Software"), to deal
 7# in the Software without restriction, including without limitation the rights
 8# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 9# copies of the Software, and to permit persons to whom the Software is
10# furnished to do so, subject to the following conditions:
11#
12# The above copyright notice and this permission notice shall be included in
13# all copies or substantial portions of the Software.
14#
15# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21# THE SOFTWARE.
22r"""This module defines geometric search functionality.
23
24This module contains functionality to find points close to each other in
25a point cloud. Currently, three different implementations for the actual
26search algorithm are available (depending on your installation/setup):
27
28- `brute_force_cython`: A brute force algorithm implemented in Cython,
29  scales with $\mathcal{O}(n^2)$, but for a small number of points
30  ($n<200$) this is the fastest algorithm since compared to the others
31  it does not have any setup costs.
32
33- `kd_tree_scipy`: Uses a
34  [bounding volume hierarchy (BVH)](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy)
35  implementation provided by
36  [scipy](https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.KDTree.html).
37  This scales with $\mathcal{O}(n\ \log{n})$.
38
39- `boundary_volume_hierarchy_arborx` : Uses a
40  [bounding volume hierarchy (BVH)](https://en.wikipedia.org/wiki/Bounding_volume_hierarchy)
41  implementation provided by [ArborX](https://github.com/arborx/ArborX).
42  This also scales with $\mathcal{O}(n\ \log{n})$
43  but due to a more optimised implementation is a few times faster
44  than the scipy implementation.
45
46The `find_close_points` function automatically chooses the fastest
47(available) implementation for the given point array.
48
49Consult the `README.md` regarding install and testing options for
50different implementations.
51"""