Qt 4.8
qpathclipper_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 QPATHCLIPPER_P_H
43 #define QPATHCLIPPER_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 purely as an
50 // implementation detail. 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 <QtGui/qpainterpath.h>
57 #include <QtCore/qlist.h>
58 
59 #include <private/qbezier_p.h>
60 #include <private/qdatabuffer_p.h>
61 #include <stdio.h>
62 
64 
66 
67 QT_MODULE(Gui)
68 
69 class QWingedEdge;
70 
72 {
73 public:
74  enum Operation {
78  Simplify
79  };
80 public:
81  QPathClipper(const QPainterPath &subject,
82  const QPainterPath &clip);
83 
84  QPainterPath clip(Operation op = BoolAnd);
85 
86  bool intersect();
87  bool contains();
88 
89  static bool pathToRect(const QPainterPath &path, QRectF *rect = 0);
90  static QPainterPath intersect(const QPainterPath &path, const QRectF &rect);
91 
92 private:
94 
95  enum ClipperMode {
96  ClipMode, // do the full clip
97  CheckMode // for contains/intersects (only interested in whether the result path is non-empty)
98  };
99 
100  bool handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode);
101  bool doClip(QWingedEdge &list, ClipperMode mode);
102 
106 
107  int aMask;
108  int bMask;
109 };
110 
112 {
113 public:
114  QPathVertex(const QPointF &p = QPointF(), int e = -1);
115  operator QPointF() const;
116 
117  int edge;
118 
121 };
122 
124 {
125 public:
126  enum Traversal {
128  LeftTraversal
129  };
130 
131  enum Direction {
133  Backward
134  };
135 
136  enum Type {
138  Curve
139  };
140 
141  QPathEdge(int a = -1, int b = -1);
142 
143  mutable int flag;
144 
145  int windingA;
146  int windingB;
147 
148  int first;
149  int second;
150 
151  double angle;
152  double invAngle;
153 
154  int next(Traversal traversal, Direction direction) const;
155 
156  void setNext(Traversal traversal, Direction direction, int next);
157  void setNext(Direction direction, int next);
158 
159  Direction directionTo(int vertex) const;
160  int vertex(Direction direction) const;
161 
162 private:
163  int m_next[2][2];
164 };
165 
167 {
168 public:
169  struct Intersection {
170  int vertex;
172 
173  int next;
174 
175  bool operator<(const Intersection &o) const {
176  return t < o.t;
177  }
178  };
179 
180  struct Segment {
181  Segment(int pathId, int vertexA, int vertexB)
182  : path(pathId)
183  , va(vertexA)
184  , vb(vertexB)
185  , intersection(-1)
186  {
187  }
188 
189  int path;
190 
191  // vertices
192  int va;
193  int vb;
194 
195  // intersection index
197 
199  };
200 
201 
202  QPathSegments(int reserve);
203 
204  void setPath(const QPainterPath &path);
205  void addPath(const QPainterPath &path);
206 
207  int intersections() const;
208  int segments() const;
209  int points() const;
210 
211  const Segment &segmentAt(int index) const;
212  const QLineF lineAt(int index) const;
213  const QRectF &elementBounds(int index) const;
214  int pathId(int index) const;
215 
216  const QPointF &pointAt(int vertex) const;
217  int addPoint(const QPointF &point);
218 
219  const Intersection *intersectionAt(int index) const;
220  void addIntersection(int index, const Intersection &intersection);
221 
222  void mergePoints();
223 
224 private:
228 
229  int m_pathId;
230 };
231 
233 {
234 public:
236  {
237  int edge;
240 
241  void flipDirection();
242  void flipTraversal();
243 
244  void flip();
245  };
246 
247  QWingedEdge();
248  QWingedEdge(const QPainterPath &subject, const QPainterPath &clip);
249 
250  void simplify();
251  QPainterPath toPath() const;
252 
253  int edgeCount() const;
254 
255  QPathEdge *edge(int edge);
256  const QPathEdge *edge(int edge) const;
257 
258  int vertexCount() const;
259 
260  int addVertex(const QPointF &p);
261 
262  QPathVertex *vertex(int vertex);
263  const QPathVertex *vertex(int vertex) const;
264 
265  TraversalStatus next(const TraversalStatus &status) const;
266 
267  int addEdge(const QPointF &a, const QPointF &b);
268  int addEdge(int vertexA, int vertexB);
269 
270  bool isInside(qreal x, qreal y) const;
271 
272  static QPathEdge::Traversal flip(QPathEdge::Traversal traversal);
274 
275 private:
276  void intersectAndAdd();
277 
278  void printNode(int i, FILE *handle);
279 
280  void removeEdge(int ei);
281 
282  int insert(const QPathVertex &vertex);
283  TraversalStatus findInsertStatus(int vertex, int edge) const;
284 
285  qreal delta(int vertex, int a, int b) const;
286 
289 
291 
293 };
294 
295 inline QPathEdge::QPathEdge(int a, int b)
296  : flag(0)
297  , windingA(0)
298  , windingB(0)
299  , first(a)
300  , second(b)
301  , angle(0)
302  , invAngle(0)
303 {
304  m_next[0][0] = -1;
305  m_next[1][0] = -1;
306  m_next[0][0] = -1;
307  m_next[1][0] = -1;
308 }
309 
310 inline int QPathEdge::next(Traversal traversal, Direction direction) const
311 {
312  return m_next[int(traversal)][int(direction)];
313 }
314 
316 {
317  m_next[int(traversal)][int(direction)] = next;
318 }
319 
321 {
322  m_next[0][int(direction)] = next;
323  m_next[1][int(direction)] = next;
324 }
325 
327 {
328  return first == vertex ? Backward : Forward;
329 }
330 
332 {
333  return direction == Backward ? first : second;
334 }
335 
336 inline QPathVertex::QPathVertex(const QPointF &p, int e)
337  : edge(e)
338  , x(p.x())
339  , y(p.y())
340 {
341 }
342 
343 inline QPathVertex::operator QPointF() const
344 {
345  return QPointF(x, y);
346 }
347 
348 inline QPathSegments::QPathSegments(int reserve) :
349  m_points(reserve),
350  m_segments(reserve),
351  m_intersections(reserve)
352 {
353 }
354 
355 inline int QPathSegments::segments() const
356 {
357  return m_segments.size();
358 }
359 
360 inline int QPathSegments::points() const
361 {
362  return m_points.size();
363 }
364 
365 inline const QPointF &QPathSegments::pointAt(int i) const
366 {
367  return m_points.at(i);
368 }
369 
370 inline int QPathSegments::addPoint(const QPointF &point)
371 {
372  m_points << point;
373  return m_points.size() - 1;
374 }
375 
377 {
378  return m_segments.at(index);
379 }
380 
381 inline const QLineF QPathSegments::lineAt(int index) const
382 {
383  const Segment &segment = m_segments.at(index);
384  return QLineF(m_points.at(segment.va), m_points.at(segment.vb));
385 }
386 
387 inline const QRectF &QPathSegments::elementBounds(int index) const
388 {
389  return m_segments.at(index).bounds;
390 }
391 
392 inline int QPathSegments::pathId(int index) const
393 {
394  return m_segments.at(index).path;
395 }
396 
398 {
399  const int intersection = m_segments.at(index).intersection;
400  if (intersection < 0)
401  return 0;
402  else
403  return &m_intersections.at(intersection);
404 }
405 
407 {
408  return m_intersections.size();
409 }
410 
411 inline void QPathSegments::addIntersection(int index, const Intersection &intersection)
412 {
413  m_intersections << intersection;
414 
415  Segment &segment = m_segments.at(index);
416  if (segment.intersection < 0) {
417  segment.intersection = m_intersections.size() - 1;
418  } else {
419  Intersection *isect = &m_intersections.at(segment.intersection);
420 
421  while (isect->next != 0)
422  isect += isect->next;
423 
424  isect->next = (m_intersections.size() - 1) - (isect - m_intersections.data());
425  }
426 }
427 
429 {
431 }
432 
434 {
435  traversal = QWingedEdge::flip(traversal);
436 }
437 
439 {
440  flipDirection();
441  flipTraversal();
442 }
443 
444 inline int QWingedEdge::edgeCount() const
445 {
446  return m_edges.size();
447 }
448 
449 inline QPathEdge *QWingedEdge::edge(int edge)
450 {
451  return edge < 0 ? 0 : &m_edges.at(edge);
452 }
453 
454 inline const QPathEdge *QWingedEdge::edge(int edge) const
455 {
456  return edge < 0 ? 0 : &m_edges.at(edge);
457 }
458 
459 inline int QWingedEdge::vertexCount() const
460 {
461  return m_vertices.size();
462 }
463 
464 inline int QWingedEdge::addVertex(const QPointF &p)
465 {
466  m_vertices << p;
467  return m_vertices.size() - 1;
468 }
469 
470 inline QPathVertex *QWingedEdge::vertex(int vertex)
471 {
472  return vertex < 0 ? 0 : &m_vertices.at(vertex);
473 }
474 
475 inline const QPathVertex *QWingedEdge::vertex(int vertex) const
476 {
477  return vertex < 0 ? 0 : &m_vertices.at(vertex);
478 }
479 
481 {
483 }
484 
486 {
488 }
489 
491 
493 
494 #endif // QPATHCLIPPER_P_H
QPathEdge::Traversal traversal
Segment(int pathId, int vertexA, int vertexB)
double qreal
Definition: qglobal.h:1193
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
int intersections() const
#define QT_MODULE(x)
Definition: qglobal.h:2783
int segments() const
const QLineF lineAt(int index) const
const Intersection * intersectionAt(int index) const
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
The QPainterPath class provides a container for painting operations, enabling graphical shapes to be ...
Definition: qpainterpath.h:67
The QPointF class defines a point in the plane using floating point precision.
Definition: qpoint.h:214
static void addPoint(QPolygon &a, const QPoint &p)
Definition: qlcdnumber.cpp:989
QPathVertex * vertex(int vertex)
static LibLoadStatus status
Definition: qlocale_icu.cpp:69
int pathId(int index) const
QPathSegments(int reserve)
#define Q_DISABLE_COPY(Class)
Disables the use of copy constructors and assignment operators for the given Class.
Definition: qglobal.h:2523
long ASN1_INTEGER_get ASN1_INTEGER * a
int vertex(Direction direction) const
const Segment & segmentAt(int index) const
QPathEdge::Direction direction
QDataBuffer< QPointF > m_points
The QLineF class provides a two-dimensional vector using floating point precision.
Definition: qline.h:212
int addVertex(const QPointF &p)
#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
Direction directionTo(int vertex) const
QPainterPath subjectPath
QDataBuffer< Segment > m_segments
QPainterPath clipPath
int m_next[2][2]
Type & at(int i)
Definition: qdatabuffer_p.h:86
int addPoint(const QPointF &point)
QDataBuffer< QPathEdge > m_edges
QPathSegments m_segments
const QPointF & pointAt(int vertex) const
int next(Traversal traversal, Direction direction) const
double invAngle
qreal angle(const QPointF &p1, const QPointF &p2)
QPathEdge * edge(int edge)
void setNext(Traversal traversal, Direction direction, int next)
QVector< qreal > m_splitPoints
static QPathEdge::Traversal flip(QPathEdge::Traversal traversal)
#define Q_AUTOTEST_EXPORT
Definition: qglobal.h:1510
quint16 index
int points() const
QPathEdge(int a=-1, int b=-1)
QPathVertex(const QPointF &p=QPointF(), int e=-1)
Operation op
#define QT_END_HEADER
Definition: qglobal.h:137
int edgeCount() const
double angle
QDataBuffer< QPathVertex > m_vertices
void addIntersection(int index, const Intersection &intersection)
int vertexCount() const
bool operator<(const Intersection &o) const
const QRectF & elementBounds(int index) const
QDataBuffer< Intersection > m_intersections
Qt::LayoutDirection direction
int size() const
Definition: qdatabuffer_p.h:83