Qt 4.8
qpolygonclipper_p.h
Go to the documentation of this file.
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 
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:
66  buffer1(0), buffer2(0)
67  {
68  x1 = y1 = x2 = y2 = 0;
69  }
70 
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 
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;
313 };
314 
316 
317 #endif // QPOLYGONCLIPPER_P_H
void setBoundingRect(const QRect bounds)
QDataBuffer< OutType > buffer1
double qreal
Definition: qglobal.h:1193
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
QDataBuffer< OutType > buffer2
Type * data() const
Definition: qdatabuffer_p.h:84
int width() const
Returns the width of the rectangle.
Definition: qrect.h:303
int height() const
Returns the height of the rectangle.
Definition: qrect.h:306
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
void clipPolygon(const InType *inPoints, int inCount, OutType **outPoints, int *outCount, bool closePolygon=true)
Type & at(int i)
Definition: qdatabuffer_p.h:86
void add(const Type &t)
Definition: qdatabuffer_p.h:93
OutType intersectBottom(const OutType &p1, const OutType &p2)
OutType intersectRight(const OutType &p1, const OutType &p2)
int y() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:255
int x() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:252
The QPoint class defines a point in the plane using integer precision.
Definition: qpoint.h:53
The QRect class defines a rectangle in the plane using integer precision.
Definition: qrect.h:58
OutType intersectLeft(const OutType &p1, const OutType &p2)
OutType intersectTop(const OutType &p1, const OutType &p2)
void reset()
Definition: qdatabuffer_p.h:79
int size() const
Definition: qdatabuffer_p.h:83