Coverage for tests/pex25d/geometry_test.py: 100%

1# 

2# -------------------------------------------------------------------------------- 

3# SPDX-FileCopyrightText: 2024-2026 Martin Jan Köhler and Harald Pretl 

4# Johannes Kepler University, Institute for Integrated Circuits. 

5# 

6# This file is part of KPEX  

7# (see https://github.com/iic-jku/klayout-pex). 

8# 

9# This program is free software: you can redistribute it and/or modify 

10# it under the terms of the GNU General Public License as published by 

11# the Free Software Foundation, either version 3 of the License, or 

12# (at your option) any later version. 

13# 

14# This program is distributed in the hope that it will be useful, 

15# but WITHOUT ANY WARRANTY; without even the implied warranty of 

16# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 

17# GNU General Public License for more details. 

18# 

19# You should have received a copy of the GNU General Public License 

20# along with this program. If not, see <http://www.gnu.org/licenses/>. 

21# SPDX-License-Identifier: GPL-3.0-or-later 

22# -------------------------------------------------------------------------------- 

23# 

24 

25""" 

26The integer geometry the validator's ``--strict`` tier is built on. 

27 

28Several cases here came out of a differential fuzz against shapely rather than 

29out of inspection; where that is so, the test says which shape defeated which 

30attempt. shapely is deliberately not a dependency — the point of this package 

31is that it needs protobuf and nothing else — so the cases it found are frozen 

32here as fixed tests. 

33""" 

34 

35from __future__ import annotations 

36 

37import allure 

38import unittest 

39 

40from klayout_pex.pex25d.validator import ( 

41 Polygon, polygons_overlap, ring_is_collinear, ring_is_simple, 

42 ring_strictly_inside, rings_meet, 

43) 

44 

45UNIT = [(0, 0), (2, 0), (2, 2), (0, 2)] 

46L_SHAPE = [(0, 0), (4, 0), (4, 1), (1, 1), (1, 4), (0, 4)] 

47 

48 

49def square(x: int, y: int, size: int) -> list: 

50 return [(x, y), (x + size, y), (x + size, y + size), (x, y + size)] 

51 

52 

53@allure.parent_suite("Unit Tests") 

54@allure.tag("PEX25D", "Geometry") 

55class Pex25DGeometryTest(unittest.TestCase): 

56 # ------------------------------------------------------------- one ring 

57 

58 def test_ring_is_simple(self): 

59 assert ring_is_simple(UNIT) 

60 assert ring_is_simple(L_SHAPE) 

61 assert ring_is_simple([(0, 0), (4, 0), (2, 3)]) 

62 

63 def test_a_bowtie_is_not_simple(self): 

64 assert not ring_is_simple([(0, 0), (2, 2), (2, 0), (0, 2)]) 

65 assert not ring_is_simple([(0, 0), (4, 4), (4, 0), (0, 3)]) 

66 

67 def test_a_fold_back_is_not_simple(self): 

68 # Consecutive edges may share their endpoint but not run along it. 

69 assert not ring_is_simple([(0, 0), (4, 0), (2, 0), (2, 3)]) 

70 

71 def test_ring_is_collinear(self): 

72 assert ring_is_collinear([(0, 0), (1, 0), (3, 0), (2, 0)]) 

73 assert ring_is_collinear([(0, 0), (1, 1), (2, 2)]) 

74 assert not ring_is_collinear(UNIT) 

75 

76 def test_winding_does_not_matter(self): 

77 assert ring_is_simple(UNIT[::-1]) 

78 assert ring_strictly_inside(square(1, 1, 2), square(0, 0, 8)[::-1]) 

79 

80 # --------------------------------------------------------- ring against ring 

81 

82 def test_ring_strictly_inside(self): 

83 outer = square(0, 0, 8) 

84 assert ring_strictly_inside(square(2, 2, 4), outer) 

85 assert not ring_strictly_inside(square(9, 9, 2), outer) # outside 

86 assert not ring_strictly_inside(square(0, 1, 2), outer) # touching 

87 assert not ring_strictly_inside(square(-1, -1, 10), outer) # containing 

88 

89 def test_a_hole_that_leaves_a_concave_outer_and_comes_back(self): 

90 # Every vertex inside is not enough: this one's vertices are all in the 

91 # L, but the edge between two of them crosses the notch. 

