Fri, 28 Jul 2017 15:56:52 +0200
Bugfix SVG offset correction
Changed settings min/max values
15 | 1 | # Imported from python-rectangle-packer commit 32fce1aaba |
2 | # https://github.com/maxretter/python-rectangle-packer | |
3 | # | |
4 | # Python Rectangle Packer - Packs rectangles around a central point | |
5 | # Copyright (C) 2013 Max Retter | |
6 | # | |
7 | # This program is free software: you can redistribute it and/or modify | |
8 | # it under the terms of the GNU General Public License as published by | |
9 | # the Free Software Foundation, either version 3 of the License, or | |
10 | # (at your option) any later version. | |
11 | # | |
12 | # This program is distributed in the hope that it will be useful, | |
13 | # but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | # GNU General Public License for more details. | |
16 | # | |
17 | # You should have received a copy of the GNU General Public License | |
18 | # along with this program. If not, see <http://www.gnu.org/licenses/>. | |
19 | ||
20 | import math | |
21 | ||
22 | import Polygon | |
23 | import Polygon.Utils | |
24 | ||
25 | ||
26 | class Vector2(object): | |
27 | """Simple 2d vector / point class.""" | |
28 | ||
29 | def __init__(self, x=0, y=0): | |
30 | self.x = float(x) | |
31 | self.y = float(y) | |
32 | ||
33 | def __eq__(self, other): | |
34 | return self.x == other.x and self.y == other.y | |
35 | ||
36 | def add(self, other): | |
37 | return Vector2(self.x + other.x, self.y + other.y) | |
38 | ||
39 | def sub(self, other): | |
40 | return Vector2(self.x - other.x, self.y - other.y) | |
41 | ||
42 | def scale(self, factor): | |
43 | return Vector2(self.x * factor, self.y * factor) | |
44 | ||
45 | def magnitude(self): | |
46 | return math.sqrt(self.dot_product(self)) | |
47 | ||
48 | def unit(self): | |
49 | """Build unit vector.""" | |
50 | return self.scale(1 / self.magnitude()) | |
51 | ||
52 | def dot_product(self, other): | |
53 | return self.x * other.x + self.y * other.y | |
54 | ||
55 | def distance(self, other): | |
56 | """Distance forumla for other point.""" | |
57 | return math.sqrt( | |
58 | (other.x - self.x) ** 2 + | |
59 | (other.y - self.y) ** 2 | |
60 | ) | |
61 | ||
62 | ||
63 | class Rect(object): | |
64 | """Simple rectangle object.""" | |
65 | def __init__(self, width, height, data={}): | |
66 | self.width = width | |
67 | self.height = height | |
68 | self.data = data | |
69 | ||
70 | # upper left | |
71 | self.position = Vector2() | |
72 | ||
73 | def half(self): | |
74 | """Half width and height.""" | |
75 | return Vector2( | |
76 | self.width / 2, | |
77 | self.height / 2 | |
78 | ) | |
79 | ||
80 | def expand(self, width, height): | |
81 | """Builds a new rectangle based on this one with given offsets.""" | |
82 | expanded = Rect(self.width + width, self.height + height) | |
83 | expanded.set_center(self.center()) | |
84 | ||
85 | return expanded | |
86 | ||
87 | def point_list(self): | |
88 | top = self.position.y | |
89 | right = self.position.x + self.width | |
90 | bottom = self.position.y + self.height | |
91 | left = self.position.x | |
92 | ||
93 | return PointList([ | |
94 | (left, top), | |
95 | (right, top), | |
96 | (right, bottom), | |
97 | (left, bottom), | |
98 | ]) | |
99 | ||
100 | def center(self): | |
101 | """Center of rect calculated from position and dimensions.""" | |
102 | return self.position.add(self.half()) | |
103 | ||
104 | def set_center(self, center): | |
105 | """Set the position based on a new center point.""" | |
106 | self.position = center.sub(self.half()) | |
107 | ||
108 | def area(self): | |
109 | """Area: length * width.""" | |
110 | return self.width * self.height | |
111 | ||
112 | ||
113 | class PointList(object): | |
114 | """Methods for transforming a list of points.""" | |
115 | def __init__(self, points=[]): | |
116 | self.points = points | |
117 | self._polygon = None | |
118 | ||
119 | def polygon(self): | |
120 | """Builds a polygon from the set of points.""" | |
121 | if not self._polygon: | |
122 | self._polygon = Polygon.Polygon(self.points) | |
123 | ||
124 | return self._polygon | |
125 | ||
126 | def segments(self): | |
127 | """Returns a list of LineSegment objects.""" | |
128 | segs = [] | |
129 | for i, point in enumerate(self.points[1:]): | |
130 | index = i + 1 | |
131 | ||
132 | segs.append(LineSegment( | |
133 | Vector2(self.points[index - 1][0], self.points[index - 1][1]), | |
134 | Vector2(self.points[index][0], self.points[index][1]) | |
135 | )) | |
136 | ||
137 | segs.append(LineSegment( | |
138 | Vector2(self.points[-1][0], self.points[-1][1]), | |
139 | Vector2(self.points[0][0], self.points[0][1]), | |
140 | )) | |
141 | ||
142 | return segs | |
143 | ||
144 | ||
145 | class LineSegment(object): | |
146 | def __init__(self, start, end): | |
147 | self.start = start | |
148 | self.end = end | |
149 | ||
150 | def length(self): | |
151 | """Length of segment vector.""" | |
152 | return self.end.sub(self.start).magnitude() | |
153 | ||
154 | def closest_point_to_point(self, point): | |
155 | """Point along segment that is closest to given point.""" | |
156 | segment_vector = self.end.sub(self.start) | |
157 | point_vector = point.sub(self.start) | |
158 | ||
159 | seg_mag = segment_vector.magnitude() | |
160 | ||
161 | # project point_vector on segment_vector | |
162 | projection = segment_vector.dot_product(point_vector) | |
163 | ||
164 | # scalar value used to interpolate new point along segment_vector | |
165 | scalar = projection / seg_mag ** 2 | |
166 | ||
167 | # clamp on [0,1] | |
168 | scalar = 1.0 if scalar > 1.0 else scalar | |
169 | scalar = 0.0 if scalar < 0.0 else scalar | |
170 | ||
171 | # interpolate scalar along segment and add start point back in | |
172 | return self.start.add(segment_vector.unit().scale(scalar * seg_mag)) | |
173 | ||
174 | def closest_distance_to_point(self, point): | |
175 | """Helper method too automatically return distance.""" | |
176 | closest_point = self.closest_point_to_point(point) | |
177 | return closest_point.distance(point) | |
178 | ||
179 | ||
180 | class Packer(object): | |
181 | def __init__(self): | |
182 | self._rects = [] | |
183 | ||
184 | def add_rect(self, width, height, data={}): | |
185 | self._rects.append(Rect(width, height, data)) | |
186 | ||
187 | def pack(self, padding=0, center=Vector2()): | |
188 | # init everything | |
189 | placed_rects = [] | |
190 | sorted_rects = sorted(self._rects, key=lambda rect: -rect.area()) | |
191 | # double padding due to halfing later on | |
192 | padding *= 2 | |
193 | ||
194 | for rect in sorted_rects: | |
195 | ||
196 | if not placed_rects: | |
197 | # first rect, right on target. | |
198 | rect.set_center(center) | |
199 | ||
200 | else: | |
201 | # Expand each rectangle based on new rect size and padding | |
202 | # get a list of points | |
203 | # build a polygon | |
204 | point_lists = [ | |
205 | pr.expand(rect.width + padding, rect.height + padding).point_list().polygon() | |
206 | for pr in placed_rects | |
207 | ] | |
208 | ||
209 | # take the union of all the polygons (relies on + operator override) | |
210 | # the [0] at the end returns the first "contour", which is the only one we need | |
211 | bounding_points = PointList(sum( | |
212 | point_lists[1:], | |
213 | point_lists[0] | |
214 | )[0]) | |
215 | ||
216 | # find the closest segment | |
217 | closest_segments = sorted( | |
218 | bounding_points.segments(), | |
219 | key=lambda segment: segment.closest_distance_to_point(center) | |
220 | ) | |
221 | ||
222 | # get the closest point | |
223 | place_point = closest_segments[0].closest_point_to_point(center) | |
224 | ||
225 | # set the rect position | |
226 | rect.set_center(place_point) | |
227 | ||
228 | placed_rects.append(rect) | |
229 | ||
230 | return placed_rects |