Coverage for trimesh/path/repair.py: 100%

1""" 

2repair.py 

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

4 

5Try to fix problems with closed regions. 

6""" 

7 

8import numpy as np 

9from scipy.spatial import cKDTree 

10 

11from .. import util 

12from . import segments 

13 

14 

15def fill_gaps(path, distance=0.025): 

16 """ 

17 Find vertices without degree 2 and try to connect to 

18 other vertices. Operations are done in-place. 

19 

20 Parameters 

21 ------------ 

22 segments : trimesh.path.Path2D 

23 Line segments defined by start and end points 

24 """ 

25 

26 # find any vertex without degree 2 (connected to two things) 

27 broken = np.array([k for k, d in dict(path.vertex_graph.degree()).items() if d != 2]) 

28 

29 # if all vertices have correct connectivity, exit 

30 if len(broken) == 0: 

31 return 

32 

33 # first find broken vertices with distance 

34 tree = cKDTree(path.vertices[broken]) 

35 pairs = tree.query_pairs(r=distance, output_type="ndarray") 

36 

37 connect_seg = [] 

38 if len(pairs) > 0: 

39 end_points = {tuple(sorted(e.end_points)) for e in path.entities} 

40 pair_set = {tuple(i) for i in np.sort(broken[pairs], axis=1)} 

41 

42 # we don't want to connect entities to themselves so do a set 

43 # difference 

44 mask = np.array(list(pair_set.difference(end_points))) 

45 

46 if len(mask) > 0: 

47 connect_seg = path.vertices[mask] 

48 

49 # a set of values we can query intersections with quickly 

50 broken_set = set(broken) 

51 # query end points set vs path.dangling to avoid having 

52 # to compute every single path and discrete curve 

53 dangle = [ 

54 i 

55 for i, e in enumerate(path.entities) 

56 if len(broken_set.intersection(e.end_points)) > 0 

57 ] 

58 

59 segs = [] 

60 # mask for which entities to keep 

61 keep = np.ones(len(path.entities), dtype=bool) 

62 # save a reference to the line class to avoid circular import 

63 line_class = None 

64 

65 for entity_index in dangle: 

66 # only consider line entities 

67 if path.entities[entity_index].__class__.__name__ != "Line": 

68 continue 

69 

70 if line_class is None: 

71 line_class = path.entities[entity_index].__class__ 

72 

73 # get discrete version of entity 

74 points = path.entities[entity_index].discrete(path.vertices) 

75 # turn connected curve into segments 

76 seg_idx = util.stack_lines(np.arange(len(points))) 

77 # append the segments to our collection 

78 segs.append(points[seg_idx]) 

79 # remove this entity and replace with segments 

80 keep[entity_index] = False 

81 

82 # combine segments with connection segments 

83 all_segs = util.vstack_empty((util.vstack_empty(segs), connect_seg)) 

84 

85 # go home early 

86 if len(all_segs) == 0: 

87 return 

88 

89 # split segments at broken vertices so topology can happen 

90 split = segments.split(all_segs, path.vertices[broken]) 

91 # merge duplicate segments 

92 final_seg = segments.unique(split) 

93 

94 # add line segments in as line entities 

95 entities = [] 

96 for i in range(len(final_seg)): 

97 entities.append(line_class(points=np.arange(2) + (i * 2) + len(path.vertices))) 

98 

99 # replace entities with new entities 

100 path.entities = np.append(path.entities[keep], entities) 

101 path.vertices = np.vstack((path.vertices, np.vstack(final_seg))) 

102 path._cache.clear() 

103 path.process()