1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/legal |
5 | ** |
6 | ** This file is part of the QtGui module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and Digia. For licensing terms and |
14 | ** conditions see http://qt.digia.com/licensing. For further information |
15 | ** use the contact form at http://qt.digia.com/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 2.1 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 2.1 requirements |
23 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
24 | ** |
25 | ** In addition, as a special exception, Digia gives you certain additional |
26 | ** rights. These rights are described in the Digia Qt LGPL Exception |
27 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
28 | ** |
29 | ** GNU General Public License Usage |
30 | ** Alternatively, this file may be used under the terms of the GNU |
31 | ** General Public License version 3.0 as published by the Free Software |
32 | ** Foundation and appearing in the file LICENSE.GPL included in the |
33 | ** packaging of this file. Please review the following information to |
34 | ** ensure the GNU General Public License version 3.0 requirements will be |
35 | ** met: http://www.gnu.org/copyleft/gpl.html. |
36 | ** |
37 | ** |
38 | ** $QT_END_LICENSE$ |
39 | ** |
40 | ****************************************************************************/ |
41 | |
42 | #ifndef QPOLYGONCLIPPER_P_H |
43 | #define QPOLYGONCLIPPER_P_H |
44 | |
45 | // |
46 | // W A R N I N G |
47 | // ------------- |
48 | // |
49 | // This file is not part of the Qt API. It exists for the convenience |
50 | // of other Qt classes. This header file may change from version to |
51 | // version without notice, or even be removed. |
52 | // |
53 | // We mean it. |
54 | // |
55 | |
56 | #include "private/qdatabuffer_p.h" |
57 | |
58 | QT_BEGIN_NAMESPACE |
59 | |
60 | /* based on sutherland-hodgman line-by-line clipping, as described in |
61 | Computer Graphics and Principles */ |
62 | template <typename InType, typename OutType, typename CastType> class QPolygonClipper |
63 | { |
64 | public: |
65 | QPolygonClipper() : |
66 | buffer1(0), buffer2(0) |
67 | { |
68 | x1 = y1 = x2 = y2 = 0; |
69 | } |
70 | |
71 | ~QPolygonClipper() |
72 | { |
73 | } |
74 | |
75 | void setBoundingRect(const QRect bounds) |
76 | { |
77 | x1 = bounds.x(); |
78 | x2 = bounds.x() + bounds.width(); |
79 | y1 = bounds.y(); |
80 | y2 = bounds.y() + bounds.height(); |
81 | } |
82 | |
83 | QRect boundingRect() |
84 | { |
85 | return QRect(QPoint(x1, y1), QPoint(x2, y2)); |
86 | } |
87 | |
88 | inline OutType intersectLeft(const OutType &p1, const OutType &p2) |
89 | { |
90 | OutType t; |
91 | qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x); |
92 | t.x = x1; |
93 | t.y = static_cast<CastType>(p2.y + (x1 - p2.x) * dy); |
94 | return t; |
95 | } |
96 | |
97 | |
98 | inline OutType intersectRight(const OutType &p1, const OutType &p2) |
99 | { |
100 | OutType t; |
101 | qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x); |
102 | t.x = x2; |
103 | t.y = static_cast<CastType>(p2.y + (x2 - p2.x) * dy); |
104 | return t; |
105 | } |
106 | |
107 | |
108 | inline OutType intersectTop(const OutType &p1, const OutType &p2) |
109 | { |
110 | OutType t; |
111 | qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y); |
112 | t.x = static_cast<CastType>(p2.x + (y1 - p2.y) * dx); |
113 | t.y = y1; |
114 | return t; |
115 | } |
116 | |
117 | |
118 | inline OutType intersectBottom(const OutType &p1, const OutType &p2) |
119 | { |
120 | OutType t; |
121 | qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y); |
122 | t.x = static_cast<CastType>(p2.x + (y2 - p2.y) * dx); |
123 | t.y = y2; |
124 | return t; |
125 | } |
126 | |
127 | |
128 | void clipPolygon(const InType *inPoints, int inCount, OutType **outPoints, int *outCount, |
129 | bool closePolygon = true) |
130 | { |
131 | Q_ASSERT(outPoints); |
132 | Q_ASSERT(outCount); |
133 | |
134 | if (inCount < 2) { |
135 | *outCount = 0; |
136 | return; |
137 | } |
138 | |
139 | buffer1.reset(); |
140 | buffer2.reset(); |
141 | |
142 | QDataBuffer<OutType> *source = &buffer1; |
143 | QDataBuffer<OutType> *clipped = &buffer2; |
144 | |
145 | // Gather some info since we are iterating through the points anyway.. |
146 | bool doLeft = false, doRight = false, doTop = false, doBottom = false; |
147 | OutType ot; |
148 | for (int i=0; i<inCount; ++i) { |
149 | ot = inPoints[i]; |
150 | clipped->add(ot); |
151 | |
152 | if (ot.x < x1) |
153 | doLeft = true; |
154 | else if (ot.x > x2) |
155 | doRight = true; |
156 | if (ot.y < y1) |
157 | doTop = true; |
158 | else if (ot.y > y2) |
159 | doBottom = true; |
160 | } |
161 | |
162 | if (doLeft && clipped->size() > 1) { |
163 | QDataBuffer<OutType> *tmp = source; |
164 | source = clipped; |
165 | clipped = tmp; |
166 | clipped->reset(); |
167 | int lastPos, start; |
168 | if (closePolygon) { |
169 | lastPos = source->size() - 1; |
170 | start = 0; |
171 | } else { |
172 | lastPos = 0; |
173 | start = 1; |
174 | if (source->at(0).x >= x1) |
175 | clipped->add(source->at(0)); |
176 | } |
177 | for (int i=start; i<inCount; ++i) { |
178 | const OutType &cpt = source->at(i); |
179 | const OutType &ppt = source->at(lastPos); |
180 | |
181 | if (cpt.x >= x1) { |
182 | if (ppt.x >= x1) { |
183 | clipped->add(cpt); |
184 | } else { |
185 | clipped->add(intersectLeft(cpt, ppt)); |
186 | clipped->add(cpt); |
187 | } |
188 | } else if (ppt.x >= x1) { |
189 | clipped->add(intersectLeft(cpt, ppt)); |
190 | } |
191 | lastPos = i; |
192 | } |
193 | } |
194 | |
195 | if (doRight && clipped->size() > 1) { |
196 | QDataBuffer<OutType> *tmp = source; |
197 | source = clipped; |
198 | clipped = tmp; |
199 | clipped->reset(); |
200 | int lastPos, start; |
201 | if (closePolygon) { |
202 | lastPos = source->size() - 1; |
203 | start = 0; |
204 | } else { |
205 | lastPos = 0; |
206 | start = 1; |
207 | if (source->at(0).x <= x2) |
208 | clipped->add(source->at(0)); |
209 | } |
210 | for (int i=start; i<source->size(); ++i) { |
211 | const OutType &cpt = source->at(i); |
212 | const OutType &ppt = source->at(lastPos); |
213 | |
214 | if (cpt.x <= x2) { |
215 | if (ppt.x <= x2) { |
216 | clipped->add(cpt); |
217 | } else { |
218 | clipped->add(intersectRight(cpt, ppt)); |
219 | clipped->add(cpt); |
220 | } |
221 | } else if (ppt.x <= x2) { |
222 | clipped->add(intersectRight(cpt, ppt)); |
223 | } |
224 | |
225 | lastPos = i; |
226 | } |
227 | |
228 | } |
229 | |
230 | if (doTop && clipped->size() > 1) { |
231 | QDataBuffer<OutType> *tmp = source; |
232 | source = clipped; |
233 | clipped = tmp; |
234 | clipped->reset(); |
235 | int lastPos, start; |
236 | if (closePolygon) { |
237 | lastPos = source->size() - 1; |
238 | start = 0; |
239 | } else { |
240 | lastPos = 0; |
241 | start = 1; |
242 | if (source->at(0).y >= y1) |
243 | clipped->add(source->at(0)); |
244 | } |
245 | for (int i=start; i<source->size(); ++i) { |
246 | const OutType &cpt = source->at(i); |
247 | const OutType &ppt = source->at(lastPos); |
248 | |
249 | if (cpt.y >= y1) { |
250 | if (ppt.y >= y1) { |
251 | clipped->add(cpt); |
252 | } else { |
253 | clipped->add(intersectTop(cpt, ppt)); |
254 | clipped->add(cpt); |
255 | } |
256 | } else if (ppt.y >= y1) { |
257 | clipped->add(intersectTop(cpt, ppt)); |
258 | } |
259 | |
260 | lastPos = i; |
261 | } |
262 | } |
263 | |
264 | if (doBottom && clipped->size() > 1) { |
265 | QDataBuffer<OutType> *tmp = source; |
266 | source = clipped; |
267 | clipped = tmp; |
268 | clipped->reset(); |
269 | int lastPos, start; |
270 | if (closePolygon) { |
271 | lastPos = source->size() - 1; |
272 | start = 0; |
273 | } else { |
274 | lastPos = 0; |
275 | start = 1; |
276 | if (source->at(0).y <= y2) |
277 | clipped->add(source->at(0)); |
278 | } |
279 | for (int i=start; i<source->size(); ++i) { |
280 | const OutType &cpt = source->at(i); |
281 | const OutType &ppt = source->at(lastPos); |
282 | |
283 | if (cpt.y <= y2) { |
284 | if (ppt.y <= y2) { |
285 | clipped->add(cpt); |
286 | } else { |
287 | clipped->add(intersectBottom(cpt, ppt)); |
288 | clipped->add(cpt); |
289 | } |
290 | } else if (ppt.y <= y2) { |
291 | clipped->add(intersectBottom(cpt, ppt)); |
292 | } |
293 | lastPos = i; |
294 | } |
295 | } |
296 | |
297 | if (closePolygon && clipped->size() > 0) { |
298 | // close clipped polygon |
299 | if (clipped->at(0).x != clipped->at(clipped->size()-1).x || |
300 | clipped->at(0).y != clipped->at(clipped->size()-1).y) { |
301 | OutType ot = clipped->at(0); |
302 | clipped->add(ot); |
303 | } |
304 | } |
305 | *outCount = clipped->size(); |
306 | *outPoints = clipped->data(); |
307 | } |
308 | |
309 | private: |
310 | int x1, x2, y1, y2; |
311 | QDataBuffer<OutType> buffer1; |
312 | QDataBuffer<OutType> buffer2; |
313 | }; |
314 | |
315 | QT_END_NAMESPACE |
316 | |
317 | #endif // QPOLYGONCLIPPER_P_H |
318 | |