|
1 /**************************************************************************** |
|
2 ** |
|
3 ** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). |
|
4 ** All rights reserved. |
|
5 ** Contact: Nokia Corporation (qt-info@nokia.com) |
|
6 ** |
|
7 ** This file is part of the QtGui module of the Qt Toolkit. |
|
8 ** |
|
9 ** $QT_BEGIN_LICENSE:LGPL$ |
|
10 ** No Commercial Usage |
|
11 ** This file contains pre-release code and may not be distributed. |
|
12 ** You may use this file in accordance with the terms and conditions |
|
13 ** contained in the Technology Preview License Agreement accompanying |
|
14 ** this package. |
|
15 ** |
|
16 ** GNU Lesser General Public License Usage |
|
17 ** Alternatively, this file may be used under the terms of the GNU Lesser |
|
18 ** General Public License version 2.1 as published by the Free Software |
|
19 ** Foundation and appearing in the file LICENSE.LGPL included in the |
|
20 ** packaging of this file. Please review the following information to |
|
21 ** ensure the GNU Lesser General Public License version 2.1 requirements |
|
22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
|
23 ** |
|
24 ** In addition, as a special exception, Nokia gives you certain additional |
|
25 ** rights. These rights are described in the Nokia Qt LGPL Exception |
|
26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
|
27 ** |
|
28 ** If you have questions regarding the use of this file, please contact |
|
29 ** Nokia at qt-info@nokia.com. |
|
30 ** |
|
31 ** |
|
32 ** |
|
33 ** |
|
34 ** |
|
35 ** |
|
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 { |
|
67 x1 = y1 = x2 = y2 = 0; |
|
68 } |
|
69 |
|
70 ~QPolygonClipper() |
|
71 { |
|
72 } |
|
73 |
|
74 void setBoundingRect(const QRect bounds) |
|
75 { |
|
76 x1 = bounds.x(); |
|
77 x2 = bounds.x() + bounds.width(); |
|
78 y1 = bounds.y(); |
|
79 y2 = bounds.y() + bounds.height(); |
|
80 } |
|
81 |
|
82 QRect boundingRect() |
|
83 { |
|
84 return QRect(QPoint(x1, y1), QPoint(x2, y2)); |
|
85 } |
|
86 |
|
87 inline OutType intersectLeft(const OutType &p1, const OutType &p2) |
|
88 { |
|
89 OutType t; |
|
90 qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x); |
|
91 t.x = x1; |
|
92 t.y = static_cast<CastType>(p2.y + (x1 - p2.x) * dy); |
|
93 return t; |
|
94 } |
|
95 |
|
96 |
|
97 inline OutType intersectRight(const OutType &p1, const OutType &p2) |
|
98 { |
|
99 OutType t; |
|
100 qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x); |
|
101 t.x = x2; |
|
102 t.y = static_cast<CastType>(p2.y + (x2 - p2.x) * dy); |
|
103 return t; |
|
104 } |
|
105 |
|
106 |
|
107 inline OutType intersectTop(const OutType &p1, const OutType &p2) |
|
108 { |
|
109 OutType t; |
|
110 qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y); |
|
111 t.x = static_cast<CastType>(p2.x + (y1 - p2.y) * dx); |
|
112 t.y = y1; |
|
113 return t; |
|
114 } |
|
115 |
|
116 |
|
117 inline OutType intersectBottom(const OutType &p1, const OutType &p2) |
|
118 { |
|
119 OutType t; |
|
120 qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y); |
|
121 t.x = static_cast<CastType>(p2.x + (y2 - p2.y) * dx); |
|
122 t.y = y2; |
|
123 return t; |
|
124 } |
|
125 |
|
126 |
|
127 void clipPolygon(const InType *inPoints, int inCount, OutType **outPoints, int *outCount, |
|
128 bool closePolygon = true) |
|
129 { |
|
130 Q_ASSERT(outPoints); |
|
131 Q_ASSERT(outCount); |
|
132 |
|
133 if (inCount < 2) { |
|
134 *outCount = 0; |
|
135 return; |
|
136 } |
|
137 |
|
138 buffer1.reset(); |
|
139 buffer2.reset(); |
|
140 |
|
141 QDataBuffer<OutType> *source = &buffer1; |
|
142 QDataBuffer<OutType> *clipped = &buffer2; |
|
143 |
|
144 // Gather some info since we are iterating through the points anyway.. |
|
145 bool doLeft = false, doRight = false, doTop = false, doBottom = false; |
|
146 OutType ot; |
|
147 for (int i=0; i<inCount; ++i) { |
|
148 ot = inPoints[i]; |
|
149 clipped->add(ot); |
|
150 |
|
151 if (ot.x < x1) |
|
152 doLeft = true; |
|
153 else if (ot.x > x2) |
|
154 doRight = true; |
|
155 if (ot.y < y1) |
|
156 doTop = true; |
|
157 else if (ot.y > y2) |
|
158 doBottom = true; |
|
159 } |
|
160 |
|
161 if (doLeft && clipped->size() > 1) { |
|
162 QDataBuffer<OutType> *tmp = source; |
|
163 source = clipped; |
|
164 clipped = tmp; |
|
165 clipped->reset(); |
|
166 int lastPos, start; |
|
167 if (closePolygon) { |
|
168 lastPos = source->size() - 1; |
|
169 start = 0; |
|
170 } else { |
|
171 lastPos = 0; |
|
172 start = 1; |
|
173 if (source->at(0).x >= x1) |
|
174 clipped->add(source->at(0)); |
|
175 } |
|
176 for (int i=start; i<inCount; ++i) { |
|
177 const OutType &cpt = source->at(i); |
|
178 const OutType &ppt = source->at(lastPos); |
|
179 |
|
180 if (cpt.x >= x1) { |
|
181 if (ppt.x >= x1) { |
|
182 clipped->add(cpt); |
|
183 } else { |
|
184 clipped->add(intersectLeft(cpt, ppt)); |
|
185 clipped->add(cpt); |
|
186 } |
|
187 } else if (ppt.x >= x1) { |
|
188 clipped->add(intersectLeft(cpt, ppt)); |
|
189 } |
|
190 lastPos = i; |
|
191 } |
|
192 } |
|
193 |
|
194 if (doRight && clipped->size() > 1) { |
|
195 QDataBuffer<OutType> *tmp = source; |
|
196 source = clipped; |
|
197 clipped = tmp; |
|
198 clipped->reset(); |
|
199 int lastPos, start; |
|
200 if (closePolygon) { |
|
201 lastPos = source->size() - 1; |
|
202 start = 0; |
|
203 } else { |
|
204 lastPos = 0; |
|
205 start = 1; |
|
206 if (source->at(0).x <= x2) |
|
207 clipped->add(source->at(0)); |
|
208 } |
|
209 for (int i=start; i<source->size(); ++i) { |
|
210 const OutType &cpt = source->at(i); |
|
211 const OutType &ppt = source->at(lastPos); |
|
212 |
|
213 if (cpt.x <= x2) { |
|
214 if (ppt.x <= x2) { |
|
215 clipped->add(cpt); |
|
216 } else { |
|
217 clipped->add(intersectRight(cpt, ppt)); |
|
218 clipped->add(cpt); |
|
219 } |
|
220 } else if (ppt.x <= x2) { |
|
221 clipped->add(intersectRight(cpt, ppt)); |
|
222 } |
|
223 |
|
224 lastPos = i; |
|
225 } |
|
226 |
|
227 } |
|
228 |
|
229 if (doTop && clipped->size() > 1) { |
|
230 QDataBuffer<OutType> *tmp = source; |
|
231 source = clipped; |
|
232 clipped = tmp; |
|
233 clipped->reset(); |
|
234 int lastPos, start; |
|
235 if (closePolygon) { |
|
236 lastPos = source->size() - 1; |
|
237 start = 0; |
|
238 } else { |
|
239 lastPos = 0; |
|
240 start = 1; |
|
241 if (source->at(0).y >= y1) |
|
242 clipped->add(source->at(0)); |
|
243 } |
|
244 for (int i=start; i<source->size(); ++i) { |
|
245 const OutType &cpt = source->at(i); |
|
246 const OutType &ppt = source->at(lastPos); |
|
247 |
|
248 if (cpt.y >= y1) { |
|
249 if (ppt.y >= y1) { |
|
250 clipped->add(cpt); |
|
251 } else { |
|
252 clipped->add(intersectTop(cpt, ppt)); |
|
253 clipped->add(cpt); |
|
254 } |
|
255 } else if (ppt.y >= y1) { |
|
256 clipped->add(intersectTop(cpt, ppt)); |
|
257 } |
|
258 |
|
259 lastPos = i; |
|
260 } |
|
261 } |
|
262 |
|
263 if (doBottom && clipped->size() > 1) { |
|
264 QDataBuffer<OutType> *tmp = source; |
|
265 source = clipped; |
|
266 clipped = tmp; |
|
267 clipped->reset(); |
|
268 int lastPos, start; |
|
269 if (closePolygon) { |
|
270 lastPos = source->size() - 1; |
|
271 start = 0; |
|
272 } else { |
|
273 lastPos = 0; |
|
274 start = 1; |
|
275 if (source->at(0).y <= y2) |
|
276 clipped->add(source->at(0)); |
|
277 } |
|
278 for (int i=start; i<source->size(); ++i) { |
|
279 const OutType &cpt = source->at(i); |
|
280 const OutType &ppt = source->at(lastPos); |
|
281 |
|
282 if (cpt.y <= y2) { |
|
283 if (ppt.y <= y2) { |
|
284 clipped->add(cpt); |
|
285 } else { |
|
286 clipped->add(intersectBottom(cpt, ppt)); |
|
287 clipped->add(cpt); |
|
288 } |
|
289 } else if (ppt.y <= y2) { |
|
290 clipped->add(intersectBottom(cpt, ppt)); |
|
291 } |
|
292 lastPos = i; |
|
293 } |
|
294 } |
|
295 |
|
296 if (closePolygon && clipped->size() > 0) { |
|
297 // close clipped polygon |
|
298 if (clipped->at(0).x != clipped->at(clipped->size()-1).x || |
|
299 clipped->at(0).y != clipped->at(clipped->size()-1).y) { |
|
300 OutType ot = clipped->at(0); |
|
301 clipped->add(ot); |
|
302 } |
|
303 } |
|
304 *outCount = clipped->size(); |
|
305 *outPoints = clipped->data(); |
|
306 } |
|
307 |
|
308 private: |
|
309 int x1, x2, y1, y2; |
|
310 QDataBuffer<OutType> buffer1; |
|
311 QDataBuffer<OutType> buffer2; |
|
312 }; |
|
313 |
|
314 QT_END_NAMESPACE |
|
315 |
|
316 #endif // QPOLYGONCLIPPER_P_H |