Coverage for src/abm_shape_collection/extract_voxel_contours.py: 100%

1import numpy as np 

2 

3 

4def extract_voxel_contours( 

5 all_voxels: list[tuple[int, int, int]], 

6 projection: str, 

7 box: tuple[int, int, int], 

8) -> list[list[tuple[int, int]]]: 

9 """ 

10 Extract contours from list of voxels in specified projection direction. 

11 

12 Parameters 

13 ---------- 

14 all_voxels 

15 List of all voxels in region. 

16 projection 

17 Projection direction. 

18 box 

19 Bounding box. 

20 

21 Returns 

22 ------- 

23 : 

24 List of list of contour points. 

25 """ 

26 

27 voxels = set() 

28 length, width, height = box 

29 

30 if projection == "top": 

31 voxels.update({(x, y) for x, y, _ in all_voxels}) 

32 x_bounds = length 

33 y_bounds = width 

34 elif projection == "side1": 

35 voxels.update({(x, z) for x, _, z in all_voxels}) 

36 x_bounds = length 

37 y_bounds = height 

38 else: 

39 voxels.update({(y, z) for _, y, z in all_voxels}) 

40 x_bounds = width 

41 y_bounds = height 

42 

43 array = np.full((x_bounds, y_bounds), fill_value=False) 

44 array[tuple(np.transpose(list(voxels)))] = True 

45 

46 edges = get_array_edges(array) 

47 contours = connect_array_edges(edges) 

48 

49 return [merge_contour_edges(contour) for contour in contours] 

50 

51 

52def get_array_edges(array: np.ndarray) -> list[list[tuple[int, int]]]: 

53 """ 

54 Get edges of region in binary array. 

55 

56 Parameters 

57 ---------- 

58 array 

59 Binary array. 

60 

61 Returns 

62 ------- 

63 : 

64 List of unconnected region edges. 

65 """ 

66 

67 edges = [] 

68 x, y = np.nonzero(array) 

69 

70 for i, j in zip(x.tolist(), y.tolist()): 

71 if j == array.shape[1] - 1 or not array[i, j + 1]: 

72 edges.append([(i, j + 1), (i + 1, j + 1)]) 

73 

74 if i == array.shape[0] - 1 or not array[i + 1, j]: 

75 edges.append([(i + 1, j), (i + 1, j + 1)]) 

76 

77 if j == 0 or not array[i, j - 1]: 

78 edges.append([(i, j), (i + 1, j)]) 

79 

80 if i == 0 or not array[i - 1, j]: 

81 edges.append([(i, j), (i, j + 1)]) 

82 

83 return edges 

84 

85 

86def connect_array_edges(edges: list[list[tuple[int, int]]]) -> list[list[tuple[int, int]]]: 

87 """ 

88 Group unconnected region edges into connected contour edges. 

89 

90 Parameters 

91 ---------- 

92 edges 

93 List of unconnected region edges. 

94 

95 Returns 

96 ------- 

97 : 

98 List of connected contour edges. 

99 """ 

100 

101 contours: list[list[tuple[int, int]]] = [] 

102 

103 while edges: 

104 contour = edges[0] 

105 contour_length = 0 

106 edges.remove(contour) 

107 

108 while contour_length != len(contour): 

109 contour_length = len(contour) 

110 

111 forward = list(filter(lambda edge: contour[-1] == edge[0], edges)) 

112 

113 if len(forward) > 0: 

114 edges.remove(forward[0]) 

115 contour.extend(forward[0][1:]) 

116 

117 backward = list(filter(lambda edge: contour[-1] == edge[-1], edges)) 

118 

119 if len(backward) > 0: 

120 edges.remove(backward[0]) 

121 contour.extend(list(reversed(backward[0]))[1:]) 

122 

123 if contour_length == len(contour): 

124 contours.append(list(contour)) 

125 

126 return sorted(contours, key=len) 

127 

128 

129def merge_contour_edges(contour: list[tuple[int, int]]) -> list[tuple[int, int]]: 

130 """ 

131 Merge connected contour edges. 

132 

133 Parameters 

134 ---------- 

135 contour 

136 List of connected contour edges. 

137 

138 Returns 

139 ------- 

140 : 

141 List of connected contours. 

142 """ 

143 

144 merged = contour.copy() 

145 

146 for (x0, y0), (x1, y1), (x2, y2) in zip(contour, contour[1:], contour[2:]): 

147 area = x0 * (y1 - y2) + x1 * (y2 - y0) + x2 * (y0 - y1) 

148 if area == 0: 

149 merged.remove((x1, y1)) 

150 

151 return merged