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
58QT_BEGIN_NAMESPACE
59
60/* based on sutherland-hodgman line-by-line clipping, as described in
61 Computer Graphics and Principles */
62template <typename InType, typename OutType, typename CastType> class QPolygonClipper
63{
64public:
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
309private:
310 int x1, x2, y1, y2;
311 QDataBuffer<OutType> buffer1;
312 QDataBuffer<OutType> buffer2;
313};
314
315QT_END_NAMESPACE
316
317#endif // QPOLYGONCLIPPER_P_H
318