Qt 4.8
qpolygon.cpp
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 #include "qpolygon.h"
43 #include "qrect.h"
44 #include "qdatastream.h"
45 #include "qmatrix.h"
46 #include "qdebug.h"
47 #include "qpainterpath.h"
48 #include "qvariant.h"
49 #include "qpainterpath_p.h"
50 #include "qbezier_p.h"
51 
52 #include <stdarg.h>
53 
55 
56 //same as qt_painterpath_isect_line in qpainterpath.cpp
57 static void qt_polygon_isect_line(const QPointF &p1, const QPointF &p2, const QPointF &pos,
58  int *winding)
59 {
60  qreal x1 = p1.x();
61  qreal y1 = p1.y();
62  qreal x2 = p2.x();
63  qreal y2 = p2.y();
64  qreal y = pos.y();
65 
66  int dir = 1;
67 
68  if (qFuzzyCompare(y1, y2)) {
69  // ignore horizontal lines according to scan conversion rule
70  return;
71  } else if (y2 < y1) {
72  qreal x_tmp = x2; x2 = x1; x1 = x_tmp;
73  qreal y_tmp = y2; y2 = y1; y1 = y_tmp;
74  dir = -1;
75  }
76 
77  if (y >= y1 && y < y2) {
78  qreal x = x1 + ((x2 - x1) / (y2 - y1)) * (y - y1);
79 
80  // count up the winding number if we're
81  if (x<=pos.x()) {
82  (*winding) += dir;
83  }
84  }
85 }
86 
127 /*****************************************************************************
128  QPolygon member functions
129  *****************************************************************************/
130 
194 QPolygon::QPolygon(const QRect &r, bool closed)
195 {
196  reserve(closed ? 5 : 4);
197  *this << QPoint(r.x(), r.y())
198  << QPoint(r.x() + r.width(), r.y())
199  << QPoint(r.x() + r.width(), r.y() + r.height())
200  << QPoint(r.x(), r.y() + r.height());
201  if (closed)
202  *this << QPoint(r.left(), r.top());
203 }
204 
216 QPolygon::QPolygon(int nPoints, const int *points)
217 {
218  setPoints(nPoints, points);
219 }
220 
221 
238 void QPolygon::translate(int dx, int dy)
239 {
240  if (dx == 0 && dy == 0)
241  return;
242 
243  register QPoint *p = data();
244  register int i = size();
245  QPoint pt(dx, dy);
246  while (i--) {
247  *p += pt;
248  ++p;
249  }
250 }
251 
270 QPolygon QPolygon::translated(int dx, int dy) const
271 {
272  QPolygon copy(*this);
273  copy.translate(dx, dy);
274  return copy;
275 }
276 
297 void QPolygon::point(int index, int *x, int *y) const
298 {
299  QPoint p = at(index);
300  if (x)
301  *x = (int)p.x();
302  if (y)
303  *y = (int)p.y();
304 }
305 
350 void QPolygon::setPoints(int nPoints, const int *points)
351 {
352  resize(nPoints);
353  int i = 0;
354  while (nPoints--) {
355  setPoint(i++, *points, *(points+1));
356  points += 2;
357  }
358 }
359 
377 void QPolygon::setPoints(int nPoints, int firstx, int firsty, ...)
378 {
379  va_list ap;
380  resize(nPoints);
381  setPoint(0, firstx, firsty);
382  int i = 0, x, y;
383  va_start(ap, firsty);
384  while (--nPoints) {
385  x = va_arg(ap, int);
386  y = va_arg(ap, int);
387  setPoint(++i, x, y);
388  }
389  va_end(ap);
390 }
391 
406 void QPolygon::putPoints(int index, int nPoints, const int *points)
407 {
408  if (index + nPoints > size())
409  resize(index + nPoints);
410  int i = index;
411  while (nPoints--) {
412  setPoint(i++, *points, *(points+1));
413  points += 2;
414  }
415 }
416 
438 void QPolygon::putPoints(int index, int nPoints, int firstx, int firsty, ...)
439 {
440  va_list ap;
441  if (index + nPoints > size())
442  resize(index + nPoints);
443  if (nPoints <= 0)
444  return;
445  setPoint(index, firstx, firsty);
446  int i = index, x, y;
447  va_start(ap, firsty);
448  while (--nPoints) {
449  x = va_arg(ap, int);
450  y = va_arg(ap, int);
451  setPoint(++i, x, y);
452  }
453  va_end(ap);
454 }
455 
456 
471 void QPolygon::putPoints(int index, int nPoints, const QPolygon & from, int fromIndex)
472 {
473  if (index + nPoints > size())
474  resize(index + nPoints);
475  if (nPoints <= 0)
476  return;
477  int n = 0;
478  while(n < nPoints) {
479  setPoint(index + n, from[fromIndex+n]);
480  ++n;
481  }
482 }
483 
484 
493 {
494  if (isEmpty())
495  return QRect(0, 0, 0, 0);
496  register const QPoint *pd = constData();
497  int minx, maxx, miny, maxy;
498  minx = maxx = pd->x();
499  miny = maxy = pd->y();
500  ++pd;
501  for (int i = 1; i < size(); ++i) {
502  if (pd->x() < minx)
503  minx = pd->x();
504  else if (pd->x() > maxx)
505  maxx = pd->x();
506  if (pd->y() < miny)
507  miny = pd->y();
508  else if (pd->y() > maxy)
509  maxy = pd->y();
510  ++pd;
511  }
512  return QRect(QPoint(minx,miny), QPoint(maxx,maxy));
513 }
514 
515 #ifndef QT_NO_DEBUG_STREAM
517 {
518 #ifndef Q_BROKEN_DEBUG_STREAM
519  dbg.nospace() << "QPolygon(";
520  for (int i = 0; i < a.count(); ++i)
521  dbg.nospace() << a.at(i);
522  dbg.nospace() << ')';
523  return dbg.space();
524 #else
525  qWarning("This compiler doesn't support streaming QPolygon to QDebug");
526  return dbg;
527  Q_UNUSED(a);
528 #endif
529 }
530 #endif
531 
532 
567 /*****************************************************************************
568  QPolygonF member functions
569  *****************************************************************************/
570 
627 {
628  reserve(5);
629  append(QPointF(r.x(), r.y()));
630  append(QPointF(r.x() + r.width(), r.y()));
631  append(QPointF(r.x() + r.width(), r.y() + r.height()));
632  append(QPointF(r.x(), r.y() + r.height()));
633  append(QPointF(r.x(), r.y()));
634 }
635 
649 {
650  reserve(a.size());
651  for (int i=0; i<a.size(); ++i)
652  append(a.at(i));
653 }
654 
671 void QPolygonF::translate(const QPointF &offset)
672 {
673  if (offset.isNull())
674  return;
675 
676  register QPointF *p = data();
677  register int i = size();
678  while (i--) {
679  *p += offset;
680  ++p;
681  }
682 }
683 
703 {
704  QPolygonF copy(*this);
705  copy.translate(offset);
706  return copy;
707 }
708 
743 {
744  if (isEmpty())
745  return QRectF(0, 0, 0, 0);
746  register const QPointF *pd = constData();
747  qreal minx, maxx, miny, maxy;
748  minx = maxx = pd->x();
749  miny = maxy = pd->y();
750  ++pd;
751  for (int i = 1; i < size(); ++i) {
752  if (pd->x() < minx)
753  minx = pd->x();
754  else if (pd->x() > maxx)
755  maxx = pd->x();
756  if (pd->y() < miny)
757  miny = pd->y();
758  else if (pd->y() > maxy)
759  maxy = pd->y();
760  ++pd;
761  }
762  return QRectF(minx,miny, maxx - minx, maxy - miny);
763 }
764 
773 {
774  QPolygon a;
775  a.reserve(size());
776  for (int i=0; i<size(); ++i)
777  a.append(at(i).toPoint());
778  return a;
779 }
780 
806 QPolygon::operator QVariant() const
807 {
808  return QVariant(QVariant::Polygon, this);
809 }
810 
811 /*****************************************************************************
812  QPolygon stream functions
813  *****************************************************************************/
814 #ifndef QT_NO_DATASTREAM
815 
829 {
830  const QVector<QPoint> &v = a;
831  return s << v;
832 }
833 
848 {
849  QVector<QPoint> &v = a;
850  return s >> v;
851 }
852 #endif // QT_NO_DATASTREAM
853 
854 /*****************************************************************************
855  QPolygonF stream functions
856  *****************************************************************************/
857 #ifndef QT_NO_DATASTREAM
858 
872 {
873  quint32 len = a.size();
874  uint i;
875 
876  s << len;
877  for (i = 0; i < len; ++i)
878  s << a.at(i);
879  return s;
880 }
881 
896 {
897  quint32 len;
898  uint i;
899 
900  s >> len;
901  a.reserve(a.size() + (int)len);
902  QPointF p;
903  for (i = 0; i < len; ++i) {
904  s >> p;
905  a.insert(i, p);
906  }
907  return s;
908 }
909 #endif //QT_NO_DATASTREAM
910 
911 #ifndef QT_NO_DEBUG_STREAM
913 {
914 #ifndef Q_BROKEN_DEBUG_STREAM
915  dbg.nospace() << "QPolygonF(";
916  for (int i = 0; i < a.count(); ++i)
917  dbg.nospace() << a.at(i);
918  dbg.nospace() << ')';
919  return dbg.space();
920 #else
921  qWarning("This compiler doesn't support streaming QPolygonF to QDebug");
922  return dbg;
923  Q_UNUSED(a);
924 #endif
925 }
926 #endif
927 
928 
940 bool QPolygonF::containsPoint(const QPointF &pt, Qt::FillRule fillRule) const
941 {
942  if (isEmpty())
943  return false;
944 
945  int winding_number = 0;
946 
947  QPointF last_pt = at(0);
948  QPointF last_start = at(0);
949  for (int i = 1; i < size(); ++i) {
950  const QPointF &e = at(i);
951  qt_polygon_isect_line(last_pt, e, pt, &winding_number);
952  last_pt = e;
953  }
954 
955  // implicitly close last subpath
956  if (last_pt != last_start)
957  qt_polygon_isect_line(last_pt, last_start, pt, &winding_number);
958 
959  return (fillRule == Qt::WindingFill
960  ? (winding_number != 0)
961  : ((winding_number % 2) != 0));
962 }
963 
974 bool QPolygon::containsPoint(const QPoint &pt, Qt::FillRule fillRule) const
975 {
976  if (isEmpty())
977  return false;
978 
979  int winding_number = 0;
980 
981  QPoint last_pt = at(0);
982  QPoint last_start = at(0);
983  for (int i = 1; i < size(); ++i) {
984  const QPoint &e = at(i);
985  qt_polygon_isect_line(last_pt, e, pt, &winding_number);
986  last_pt = e;
987  }
988 
989  // implicitly close last subpath
990  if (last_pt != last_start)
991  qt_polygon_isect_line(last_pt, last_start, pt, &winding_number);
992 
993  return (fillRule == Qt::WindingFill
994  ? (winding_number != 0)
995  : ((winding_number % 2) != 0));
996 }
997 
1013 {
1014  QPainterPath subject; subject.addPolygon(*this);
1015  QPainterPath clip; clip.addPolygon(r);
1016 
1017  return subject.united(clip).toFillPolygon().toPolygon();
1018 }
1019 
1033 {
1034  QPainterPath subject; subject.addPolygon(*this);
1035  QPainterPath clip; clip.addPolygon(r);
1036 
1037  return subject.intersected(clip).toFillPolygon().toPolygon();
1038 }
1039 
1054 {
1055  QPainterPath subject; subject.addPolygon(*this);
1056  QPainterPath clip; clip.addPolygon(r);
1057 
1058  return subject.subtracted(clip).toFillPolygon().toPolygon();
1059 }
1060 
1076 {
1077  QPainterPath subject; subject.addPolygon(*this);
1078  QPainterPath clip; clip.addPolygon(r);
1079 
1080  return subject.united(clip).toFillPolygon();
1081 }
1082 
1097 {
1098  QPainterPath subject; subject.addPolygon(*this);
1099  QPainterPath clip; clip.addPolygon(r);
1100 
1101  return subject.intersected(clip).toFillPolygon();
1102 }
1103 
1118 {
1119  QPainterPath subject; subject.addPolygon(*this);
1120  QPainterPath clip; clip.addPolygon(r);
1121  return subject.subtracted(clip).toFillPolygon();
1122 }
1123 
The QVariant class acts like a union for the most common Qt data types.
Definition: qvariant.h:92
The QDebug class provides an output stream for debugging information.
Definition: qdebug.h:62
qreal y() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:667
QPolygon united(const QPolygon &r) const
Returns a polygon which is the union of this polygon and r.
Definition: qpolygon.cpp:1012
double qreal
Definition: qglobal.h:1193
QDataStream & operator>>(QDataStream &stream, QPolygon &polygon)
Reads a polygon from the given stream into the given polygon, and returns a reference to the stream...
Definition: qpolygon.cpp:847
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
QDataStream & operator<<(QDataStream &stream, const QPolygon &polygon)
Writes the given polygon to the given stream, and returns a reference to the stream.
Definition: qpolygon.cpp:828
QPolygon translated(int dx, int dy) const
Returns a copy of the polygon that is translated by ({dx}, {dy}).
Definition: qpolygon.cpp:270
The QPainterPath class provides a container for painting operations, enabling graphical shapes to be ...
Definition: qpainterpath.h:67
int count(const T &t) const
Returns the number of occurrences of value in the vector.
Definition: qvector.h:742
QDebug & nospace()
Clears the stream&#39;s internal flag that records whether the last character was a space and returns a r...
Definition: qdebug.h:92
The QPointF class defines a point in the plane using floating point precision.
Definition: qpoint.h:214
FillRule
Definition: qnamespace.h:1485
QPainterPath subtracted(const QPainterPath &r) const
Returns a path which is p&#39;s fill area subtracted from this path&#39;s fill area.
QPainterPath intersected(const QPainterPath &r) const
Returns a path which is the intersection of this path&#39;s fill area and p&#39;s fill area.
int left() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:240
int width() const
Returns the width of the rectangle.
Definition: qrect.h:303
QPolygon()
Constructs a polygon with no points.
Definition: qpolygon.h:63
long ASN1_INTEGER_get ASN1_INTEGER * a
void putPoints(int index, int nPoints, const int *points)
Copies nPoints points from the points coord array into this point array, and resizes the point array ...
Definition: qpolygon.cpp:406
QPolygonF()
Constructs a polygon with no points.
Definition: qpolygon.h:137
The QPolygon class provides a vector of points using integer precision.
Definition: qpolygon.h:60
void addPolygon(const QPolygonF &polygon)
Adds the given polygon to the path as an (unclosed) subpath.
int height() const
Returns the height of the rectangle.
Definition: qrect.h:306
QRectF boundingRect() const
Returns the bounding rectangle of the polygon, or QRectF(0,0,0,0) if the polygon is empty...
Definition: qpolygon.cpp:742
QPolygon toPolygon() const
Creates and returns a QPolygon by converting each QPointF to a QPoint.
Definition: qpolygon.cpp:772
qreal x() const
Returns the x-coordinate of this point.
Definition: qpoint.h:282
void resize(int size)
Sets the size of the vector to size.
Definition: qvector.h:342
QPolygonF translated(qreal dx, qreal dy) const
Returns a copy of the polygon that is translated by ({dx}, {dy}).
Definition: qpolygon.h:182
void translate(int dx, int dy)
Translates all points in the polygon by ({dx}, {dy}).
Definition: qpolygon.cpp:238
QPolygonF united(const QPolygonF &r) const
Returns a polygon which is the union of this polygon and r.
Definition: qpolygon.cpp:1075
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
The QRectF class defines a rectangle in the plane using floating point precision. ...
Definition: qrect.h:511
QPolygonF toFillPolygon(const QMatrix &matrix=QMatrix()) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
QPolygonF intersected(const QPolygonF &r) const
Returns a polygon which is the intersection of this polygon and r.
Definition: qpolygon.cpp:1096
QPolygon subtracted(const QPolygon &r) const
Returns a polygon which is r subtracted from this polygon.
Definition: qpolygon.cpp:1053
qreal height() const
Returns the height of the rectangle.
Definition: qrect.h:710
The QPolygonF class provides a vector of points using floating point precision.
Definition: qpolygon.h:134
void append(const QPoint &t)
Inserts value at the end of the vector.
Definition: qvector.h:573
Q_CORE_EXPORT void qWarning(const char *,...)
unsigned int uint
Definition: qglobal.h:996
qreal width() const
Returns the width of the rectangle.
Definition: qrect.h:707
static void qt_polygon_isect_line(const QPointF &p1, const QPointF &p2, const QPointF &pos, int *winding)
Definition: qpolygon.cpp:57
void translate(qreal dx, qreal dy)
Translates all points in the polygon by ({dx}, {dy}).
Definition: qpolygon.h:179
const QPoint & at(int i) const
Returns the item at index position i in the vector.
Definition: qvector.h:350
void insert(int i, const T &t)
Inserts value at index position i in the vector.
Definition: qvector.h:362
int top() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:243
int y() const
Returns the y-coordinate of the rectangle&#39;s top edge.
Definition: qrect.h:255
qreal x() const
Returns the x-coordinate of the rectangle&#39;s left edge.
Definition: qrect.h:664
QPainterPath united(const QPainterPath &r) const
Returns a path which is the union of this path&#39;s fill area and p&#39;s fill area.
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
unsigned int quint32
Definition: qglobal.h:938
The QRect class defines a rectangle in the plane using integer precision.
Definition: qrect.h:58
void setPoint(int index, int x, int y)
Sets the point at the given index to the point specified by ({x}, {y}).
Definition: qpolygon.h:120
QRect boundingRect() const
Returns the bounding rectangle of the polygon, or QRect(0, 0, 0, 0) if the polygon is empty...
Definition: qpolygon.cpp:492
bool isNull() const
Returns true if both the x and y coordinates are set to +0.
Definition: qpoint.h:277
bool containsPoint(const QPoint &pt, Qt::FillRule fillRule) const
Returns true if the given point is inside the polygon according to the specified fillRule; otherwise ...
Definition: qpolygon.cpp:974
int y() const
Returns the y coordinate of this point.
Definition: qpoint.h:131
qreal y() const
Returns the y-coordinate of this point.
Definition: qpoint.h:287
quint16 index
bool containsPoint(const QPointF &pt, Qt::FillRule fillRule) const
Returns true if the given point is inside the polygon according to the specified fillRule; otherwise ...
Definition: qpolygon.cpp:940
bool qFuzzyCompare(const QMatrix &m1, const QMatrix &m2)
The qFuzzyCompare function is for comparing two matrices using a fuzziness factor.
Definition: qmatrix.h:172
QPoint * data()
Returns a pointer to the data stored in the vector.
Definition: qvector.h:152
void setPoints(int nPoints, const int *points)
Resizes the polygon to nPoints and populates it with the given points.
Definition: qpolygon.cpp:350
bool isEmpty() const
Returns true if the vector has size 0; otherwise returns false.
Definition: qvector.h:139
The QDataStream class provides serialization of binary data to a QIODevice.
Definition: qdatastream.h:71
const QPoint * constData() const
Returns a const pointer to the data stored in the vector.
Definition: qvector.h:154
void reserve(int size)
Attempts to allocate memory for at least size elements.
Definition: qvector.h:339
int x() const
Returns the x coordinate of this point.
Definition: qpoint.h:128
QPolygonF subtracted(const QPolygonF &r) const
Returns a polygon which is r subtracted from this polygon.
Definition: qpolygon.cpp:1117
QDebug & space()
Writes a space character to the debug stream and returns a reference to the stream.
Definition: qdebug.h:91
#define Q_UNUSED(x)
Indicates to the compiler that the parameter with the specified name is not used in the body of a fun...
Definition: qglobal.h:1729
int size() const
Returns the number of items in the vector.
Definition: qvector.h:137
void point(int i, int *x, int *y) const
Extracts the coordinates of the point at the given index to {x} and *{y} (if they are valid pointers)...
Definition: qpolygon.cpp:297
QPolygon intersected(const QPolygon &r) const
Returns a polygon which is the intersection of this polygon and r.
Definition: qpolygon.cpp:1032