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