Coverage for src/meshpy/geometric_search/__init__.py: 100%

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"""