Coverage for src/meshpy/geometric_search/scipy.py: 91%

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. 

22"""This file defines the interface to the Scipy spatial geometric search 

23functionality.""" 

24 

25from scipy.spatial import KDTree as _KDTree 

26 

27 

28def pairs_to_partner_list(pairs, n_points): 

29 """Convert the pairs to a partner list.""" 

30 

31 # Sort the pairs by the first column 

32 pairs = pairs[pairs[:, 0].argsort()] 

33 

34 n_partners = 0 

35 partner_index_list = [-1 for i in range(n_points)] 

36 for pair in pairs: 

37 pair_partners = [partner_index_list[pair[i]] for i in range(2)] 

38 if pair_partners[0] == -1 and pair_partners[1] == -1: 

39 # We have a new partner index 

40 for i in range(2): 

41 partner_index_list[pair[i]] = n_partners 

42 n_partners += 1 

43 elif pair_partners[0] == -1: 

44 partner_index_list[pair[0]] = pair_partners[1] 

45 elif pair_partners[1] == -1: 

46 partner_index_list[pair[1]] = pair_partners[0] 

47 else: 

48 # Both points already have a partner index. Since we order 

49 # the pairs this one has to be equal to each other or we 

50 # have multiple clusters. 

51 if not pair_partners[0] == pair_partners[1]: 

52 raise ValueError( 

53 "Two points are connected to different partner indices." 

54 ) 

55 return partner_index_list, n_partners 

56 

57 

58def find_close_points_scipy(point_coordinates, tol): 

59 """Call the Scipy implementation of find close_points.""" 

60 

61 kd_tree = _KDTree(point_coordinates) 

62 pairs = kd_tree.query_pairs(r=tol, output_type="ndarray") 

63 return pairs_to_partner_list(pairs, len(point_coordinates))