Coverage for /usr/lib/python3/dist-packages/matplotlib/tri/trifinder.py: 42%

1import numpy as np 

2 

3from matplotlib import _api 

4from matplotlib.tri import Triangulation 

5 

6 

7class TriFinder: 

8 """ 

9 Abstract base class for classes used to find the triangles of a 

10 Triangulation in which (x, y) points lie. 

11 

12 Rather than instantiate an object of a class derived from TriFinder, it is 

13 usually better to use the function `.Triangulation.get_trifinder`. 

14 

15 Derived classes implement __call__(x, y) where x and y are array-like point 

16 coordinates of the same shape. 

17 """ 

18 

19 def __init__(self, triangulation): 

20 _api.check_isinstance(Triangulation, triangulation=triangulation) 

21 self._triangulation = triangulation 

22 

23 

24class TrapezoidMapTriFinder(TriFinder): 

25 """ 

26 `~matplotlib.tri.TriFinder` class implemented using the trapezoid 

27 map algorithm from the book "Computational Geometry, Algorithms and 

28 Applications", second edition, by M. de Berg, M. van Kreveld, M. Overmars 

29 and O. Schwarzkopf. 

30 

31 The triangulation must be valid, i.e. it must not have duplicate points, 

32 triangles formed from colinear points, or overlapping triangles. The 

33 algorithm has some tolerance to triangles formed from colinear points, but 

34 this should not be relied upon. 

35 """ 

36 

37 def __init__(self, triangulation): 

38 from matplotlib import _tri 

39 super().__init__(triangulation) 

40 self._cpp_trifinder = _tri.TrapezoidMapTriFinder( 

41 triangulation.get_cpp_triangulation()) 

42 self._initialize() 

43 

44 def __call__(self, x, y): 

45 """ 

46 Return an array containing the indices of the triangles in which the 

47 specified *x*, *y* points lie, or -1 for points that do not lie within 

48 a triangle. 

49 

50 *x*, *y* are array-like x and y coordinates of the same shape and any 

51 number of dimensions. 

52 

53 Returns integer array with the same shape and *x* and *y*. 

54 """ 

55 x = np.asarray(x, dtype=np.float64) 

56 y = np.asarray(y, dtype=np.float64) 

57 if x.shape != y.shape: 

58 raise ValueError("x and y must be array-like with the same shape") 

59 

60 # C++ does the heavy lifting, and expects 1D arrays. 

61 indices = (self._cpp_trifinder.find_many(x.ravel(), y.ravel()) 

62 .reshape(x.shape)) 

63 return indices 

64 

65 def _get_tree_stats(self): 

66 """ 

67 Return a python list containing the statistics about the node tree: 

68 0: number of nodes (tree size) 

69 1: number of unique nodes 

70 2: number of trapezoids (tree leaf nodes) 

71 3: number of unique trapezoids 

72 4: maximum parent count (max number of times a node is repeated in 

73 tree) 

74 5: maximum depth of tree (one more than the maximum number of 

75 comparisons needed to search through the tree) 

76 6: mean of all trapezoid depths (one more than the average number 

77 of comparisons needed to search through the tree) 

78 """ 

79 return self._cpp_trifinder.get_tree_stats() 

80 

81 def _initialize(self): 

82 """ 

83 Initialize the underlying C++ object. Can be called multiple times if, 

84 for example, the triangulation is modified. 

85 """ 

86 self._cpp_trifinder.initialize() 

87 

88 def _print_tree(self): 

89 """ 

90 Print a text representation of the node tree, which is useful for 

91 debugging purposes. 

92 """ 

93 self._cpp_trifinder.print_tree()