92 assert not ring_strictly_inside([(0, 0), (3, 0), (3, 3), (0, 3)], L_SHAPE) 

93 

94 def test_rings_meet(self): 

95 assert rings_meet(square(0, 0, 4), square(2, 2, 4)) # crossing 

96 assert rings_meet(square(0, 0, 4), square(4, 0, 4)) # touching 

97 assert rings_meet(square(0, 0, 8), square(2, 2, 2)) # nested 

98 assert not rings_meet(square(0, 0, 4), square(5, 5, 2)) 

99 

100 # ------------------------------------------------------------- overlap 

101 

102 def test_overlapping_and_disjoint_boxes(self): 

103 assert polygons_overlap(Polygon(square(0, 0, 4)), Polygon(square(2, 2, 4))) 

104 assert not polygons_overlap(Polygon(square(0, 0, 4)), Polygon(square(9, 9, 4))) 

105 

106 def test_touching_is_not_overlapping(self): 

107 assert not polygons_overlap(Polygon(square(0, 0, 4)), Polygon(square(4, 0, 4))) 

108 assert not polygons_overlap(Polygon(square(0, 0, 4)), Polygon(square(4, 4, 4))) 

109 

110 def test_containment_counts(self): 

111 assert polygons_overlap(Polygon(square(0, 0, 8)), Polygon(square(2, 2, 2))) 

112 

113 def test_identical_polygons_overlap(self): 

114 # Every vertex and every edge midpoint of each lies exactly ON the 

115 # other, so no sampled point is ever strictly inside. This is what the 

116 # vertical decomposition is for. 

117 assert polygons_overlap(Polygon(square(0, 0, 4)), Polygon(square(0, 0, 4))) 

118 assert polygons_overlap( 

119 Polygon(square(0, 0, 8), [square(2, 2, 4)]), 

120 Polygon(square(0, 0, 8), [square(2, 2, 4)])) 

121 

122 def test_a_hole_is_not_part_of_the_polygon(self): 

123 donut = Polygon(square(0, 0, 8), [square(2, 2, 4)]) 

124 assert not polygons_overlap(donut, Polygon(square(3, 3, 2))) 

125 assert polygons_overlap(donut, Polygon(square(1, 3, 4))) 

126 

127 def test_a_shape_filling_a_hole_exactly(self): 

128 donut = Polygon(square(0, 0, 8), [square(2, 2, 4)]) 

129 assert not polygons_overlap(donut, Polygon(square(2, 2, 4))) 

130 

131 def test_coincident_boundary_with_material_beyond_it(self): 

132 # From the shapely fuzz. The right-hand strip of the box is outside the 

133 # donut's hole and inside its material, but the two outlines share the 

134 # whole lower edge and both upper corners, so vertex-and-midpoint 

135 # sampling reported no overlap here. 

136 donut = Polygon([(2, 0), (10, 0), (10, 8), (2, 8)], 

137 [[(6, 2), (9, 2), (9, 5), (6, 5)]]) 

138 assert polygons_overlap(donut, Polygon([(7, 2), (10, 2), (10, 5), (7, 5)])) 

139 

140 def test_an_l_shape_and_its_notch(self): 

141 assert not polygons_overlap(Polygon(L_SHAPE), Polygon(square(1, 1, 3))) 

142 assert polygons_overlap(Polygon(L_SHAPE), 

143 Polygon([(0, 0), (3, 0), (3, 1), (0, 1)])) 

144 

145 def test_a_sliver_of_shared_area(self): 

146 # One grid unit of overlap is an overlap. 

147 assert polygons_overlap(Polygon(square(0, 0, 4)), 

148 Polygon([(3, 3), (9, 3), (9, 9), (3, 9)])) 

149 

150 def test_overlap_is_symmetric(self): 

151 pairs = ( 

152 (Polygon(square(0, 0, 4)), Polygon(square(2, 2, 4))), 

153 (Polygon(square(0, 0, 4)), Polygon(square(4, 0, 4))), 

154 (Polygon(square(0, 0, 8), [square(2, 2, 4)]), Polygon(square(3, 3, 2))), 

155 (Polygon(L_SHAPE), Polygon(square(1, 1, 3))), 

156 ) 

157 for first, second in pairs: 

158 with self.subTest(first=first.outer, second=second.outer): 

159 assert polygons_overlap(first, second) == polygons_overlap(second, first)