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