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]; |

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 | m_next[0][0] = -1; |

300 | m_next[1][0] = -1; |

301 | m_next[0][0] = -1; |

302 | m_next[1][0] = -1; |

303 | } |

304 | |

305 | inline int QPathEdge::next(Traversal traversal, Direction direction) const |

306 | { |

307 | return m_next[int(traversal)][int(direction)]; |

308 | } |

309 | |

310 | inline void QPathEdge::setNext(Traversal traversal, Direction direction, int next) |

311 | { |

312 | m_next[int(traversal)][int(direction)] = next; |

313 | } |

314 | |

315 | inline void QPathEdge::setNext(Direction direction, int next) |

316 | { |

317 | m_next[0][int(direction)] = next; |

318 | m_next[1][int(direction)] = next; |

319 | } |

320 | |

321 | inline QPathEdge::Direction QPathEdge::directionTo(int vertex) const |

322 | { |

323 | return first == vertex ? Backward : Forward; |

324 | } |

325 | |

326 | inline int QPathEdge::vertex(Direction direction) const |

327 | { |

328 | return direction == Backward ? first : second; |

329 | } |

330 | |

331 | inline QPathVertex::QPathVertex(const QPointF &p, int e) |

332 | : edge(e) |

333 | , x(p.x()) |

334 | , y(p.y()) |

335 | { |

336 | } |

337 | |

338 | inline QPathVertex::operator QPointF() const |

339 | { |

340 | return QPointF(x, y); |

341 | } |

342 | |

343 | inline QPathSegments::QPathSegments(int reserve) : |

344 | m_points(reserve), |

345 | m_segments(reserve), |

346 | m_intersections(reserve), |

347 | m_pathId(0) |

348 | { |

349 | } |

350 | |

351 | inline int QPathSegments::segments() const |

352 | { |

353 | return m_segments.size(); |

354 | } |

355 | |

356 | inline int QPathSegments::points() const |

357 | { |

358 | return m_points.size(); |

359 | } |

360 | |

361 | inline const QPointF &QPathSegments::pointAt(int i) const |

362 | { |

363 | return m_points.at(i); |

364 | } |

365 | |

366 | inline int QPathSegments::addPoint(const QPointF &point) |

367 | { |

368 | m_points << point; |

369 | return m_points.size() - 1; |

370 | } |

371 | |

372 | inline const QPathSegments::Segment &QPathSegments::segmentAt(int index) const |

373 | { |

374 | return m_segments.at(index); |

375 | } |

376 | |

377 | inline const QLineF QPathSegments::lineAt(int index) const |

378 | { |

379 | const Segment &segment = m_segments.at(index); |

380 | return QLineF(m_points.at(segment.va), m_points.at(segment.vb)); |

381 | } |

382 | |

383 | inline const QRectF &QPathSegments::elementBounds(int index) const |

384 | { |

385 | return m_segments.at(index).bounds; |

386 | } |

387 | |

388 | inline int QPathSegments::pathId(int index) const |

389 | { |

390 | return m_segments.at(index).path; |

391 | } |

392 | |

393 | inline const QPathSegments::Intersection *QPathSegments::intersectionAt(int index) const |

394 | { |

395 | const int intersection = m_segments.at(index).intersection; |

396 | if (intersection < 0) |

397 | return nullptr; |

398 | else |

399 | return &m_intersections.at(intersection); |

400 | } |

401 | |

402 | inline int QPathSegments::intersections() const |

403 | { |

404 | return m_intersections.size(); |

405 | } |

406 | |

407 | inline void QPathSegments::addIntersection(int index, const Intersection &intersection) |

408 | { |

409 | m_intersections << intersection; |

410 | |

411 | Segment &segment = m_segments.at(index); |

412 | if (segment.intersection < 0) { |

413 | segment.intersection = m_intersections.size() - 1; |

414 | } else { |

415 | Intersection *isect = &m_intersections.at(segment.intersection); |

416 | |

417 | while (isect->next != 0) |

418 | isect += isect->next; |

419 | |

420 | isect->next = (m_intersections.size() - 1) - (isect - m_intersections.data()); |

421 | } |

422 | } |

423 | |

424 | inline int QWingedEdge::edgeCount() const |

425 | { |

426 | return m_edges.size(); |

427 | } |

428 | |

429 | inline QPathEdge *QWingedEdge::edge(int edge) |

430 | { |

431 | return edge < 0 ? nullptr : &m_edges.at(edge); |

432 | } |

433 | |

434 | inline const QPathEdge *QWingedEdge::edge(int edge) const |

435 | { |

436 | return edge < 0 ? nullptr : &m_edges.at(edge); |

437 | } |

438 | |

439 | inline int QWingedEdge::vertexCount() const |

440 | { |

441 | return m_vertices.size(); |

442 | } |

443 | |

444 | inline int QWingedEdge::addVertex(const QPointF &p) |

445 | { |

446 | m_vertices << p; |

447 | return m_vertices.size() - 1; |

448 | } |

449 | |

450 | inline QPathVertex *QWingedEdge::vertex(int vertex) |

451 | { |

452 | return vertex < 0 ? nullptr : &m_vertices.at(vertex); |

453 | } |

454 | |

455 | inline const QPathVertex *QWingedEdge::vertex(int vertex) const |

456 | { |

457 | return vertex < 0 ? nullptr : &m_vertices.at(vertex); |

458 | } |

459 | |

460 | inline QPathEdge::Traversal QWingedEdge::flip(QPathEdge::Traversal traversal) |

461 | { |

462 | return traversal == QPathEdge::RightTraversal ? QPathEdge::LeftTraversal : QPathEdge::RightTraversal; |

463 | } |

464 | |

465 | inline void QWingedEdge::TraversalStatus::flipTraversal() |

466 | { |

467 | traversal = QWingedEdge::flip(traversal); |

468 | } |

469 | |

470 | inline QPathEdge::Direction QWingedEdge::flip(QPathEdge::Direction direction) |

471 | { |

472 | return direction == QPathEdge::Forward ? QPathEdge::Backward : QPathEdge::Forward; |

473 | } |

474 | |

475 | inline void QWingedEdge::TraversalStatus::flipDirection() |

476 | { |

477 | direction = QWingedEdge::flip(direction); |

478 | } |

479 | |

480 | inline void QWingedEdge::TraversalStatus::flip() |

481 | { |

482 | flipDirection(); |

483 | flipTraversal(); |

484 | } |

485 | |

486 | QT_END_NAMESPACE |

487 | |

488 | #endif // QPATHCLIPPER_P_H |

489 |