1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
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 The Qt Company. For licensing terms
14 ** and conditions see https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://www.qt.io/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 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39 
40 #ifndef QPOLYGONCLIPPER_P_H
41 #define QPOLYGONCLIPPER_P_H
42 
43 //
44 //  W A R N I N G
45 //  -------------
46 //
47 // This file is not part of the Qt API.  It exists for the convenience
48 // of other Qt classes.  This header file may change from version to
49 // version without notice, or even be removed.
50 //
51 // We mean it.
52 //
53 
54 #include <QtGui/private/qtguiglobal_p.h>
55 #include "private/qdatabuffer_p.h"
56 
57 QT_BEGIN_NAMESPACE
58 
59 /* based on sutherland-hodgman line-by-line clipping, as described in
60    Computer Graphics and Principles */
61 template <typename InType, typename OutType, typename CastType> class QPolygonClipper
62 {
63 public:
QPolygonClipper()64     QPolygonClipper() :
65         buffer1(0), buffer2(0)
66     {
67         x1 = y1 = x2 = y2 = 0;
68     }
69 
~QPolygonClipper()70     ~QPolygonClipper()
71     {
72     }
73 
setBoundingRect(const QRect bounds)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 
boundingRect()82     QRect boundingRect()
83     {
84         return QRect(QPoint(x1, y1), QPoint(x2, y2));
85     }
86 
intersectLeft(const OutType & p1,const OutType & p2)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 
intersectRight(const OutType & p1,const OutType & p2)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 
intersectTop(const OutType & p1,const OutType & p2)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 
intersectBottom(const OutType & p1,const OutType & p2)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
317