src/gui/painting/qpolygonclipper_p.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 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 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  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         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
 309 private:
 310     int x1, x2, y1, y2;
 311     QDataBuffer<OutType> buffer1;
 312     QDataBuffer<OutType> buffer2;
 313 };
 314
 315 QT_END_NAMESPACE
 316
 317 #endif // QPOLYGONCLIPPER_P_H