Coverage for trimesh/interval.py: 97%

1""" 

2interval.py 

3-------------- 

4 

5Deal with 1D intervals which are defined by: 

6 [start position, end position] 

7""" 

8 

9import numpy as np 

10 

11from .typed import ArrayLike, NDArray, float64 

12 

13 

14def intersection(a: ArrayLike, b: NDArray[float64]) -> NDArray[float64]: 

15 """ 

16 Given pairs of ranges merge them in to 

17 one range if they overlap. 

18 

19 Parameters 

20 -------------- 

21 a : (2, ) or (n, 2) 

22 Start and end of a 1D interval 

23 b : (2, ) float 

24 Start and end of a 1D interval 

25 

26 Returns 

27 -------------- 

28 inter : (2, ) or (2, 2) float 

29 The unioned range from the two inputs, 

30 if not np.ptp(`inter, axis=1)` will be zero. 

31 """ 

32 a = np.array(a, dtype=np.float64) 

33 b = np.array(b, dtype=np.float64) 

34 

35 # convert to vectorized form 

36 is_1D = a.shape == (2,) 

37 a = a.reshape((-1, 2)) 

38 b = b.reshape((-1, 2)) 

39 

40 # make sure they're min-max 

41 a.sort(axis=1) 

42 b.sort(axis=1) 

43 a_low, a_high = a.T 

44 b_low, b_high = b.T 

45 

46 # do the checks 

47 check = np.logical_not(np.logical_or(b_low >= a_high, a_low >= b_high)) 

48 overlap = np.zeros(a.shape, dtype=np.float64) 

49 overlap[check] = np.column_stack( 

50 ( 

51 np.array([a_low[check], b_low[check]]).max(axis=0), 

52 np.array([a_high[check], b_high[check]]).min(axis=0), 

53 ) 

54 ) 

55 

56 if is_1D: 

57 return overlap[0] 

58 

59 return overlap 

60 

61 

62def union(intervals: ArrayLike, sort: bool = True) -> NDArray[float64]: 

63 """ 

64 For array of multiple intervals union them all into 

65 the subset of intervals. 

66 

67 For example: 

68 `intervals = [[1,2], [2,3]] -> [[1, 3]]` 

69 `intervals = [[1,2], [2.5,3]] -> [[1, 2], [2.5, 3]]` 

70 

71 

72 Parameters 

73 ------------ 

74 intervals : (n, 2) 

75 Pairs of `(min, max)` values. 

76 sort 

77 If the array is already ordered into (min, max) pairs 

78 and then pairs sorted by minimum value you can skip the 

79 sorting in this function. 

80 

81 Returns 

82 ---------- 

83 unioned : (m, 2) 

84 New intervals where `m <= n` 

85 """ 

86 if len(intervals) == 0: 

87 return np.zeros(0) 

88 

89 # if the intervals have not been pre-sorted we should apply our sorting logic 

90 # you would only skip this if you are subsetting a larger list elsewhere. 

91 if sort: 

92 # copy inputs and make sure they are (min, max) pairs 

93 intervals = np.sort(intervals, axis=1) 

94 # order them by lowest starting point 

95 intervals = intervals[intervals[:, 0].argsort()] 

96 

97 # we know we will have at least one interval 

98 unions = [intervals[0].tolist()] 

99 

100 for begin, end in intervals[1:]: 

101 if unions[-1][1] >= begin: 

102 unions[-1][1] = max(unions[-1][1], end) 

103 else: 

104 unions.append([begin, end]) 

105 

106 return np.array(unions)