qpathclipper.cpp

Absolute File Name:

/home/qt/qt5_coco/qt5/qtbase/src/gui/painting/qpathclipper.cpp

Source code

Switch to Preprocessed file

Line Source Count

1 /**************************************************************************** -

2 ** -

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 #include "qpathclipper_p.h" -

41 -

42 #include <private/qbezier_p.h> -

43 #include <private/qdatabuffer_p.h> -

44 #include <private/qnumeric_p.h> -

45 #include <qmath.h> -

46 #include <algorithm> -

47 -

48 /** -

49 The algorithm is as follows: -

50 -

51 1. Find all intersections between the two paths (including self-intersections), -

52 and build a winged edge structure of non-intersecting parts. -

53 2. While there are more unhandled edges: -

54 3. Pick a y-coordinate from an unhandled edge. -

55 4. Intersect the horizontal line at y-coordinate with all edges. -

56 5. Traverse intersections left to right deciding whether each subpath should be added or not. -

57 6. If the subpath should be added, traverse the winged-edge structure and add the edges to -

58 a separate winged edge structure. -

59 7. Mark all edges in subpaths crossing the horizontal line as handled. -

60 8. (Optional) Simplify the resulting winged edge structure by merging shared edges. -

61 9. Convert the resulting winged edge structure to a painter path. -

62 */ -

63 -

64 #include <qdebug.h> -

65 -

66 QT_BEGIN_NAMESPACE -

67 -

68 static inline bool fuzzyIsNull(qreal d) -

69 { -

70 if (sizeof(qreal) == sizeof(double)) -

71 return qAbs(d) <= 1e-12; -

72 else -

73 return qAbs(d) <= 1e-5f; -

74 } -

75 -

76 static inline bool comparePoints(const QPointF &a, const QPointF &b) -

77 { -

78 return fuzzyIsNull(a.x() - b.x()) -

79 && fuzzyIsNull(a.y() - b.y()); -

80 } -

81 -

82 //#define QDEBUG_CLIPPER -

83 static qreal dot(const QPointF &a, const QPointF &b) -

84 { -

85 return a.x() * b.x() + a.y() * b.y(); -

86 } -

87 -

88 static void normalize(double &x, double &y) -

89 { -

90 double reciprocal = 1 / qSqrt(x * x + y * y); -

91 x *= reciprocal; -

92 y *= reciprocal; -

93 } -

94 -

95 struct QIntersection -

96 { -

97 qreal alphaA; -

98 qreal alphaB; -

99 -

100 QPointF pos; -

101 }; -

102 -

103 class QIntersectionFinder -

104 { -

105 public: -

106 void produceIntersections(QPathSegments &segments); -

107 bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const; -

108 -

109 private: -

110 bool linesIntersect(const QLineF &a, const QLineF &b) const; -

111 }; -

112 -

113 bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const -

114 { -

115 const QPointF p1 = a.p1(); -

116 const QPointF p2 = a.p2(); -

117 -

118 const QPointF q1 = b.p1(); -

119 const QPointF q2 = b.p2(); -

120 -

121 if (comparePoints(p1, p2) || comparePoints(q1, q2)) -

122 return false; -

123 -

124 const bool p1_equals_q1 = comparePoints(p1, q1); -

125 const bool p2_equals_q2 = comparePoints(p2, q2); -

126 -

127 if (p1_equals_q1 && p2_equals_q2) -

128 return true; -

129 -

130 const bool p1_equals_q2 = comparePoints(p1, q2); -

131 const bool p2_equals_q1 = comparePoints(p2, q1); -

132 -

133 if (p1_equals_q2 && p2_equals_q1) -

134 return true; -

135 -

136 const QPointF pDelta = p2 - p1; -

137 const QPointF qDelta = q2 - q1; -

138 -

139 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x(); -

140 -

141 if (qFuzzyIsNull(par)) { -

142 const QPointF normal(-pDelta.y(), pDelta.x()); -

143 -

144 // coinciding? -

145 if (qFuzzyIsNull(dot(normal, q1 - p1))) { -

146 const qreal dp = dot(pDelta, pDelta); -

147 -

148 const qreal tq1 = dot(pDelta, q1 - p1); -

149 const qreal tq2 = dot(pDelta, q2 - p1); -

150 -

151 if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp)) -

152 return true; -

153 -

154 const qreal dq = dot(qDelta, qDelta); -

155 -

156 const qreal tp1 = dot(qDelta, p1 - q1); -

157 const qreal tp2 = dot(qDelta, p2 - q1); -

158 -

159 if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq)) -

160 return true; -

161 } -

162 -

163 return false; -

164 } -

165 -

166 const qreal invPar = 1 / par; -

167 -

168 const qreal tp = (qDelta.y() * (q1.x() - p1.x()) - -

169 qDelta.x() * (q1.y() - p1.y())) * invPar; -

170 -

171 if (tp < 0 || tp > 1) -

172 return false; -

173 -

174 const qreal tq = (pDelta.y() * (q1.x() - p1.x()) - -

175 pDelta.x() * (q1.y() - p1.y())) * invPar; -

176 -

177 return tq >= 0 && tq <= 1; -

178 } -

179 -

180 bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const -

181 { -

182 if (a.segments() == 0 || b.segments() == 0) -

183 return false; -

184 -

185 const QRectF &rb0 = b.elementBounds(0); -

186 -

187 qreal minX = rb0.left(); -

188 qreal minY = rb0.top(); -

189 qreal maxX = rb0.right(); -

190 qreal maxY = rb0.bottom(); -

191 -

192 for (int i = 1; i < b.segments(); ++i) { -

193 const QRectF &r = b.elementBounds(i); -

194 minX = qMin(minX, r.left()); -

195 minY = qMin(minY, r.top()); -

196 maxX = qMax(maxX, r.right()); -

197 maxY = qMax(maxY, r.bottom()); -

198 } -

199 -

200 QRectF rb(minX, minY, maxX - minX, maxY - minY); -

201 -

202 for (int i = 0; i < a.segments(); ++i) { -

203 const QRectF &r1 = a.elementBounds(i); -

204 -

205 if (r1.left() > rb.right() || rb.left() > r1.right()) -

206 continue; -

207 if (r1.top() > rb.bottom() || rb.top() > r1.bottom()) -

208 continue; -

209 -

210 for (int j = 0; j < b.segments(); ++j) { -

211 const QRectF &r2 = b.elementBounds(j); -

212 -

213 if (r1.left() > r2.right() || r2.left() > r1.right()) -

214 continue; -

215 if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) -

216 continue; -

217 -

218 if (linesIntersect(a.lineAt(i), b.lineAt(j))) -

219 return true; -

220 } -

221 } -

222 -

223 return false; -

224 } -

225 -

226 namespace { -

227 struct TreeNode -

228 { -

229 qreal splitLeft; -

230 qreal splitRight; -

231 bool leaf; -

232 -

233 int lowestLeftIndex; -

234 int lowestRightIndex; -

235 -

236 union { -

237 struct { -

238 int first; -

239 int last; -

240 } interval; -

241 struct { -

242 int left; -

243 int right; -

244 } children; -

245 } index; -

246 }; -

247 -

248 struct RectF -

249 { -

250 qreal x1; -

251 qreal y1; -

252 qreal x2; -

253 qreal y2; -

254 }; -

255 -

256 class SegmentTree -

257 { -

258 public: -

259 SegmentTree(QPathSegments &segments); -

260 -

261 void produceIntersections(int segment); -

262 -

263 private: -

264 TreeNode buildTree(int first, int last, int depth, const RectF &bounds); -

265 -

266 void produceIntersectionsLeaf(const TreeNode &node, int segment); -

267 void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis); -

268 void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections); -

269 -

270 QPathSegments &m_segments; -

271 QVector<int> m_index; -

272 -

273 RectF m_bounds; -

274 -

275 QVector<TreeNode> m_tree; -

276 QDataBuffer<QIntersection> m_intersections; -

277 }; -

278 -

279 SegmentTree::SegmentTree(QPathSegments &segments) -

280 : m_segments(segments), -

281 m_intersections(0) -

282 { -

283 m_bounds.x1 = qt_inf(); -

284 m_bounds.y1 = qt_inf(); -

285 m_bounds.x2 = -qt_inf(); -

286 m_bounds.y2 = -qt_inf(); -

287 -

288 m_index.resize(m_segments.segments()); -

289 -

290 for (int i = 0; i < m_index.size(); ++i) { -

291 m_index[i] = i; -

292 -

293 const QRectF &segmentBounds = m_segments.elementBounds(i); -

294 -

295 if (segmentBounds.left() < m_bounds.x1) -

296 m_bounds.x1 = segmentBounds.left(); -

297 if (segmentBounds.top() < m_bounds.y1) -

298 m_bounds.y1 = segmentBounds.top(); -

299 if (segmentBounds.right() > m_bounds.x2) -

300 m_bounds.x2 = segmentBounds.right(); -

301 if (segmentBounds.bottom() > m_bounds.y2) -

302 m_bounds.y2 = segmentBounds.bottom(); -

303 } -

304 -

305 m_tree.resize(1); -

306 -

307 TreeNode root = buildTree(0, m_index.size(), 0, m_bounds); -

308 m_tree[0] = root; -

309 } -

310 -

311 static inline qreal coordinate(const QPointF &pos, int axis) -

312 { -

313 return axis == 0 ? pos.x() : pos.y(); -

314 } -

315 -

316 TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds) -

317 { -

318 if (depth >= 24 || (last - first) <= 10) { -

319 TreeNode node; -

320 node.leaf = true; -

321 node.index.interval.first = first; -

322 node.index.interval.last = last; -

323 -

324 return node; -

325 } -

326 -

327 int splitAxis = (depth & 1); -

328 -

329 TreeNode node; -

330 node.leaf = false; -

331 -

332 qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]); -

333 -

334 node.splitLeft = (&bounds.x1)[splitAxis]; -

335 node.splitRight = (&bounds.x2)[splitAxis]; -

336 -

337 node.lowestLeftIndex = INT_MAX; -

338 node.lowestRightIndex = INT_MAX; -

339 -

340 const int treeSize = m_tree.size(); -

341 -

342 node.index.children.left = treeSize; -

343 node.index.children.right = treeSize + 1; -

344 -

345 m_tree.resize(treeSize + 2); -

346 -

347 int l = first; -

348 int r = last - 1; -

349 -

350 // partition into left and right sets -

351 while (l <= r) { -

352 const int index = m_index.at(l); -

353 const QRectF &segmentBounds = m_segments.elementBounds(index); -

354 -

355 qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis); -

356 -

357 if (coordinate(segmentBounds.center(), splitAxis) < split) { -

358 qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis); -

359 if (highCoordinate > node.splitLeft) -

360 node.splitLeft = highCoordinate; -

361 if (index < node.lowestLeftIndex) -

362 node.lowestLeftIndex = index; -

363 ++l; -

364 } else { -

365 if (lowCoordinate < node.splitRight) -

366 node.splitRight = lowCoordinate; -

367 if (index < node.lowestRightIndex) -

368 node.lowestRightIndex = index; -

369 qSwap(m_index[l], m_index[r]); -

370 --r; -

371 } -

372 } -

373 -

374 RectF lbounds = bounds; -

375 (&lbounds.x2)[splitAxis] = node.splitLeft; -

376 -

377 RectF rbounds = bounds; -

378 (&rbounds.x1)[splitAxis] = node.splitRight; -

379 -

380 TreeNode left = buildTree(first, l, depth + 1, lbounds); -

381 m_tree[node.index.children.left] = left; -

382 -

383 TreeNode right = buildTree(l, last, depth + 1, rbounds); -

384 m_tree[node.index.children.right] = right; -

385 -

386 return node; -

387 } -

388 -

389 void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections) -

390 { -

391 const QPointF p1 = a.p1(); -

392 const QPointF p2 = a.p2(); -

393 -

394 const QPointF q1 = b.p1(); -

395 const QPointF q2 = b.p2(); -

396 -

397 if (comparePoints(p1, p2) || comparePoints(q1, q2)) -

398 return; -

399 -

400 const bool p1_equals_q1 = comparePoints(p1, q1); -

401 const bool p2_equals_q2 = comparePoints(p2, q2); -

402 -

403 if (p1_equals_q1 && p2_equals_q2) -

404 return; -

405 -

406 const bool p1_equals_q2 = comparePoints(p1, q2); -

407 const bool p2_equals_q1 = comparePoints(p2, q1); -

408 -

409 if (p1_equals_q2 && p2_equals_q1) -

410 return; -

411 -

412 const QPointF pDelta = p2 - p1; -

413 const QPointF qDelta = q2 - q1; -

414 -

415 const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x(); -

416 -

417 if (qFuzzyIsNull(par)) { -

418 const QPointF normal(-pDelta.y(), pDelta.x()); -

419 -

420 // coinciding? -

421 if (qFuzzyIsNull(dot(normal, q1 - p1))) { -

422 const qreal invDp = 1 / dot(pDelta, pDelta); -

423 -

424 const qreal tq1 = dot(pDelta, q1 - p1) * invDp; -

425 const qreal tq2 = dot(pDelta, q2 - p1) * invDp; -

426 -

427 if (tq1 > 0 && tq1 < 1) { -

428 QIntersection intersection; -

429 intersection.alphaA = tq1; -

430 intersection.alphaB = 0; -

431 intersection.pos = q1; -

432 intersections.add(intersection); -

433 } -

434 -

435 if (tq2 > 0 && tq2 < 1) { -

436 QIntersection intersection; -

437 intersection.alphaA = tq2; -

438 intersection.alphaB = 1; -

439 intersection.pos = q2; -

440 intersections.add(intersection); -

441 } -

442 -

443 const qreal invDq = 1 / dot(qDelta, qDelta); -

444 -

445 const qreal tp1 = dot(qDelta, p1 - q1) * invDq; -

446 const qreal tp2 = dot(qDelta, p2 - q1) * invDq; -

447 -

448 if (tp1 > 0 && tp1 < 1) { -

449 QIntersection intersection; -

450 intersection.alphaA = 0; -

451 intersection.alphaB = tp1; -

452 intersection.pos = p1; -

453 intersections.add(intersection); -

454 } -

455 -

456 if (tp2 > 0 && tp2 < 1) { -

457 QIntersection intersection; -

458 intersection.alphaA = 1; -

459 intersection.alphaB = tp2; -

460 intersection.pos = p2; -

461 intersections.add(intersection); -

462 } -

463 } -

464 -

465 return; -

466 } -

467 -

468 // if the lines are not parallel and share a common end point, then they -

469 // don't intersect -

470 if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2) -

471 return; -

472 -

473 -

474 const qreal tp = (qDelta.y() * (q1.x() - p1.x()) - -

475 qDelta.x() * (q1.y() - p1.y())) / par; -

476 const qreal tq = (pDelta.y() * (q1.x() - p1.x()) - -

477 pDelta.x() * (q1.y() - p1.y())) / par; -

478 -

479 if (tp<0 || tp>1 || tq<0 || tq>1) -

480 return; -

481 -

482 const bool p_zero = qFuzzyIsNull(tp); -

483 const bool p_one = qFuzzyIsNull(tp - 1); -

484 -

485 const bool q_zero = qFuzzyIsNull(tq); -

486 const bool q_one = qFuzzyIsNull(tq - 1); -

487 -

488 if ((q_zero || q_one) && (p_zero || p_one)) -

489 return; -

490 -

491 QPointF pt; -

492 if (p_zero) { -

493 pt = p1; -

494 } else if (p_one) { -

495 pt = p2; -

496 } else if (q_zero) { -

497 pt = q1; -

498 } else if (q_one) { -

499 pt = q2; -

500 } else { -

501 pt = q1 + (q2 - q1) * tq; -

502 } -

503 -

504 QIntersection intersection; -

505 intersection.alphaA = tp; -

506 intersection.alphaB = tq; -

507 intersection.pos = pt; -

508 intersections.add(intersection); -

509 } -

510 -

511 void SegmentTree::produceIntersections(int segment) -

512 { -

513 const QRectF &segmentBounds = m_segments.elementBounds(segment); -

514 -

515 RectF sbounds; -

516 sbounds.x1 = segmentBounds.left(); -

517 sbounds.y1 = segmentBounds.top(); -

518 sbounds.x2 = segmentBounds.right(); -

519 sbounds.y2 = segmentBounds.bottom(); -

520 -

521 produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0); -

522 } -

523 -

524 void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment) -

525 { -

526 const QRectF &r1 = m_segments.elementBounds(segment); -

527 const QLineF lineA = m_segments.lineAt(segment); -

528 -

529 for (int i = node.index.interval.first; i < node.index.interval.last; ++i) { -

530 const int other = m_index.at(i); -

531 if (other >= segment) -

532 continue; -

533 -

534 const QRectF &r2 = m_segments.elementBounds(other); -

535 -

536 if (r1.left() > r2.right() || r2.left() > r1.right()) -

537 continue; -

538 if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) -

539 continue; -

540 -

541 m_intersections.reset(); -

542 -

543 const QLineF lineB = m_segments.lineAt(other); -

544 -

545 intersectLines(lineA, lineB, m_intersections); -

546 -

547 for (int k = 0; k < m_intersections.size(); ++k) { -

548 QPathSegments::Intersection i_isect, j_isect; -

549 i_isect.t = m_intersections.at(k).alphaA; -

550 j_isect.t = m_intersections.at(k).alphaB; -

551 -

552 i_isect.vertex = j_isect.vertex = m_segments.addPoint(m_intersections.at(k).pos); -

553 -

554 i_isect.next = 0; -

555 j_isect.next = 0; -

556 -

557 m_segments.addIntersection(segment, i_isect); -

558 m_segments.addIntersection(other, j_isect); -

559 } -

560 } -

561 } -

562 -

563 void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis) -

564 { -

565 if (node.leaf) { -

566 produceIntersectionsLeaf(node, segment); -

567 return; -

568 } -

569 -

570 RectF lbounds = nodeBounds; -

571 (&lbounds.x2)[axis] = node.splitLeft; -

572 -

573 RectF rbounds = nodeBounds; -

574 (&rbounds.x1)[axis] = node.splitRight; -

575 -

576 if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft) -

577 produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis); -

578 -

579 if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight) -

580 produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis); -

581 } -

582 -

583 } -

584 -

585 void QIntersectionFinder::produceIntersections(QPathSegments &segments) -

586 { -

587 SegmentTree tree(segments); -

588 -

589 for (int i = 0; i < segments.segments(); ++i) -

590 tree.produceIntersections(i); -

591 } -

592 -

593 class QKdPointTree -

594 { -

595 public: -

596 enum Traversal { -

597 TraverseBoth, -

598 TraverseLeft, -

599 TraverseRight, -

600 TraverseNone -

601 }; -

602 -

603 struct Node { -

604 int point; -

605 int id; -

606 -

607 Node *left; -

608 Node *right; -

609 }; -

610 -

611 QKdPointTree(const QPathSegments &segments) -

612 : m_segments(&segments) -

613 , m_nodes(m_segments->points()) -

614 , m_id(0) -

615 { -

616 m_nodes.resize(m_segments->points()); -

617 -

618 for (int i = 0; i < m_nodes.size(); ++i) { -

619 m_nodes.at(i).point = i; -

620 m_nodes.at(i).id = -1; -

621 } -

622 -

623 m_rootNode = build(0, m_nodes.size()); -

624 } -

625 -

626 int build(int begin, int end, int depth = 0); -

627 -

628 Node *rootNode() -

629 { -

630 return &m_nodes.at(m_rootNode); -

631 } -

632 -

633 inline int nextId() -

634 { -

635 return m_id++; -

636 } -

637 -

638 private: -

639 const QPathSegments *m_segments; -

640 QDataBuffer<Node> m_nodes; -

641 -

642 int m_rootNode; -

643 int m_id; -

644 }; -

645 -

646 template <typename T> -

647 void qTraverseKdPointTree(QKdPointTree::Node &node, T &t, int depth = 0) -

648 { -

649 QKdPointTree::Traversal status = t(node, depth); -

650 -

651 const bool traverseRight = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseRight); -

652 const bool traverseLeft = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseLeft); -

653 -

654 if (traverseLeft && node.left) -

655 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.left, t, depth + 1); -

656 -

657 if (traverseRight && node.right) -

658 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.right, t, depth + 1); -

659 } -

660 -

661 static inline qreal component(const QPointF &point, unsigned int i) -

662 { -

663 Q_ASSERT(i < 2); -

664 const qreal components[] = { point.x(), point.y() }; -

665 return components[i]; -

666 } -

667 -

668 int QKdPointTree::build(int begin, int end, int depth) -

669 { -

670 Q_ASSERT(end > begin); -

671 -

672 const qreal pivot = component(m_segments->pointAt(m_nodes.at(begin).point), depth & 1); -

673 -

674 int first = begin + 1; -

675 int last = end - 1; -

676 -

677 while (first <= last) { -

678 const qreal value = component(m_segments->pointAt(m_nodes.at(first).point), depth & 1); -

679 -

680 if (value < pivot) -

681 ++first; -

682 else { -

683 qSwap(m_nodes.at(first), m_nodes.at(last)); -

684 --last; -

685 } -

686 } -

687 -

688 qSwap(m_nodes.at(last), m_nodes.at(begin)); -

689 -

690 if (last > begin) -

691 m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1)); -

692 else -

693 m_nodes.at(last).left = 0; -

694 -

695 if (last + 1 < end) -

696 m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1)); -

697 else -

698 m_nodes.at(last).right = 0; -

699 -

700 return last; -

701 } -

702 -

703 class QKdPointFinder -

704 { -

705 public: -

706 QKdPointFinder(int point, const QPathSegments &segments, QKdPointTree &tree) -

707 : m_result(-1) -

708 , m_segments(&segments) -

709 , m_tree(&tree) -

710 { -

711 pointComponents[0] = segments.pointAt(point).x(); -

712 pointComponents[1] = segments.pointAt(point).y(); -

713 } -

714 -

715 inline QKdPointTree::Traversal operator()(QKdPointTree::Node &node, int depth) -

716 { -

717 if (m_result != -1) -

718 return QKdPointTree::TraverseNone; -

719 -

720 const QPointF &nodePoint = m_segments->pointAt(node.point); -

721 -

722 const qreal pivotComponents[] = { nodePoint.x(), nodePoint.y() }; -

723 -

724 const qreal pivot = pivotComponents[depth & 1]; -

725 const qreal value = pointComponents[depth & 1]; -

726 -

727 if (fuzzyIsNull(pivot - value)) { -

728 const qreal pivot2 = pivotComponents[(depth + 1) & 1]; -

729 const qreal value2 = pointComponents[(depth + 1) & 1]; -

730 -

731 if (fuzzyIsNull(pivot2 - value2)) { -

732 if (node.id < 0) -

733 node.id = m_tree->nextId(); -

734 -

735 m_result = node.id; -

736 return QKdPointTree::TraverseNone; -

737 } else -

738 return QKdPointTree::TraverseBoth; -

739 } else if (value < pivot) { -

740 return QKdPointTree::TraverseLeft; -

741 } else { -

742 return QKdPointTree::TraverseRight; -

743 } -

744 } -

745 -

746 int result() const -

747 { -

748 return m_result; -

749 } -

750 -

751 private: -

752 qreal pointComponents[2]; -

753 int m_result; -

754 const QPathSegments *m_segments; -

755 QKdPointTree *m_tree; -

756 }; -

757 -

758 // merge all points that are within qFuzzyCompare range of each other -

759 void QPathSegments::mergePoints() -

760 { -

761 QKdPointTree tree(*this); -

762 -

763 if (tree.rootNode()) { -

764 QDataBuffer<QPointF> mergedPoints(points()); -

765 QDataBuffer<int> pointIndices(points()); -

766 -

767 for (int i = 0; i < points(); ++i) { -

768 QKdPointFinder finder(i, *this, tree); -

769 QT_PREPEND_NAMESPACE(qTraverseKdPointTree<QKdPointFinder>)(*tree.rootNode(), finder); -

770 -

771 Q_ASSERT(finder.result() != -1); -

772 -

773 if (finder.result() >= mergedPoints.size()) -

774 mergedPoints << m_points.at(i); -

775 -

776 pointIndices << finder.result(); -

777 } -

778 -

779 for (int i = 0; i < m_segments.size(); ++i) { -

780 m_segments.at(i).va = pointIndices.at(m_segments.at(i).va); -

781 m_segments.at(i).vb = pointIndices.at(m_segments.at(i).vb); -

782 } -

783 -

784 for (int i = 0; i < m_intersections.size(); ++i) -

785 m_intersections.at(i).vertex = pointIndices.at(m_intersections.at(i).vertex); -

786 -

787 m_points.swap(mergedPoints); -

788 } -

789 } -

790 -

791 void QWingedEdge::intersectAndAdd() -

792 { -

793 QIntersectionFinder finder; -

794 finder.produceIntersections(m_segments); -

795 -

796 m_segments.mergePoints(); -

797 -

798 for (int i = 0; i < m_segments.points(); ++i) -

799 addVertex(m_segments.pointAt(i)); -

800 -

801 QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments()); -

802 for (int i = 0; i < m_segments.segments(); ++i) { -

803 intersections.reset(); -

804 -

805 int pathId = m_segments.pathId(i); -

806 -

807 const QPathSegments::Intersection *isect = m_segments.intersectionAt(i); -

808 while (isect) { -

809 intersections << *isect; -

810 -

811 if (isect->next) { -

812 isect += isect->next; -

813 } else { -

814 isect = 0; -

815 } -

816 } -

817 -

818 std::sort(intersections.data(), intersections.data() + intersections.size()); -

819 -

820 int first = m_segments.segmentAt(i).va; -

821 int second = m_segments.segmentAt(i).vb; -

822 -

823 int last = first; -

824 for (int j = 0; j < intersections.size(); ++j) { -

825 const QPathSegments::Intersection &isect = intersections.at(j); -

826 -

827 QPathEdge *ep = edge(addEdge(last, isect.vertex)); -

828 -

829 if (ep) { -

830 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1; -

831 if (pathId == 0) -

832 ep->windingA += dir; -

833 else -

834 ep->windingB += dir; -

835 } -

836 -

837 last = isect.vertex; -

838 } -

839 -

840 QPathEdge *ep = edge(addEdge(last, second)); -

841 -

842 if (ep) { -

843 const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1; -

844 if (pathId == 0) -

845 ep->windingA += dir; -

846 else -

847 ep->windingB += dir; -

848 } -

849 } -

850 } -

851 -

852 QWingedEdge::QWingedEdge() : -

853 m_edges(0), -

854 m_vertices(0), -

855 m_segments(0) -

856 { -

857 } -

858 -

859 QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) : -

860 m_edges(subject.elementCount()), -

861 m_vertices(subject.elementCount()), -

862 m_segments(subject.elementCount()) -

863 { -

864 m_segments.setPath(subject); -

865 m_segments.addPath(clip); -

866 -

867 intersectAndAdd(); -

868 } -

869 -

870 QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const -

871 { -

872 const QPathEdge *sp = edge(status.edge); -

873 Q_ASSERT(sp); -

874 -

875 TraversalStatus result; -

876 result.edge = sp->next(status.traversal, status.direction); -

877 result.traversal = status.traversal; -

878 result.direction = status.direction; -

879 -

880 const QPathEdge *rp = edge(result.edge); -

881 Q_ASSERT(rp); -

882 -

883 if (sp->vertex(status.direction) == rp->vertex(status.direction)) -

884 result.flip(); -

885 -

886 return result; -

887 } -

888 -

889 static bool isLine(const QBezier &bezier) -

890 { -

891 const bool equal_1_2 = comparePoints(bezier.pt1(), bezier.pt2()); -

892 const bool equal_2_3 = comparePoints(bezier.pt2(), bezier.pt3()); -

893 const bool equal_3_4 = comparePoints(bezier.pt3(), bezier.pt4()); -

894 -

895 // point? -

896 if (equal_1_2 && equal_2_3 && equal_3_4) -

897 return true; -

898 -

899 if (comparePoints(bezier.pt1(), bezier.pt4())) -

900 return equal_1_2 || equal_3_4; -

901 -

902 return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4); -

903 } -

904 -

905 void QPathSegments::setPath(const QPainterPath &path) -

906 { -

907 m_points.reset(); -

908 m_intersections.reset(); -

909 m_segments.reset(); -

910 -

911 m_pathId = 0; -

912 -

913 addPath(path); -

914 } -

915 -

916 void QPathSegments::addPath(const QPainterPath &path) -

917 { -

918 int firstSegment = m_segments.size(); -

919 -

920 bool hasMoveTo = false; -

921 int lastMoveTo = 0; -

922 int last = 0; -

923 for (int i = 0; i < path.elementCount(); ++i) { -

924 int current = m_points.size(); -

925 -

926 QPointF currentPoint; -

927 if (path.elementAt(i).type == QPainterPath::CurveToElement) -

928 currentPoint = path.elementAt(i+2); -

929 else -

930 currentPoint = path.elementAt(i); -

931 -

932 if (i > 0 && comparePoints(m_points.at(lastMoveTo), currentPoint)) -

933 current = lastMoveTo; -

934 else -

935 m_points << currentPoint; -

936 -

937 switch (path.elementAt(i).type) { -

938 case QPainterPath::MoveToElement: -

939 if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo))) -

940 m_segments << Segment(m_pathId, last, lastMoveTo); -

941 hasMoveTo = true; -

942 last = lastMoveTo = current; -

943 break; -

944 case QPainterPath::LineToElement: -

945 m_segments << Segment(m_pathId, last, current); -

946 last = current; -

947 break; -

948 case QPainterPath::CurveToElement: -

949 { -

950 QBezier bezier = QBezier::fromPoints(m_points.at(last), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2)); -

951 if (isLine(bezier)) { -

952 m_segments << Segment(m_pathId, last, current); -

953 } else { -

954 QRectF bounds = bezier.bounds(); -

955 -

956 // threshold based on similar algorithm as in qtriangulatingstroker.cpp -

957 int threshold = qMin<float>(64, qMax(bounds.width(), bounds.height()) * (2 * qreal(3.14) / 6)); -

958 -

959 if (threshold < 3) threshold = 3; -

960 qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1); -

961 -

962 for (int t = 1; t < threshold - 1; ++t) { -

963 currentPoint = bezier.pointAt(t * one_over_threshold_minus_1); -

964 -

965 int index = m_points.size(); -

966 m_segments << Segment(m_pathId, last, index); -

967 last = index; -

968 -

969 m_points << currentPoint; -

970 } -

971 -

972 m_segments << Segment(m_pathId, last, current); -

973 } -

974 } -

975 last = current; -

976 i += 2; -

977 break; -

978 default: -

979 Q_ASSERT(false); -

980 break; -

981 } -

982 } -

983 -

984 if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo))) -

985 m_segments << Segment(m_pathId, last, lastMoveTo); -

986 -

987 for (int i = firstSegment; i < m_segments.size(); ++i) { -

988 const QLineF line = lineAt(i); -

989 -

990 qreal x1 = line.p1().x(); -

991 qreal y1 = line.p1().y(); -

992 qreal x2 = line.p2().x(); -

993 qreal y2 = line.p2().y(); -

994 -

995 if (x2 < x1) -

996 qSwap(x1, x2); -

997 if (y2 < y1) -

998 qSwap(y1, y2); -

999 -

1000 m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1); -

1001 } -

1002 -

1003 ++m_pathId; -

1004 } -

1005 -

1006 qreal QWingedEdge::delta(int vertex, int a, int b) const -

1007 { -

1008 const QPathEdge *ap = edge(a); -

1009 const QPathEdge *bp = edge(b); -

1010 -

1011 double a_angle = ap->angle; -

1012 double b_angle = bp->angle; -

1013 -

1014 if (vertex == ap->second) -

1015 a_angle = ap->invAngle; -

1016 -

1017 if (vertex == bp->second) -

1018 b_angle = bp->invAngle; -

1019 -

1020 double result = b_angle - a_angle; -

1021 -

1022 if (result >= 128.) -

1023 return result - 128.; -

1024 else if (result < 0) -

1025 return result + 128.; -

1026 else -

1027 return result; -

1028 } -

1029 -

1030 QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const -

1031 { -

1032 const QPathVertex *vp = vertex(vi); -

1033 -

1034 Q_ASSERT(vp); -

1035 Q_ASSERT(ei >= 0); -

1036 Q_ASSERT(vp->edge >= 0); -

1037 -

1038 int position = vp->edge; -

1039 qreal d = 128.; -

1040 -

1041 TraversalStatus status; -

1042 status.direction = edge(vp->edge)->directionTo(vi); -

1043 status.traversal = QPathEdge::RightTraversal; -

1044 status.edge = vp->edge; -

1045 -

1046 #ifdef QDEBUG_CLIPPER -

1047 const QPathEdge *ep = edge(ei); -

1048 qDebug() << "Finding insert status for edge" << ei << "at vertex" << QPointF(*vp) << ", angles: " << ep->angle << ep->invAngle; -

1049 #endif -

1050 -

1051 do { -

1052 status = next(status); -

1053 status.flip(); -

1054 -

1055 Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi); -

1056 qreal d2 = delta(vi, ei, status.edge); -

1057 -

1058 #ifdef QDEBUG_CLIPPER -

1059 const QPathEdge *op = edge(status.edge); -

1060 qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle; -

1061 #endif -

1062 -

1063 if (d2 < d) { -

1064 position = status.edge; -

1065 d = d2; -

1066 } -

1067 } while (status.edge != vp->edge); -

1068 -

1069 status.traversal = QPathEdge::LeftTraversal; -

1070 status.direction = QPathEdge::Forward; -

1071 status.edge = position; -

1072 -

1073 if (edge(status.edge)->vertex(status.direction) != vi) -

1074 status.flip(); -

1075 -

1076 #ifdef QDEBUG_CLIPPER -

1077 qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge; -

1078 #endif -

1079 -

1080 Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi); -

1081 -

1082 return status; -

1083 } -

1084 -

1085 void QWingedEdge::removeEdge(int ei) -

1086 { -

1087 QPathEdge *ep = edge(ei); -

1088 -

1089 TraversalStatus status; -

1090 status.direction = QPathEdge::Forward; -

1091 status.traversal = QPathEdge::RightTraversal; -

1092 status.edge = ei; -

1093 -

1094 TraversalStatus forwardRight = next(status); -

1095 forwardRight.flipDirection(); -

1096 -

1097 status.traversal = QPathEdge::LeftTraversal; -

1098 TraversalStatus forwardLeft = next(status); -

1099 forwardLeft.flipDirection(); -

1100 -

1101 status.direction = QPathEdge::Backward; -

1102 TraversalStatus backwardLeft = next(status); -

1103 backwardLeft.flipDirection(); -

1104 -

1105 status.traversal = QPathEdge::RightTraversal; -

1106 TraversalStatus backwardRight = next(status); -

1107 backwardRight.flipDirection(); -

1108 -

1109 edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge); -

1110 edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge); -

1111 -

1112 edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge); -

1113 edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge); -

1114 -

1115 ep->setNext(QPathEdge::Forward, ei); -

1116 ep->setNext(QPathEdge::Backward, ei); -

1117 -

1118 QPathVertex *a = vertex(ep->first); -

1119 QPathVertex *b = vertex(ep->second); -

1120 -

1121 a->edge = backwardRight.edge; -

1122 b->edge = forwardRight.edge; -

1123 } -

1124 -

1125 static int commonEdge(const QWingedEdge &list, int a, int b) -

1126 { -

1127 const QPathVertex *ap = list.vertex(a); -

1128 Q_ASSERT(ap); -

1129 -

1130 const QPathVertex *bp = list.vertex(b); -

1131 Q_ASSERT(bp); -

1132 -

1133 if (ap->edge < 0 || bp->edge < 0) -

1134 return -1; -

1135 -

1136 QWingedEdge::TraversalStatus status; -

1137 status.edge = ap->edge; -

1138 status.direction = list.edge(status.edge)->directionTo(a); -

1139 status.traversal = QPathEdge::RightTraversal; -

1140 -

1141 do { -

1142 const QPathEdge *ep = list.edge(status.edge); -

1143 -

1144 if ((ep->first == a && ep->second == b) -

1145 || (ep->first == b && ep->second == a)) -

1146 return status.edge; -

1147 -

1148 status = list.next(status); -

1149 status.flip(); -

1150 } while (status.edge != ap->edge); -

1151 -

1152 return -1; -

1153 } -

1154 -

1155 static double computeAngle(const QPointF &v) -

1156 { -

1157 #if 1 -

1158 if (v.x() == 0) { -

1159 return v.y() <= 0 ? 0 : 64.; -

1160 } else if (v.y() == 0) { -

1161 return v.x() <= 0 ? 32. : 96.; -

1162 } -

1163 -

1164 double vx = v.x(); -

1165 double vy = v.y(); -

1166 normalize(vx, vy); -

1167 if (vy < 0) { -

1168 if (vx < 0) { // 0 - 32 -

1169 return -32. * vx; -

1170 } else { // 96 - 128 -

1171 return 128. - 32. * vx; -

1172 } -

1173 } else { // 32 - 96 -

1174 return 64. + 32. * vx; -

1175 } -

1176 #else -

1177 // doesn't seem to be robust enough -

1178 return qAtan2(v.x(), v.y()) + Q_PI; -

1179 #endif -

1180 } -

1181 -

1182 int QWingedEdge::addEdge(const QPointF &a, const QPointF &b) -

1183 { -

1184 int fi = insert(a); -

1185 int si = insert(b); -

1186 -

1187 return addEdge(fi, si); -

1188 } -

1189 -

1190 int QWingedEdge::addEdge(int fi, int si) -

1191 { -

1192 if (fi == si) -

1193 return -1; -

1194 -

1195 int common = commonEdge(*this, fi, si); -

1196 if (common >= 0) -

1197 return common; -

1198 -

1199 m_edges << QPathEdge(fi, si); -

1200 -

1201 int ei = m_edges.size() - 1; -

1202 -

1203 QPathVertex *fp = vertex(fi); -

1204 QPathVertex *sp = vertex(si); -

1205 -

1206 QPathEdge *ep = edge(ei); -

1207 -

1208 const QPointF tangent = QPointF(*sp) - QPointF(*fp); -

1209 ep->angle = computeAngle(tangent); -

1210 ep->invAngle = ep->angle + 64; -

1211 if (ep->invAngle >= 128) -

1212 ep->invAngle -= 128; -

1213 -

1214 QPathVertex *vertices[2] = { fp, sp }; -

1215 QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward }; -

1216 -

1217 #ifdef QDEBUG_CLIPPER -

1218 printf("** Adding edge %d / vertices: %.07f %.07f, %.07f %.07f\n", ei, fp->x, fp->y, sp->x, sp->y); -

1219 #endif -

1220 -

1221 for (int i = 0; i < 2; ++i) { -

1222 QPathVertex *vp = vertices[i]; -

1223 if (vp->edge < 0) { -

1224 vp->edge = ei; -

1225 ep->setNext(dirs[i], ei); -

1226 } else { -

1227 int vi = ep->vertex(dirs[i]); -

1228 Q_ASSERT(vertex(vi) == vertices[i]); -

1229 -

1230 TraversalStatus os = findInsertStatus(vi, ei); -

1231 QPathEdge *op = edge(os.edge); -

1232 -

1233 Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]); -

1234 -

1235 TraversalStatus ns = next(os); -

1236 ns.flipDirection(); -

1237 QPathEdge *np = edge(ns.edge); -

1238 -

1239 op->setNext(os.traversal, os.direction, ei); -

1240 np->setNext(ns.traversal, ns.direction, ei); -

1241 -

1242 int oe = os.edge; -

1243 int ne = ns.edge; -

1244 -

1245 os = next(os); -

1246 ns = next(ns); -

1247 -

1248 os.flipDirection(); -

1249 ns.flipDirection(); -

1250 -

1251 Q_ASSERT(os.edge == ei); -

1252 Q_ASSERT(ns.edge == ei); -

1253 -

1254 ep->setNext(os.traversal, os.direction, oe); -

1255 ep->setNext(ns.traversal, ns.direction, ne); -

1256 } -

1257 } -

1258 -

1259 Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Forward) >= 0); -

1260 Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Backward) >= 0); -

1261 Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Forward) >= 0); -

1262 Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0); -

1263 -

1264 return ei; -

1265 } -

1266 -

1267 int QWingedEdge::insert(const QPathVertex &vertex) -

1268 { -

1269 if (!m_vertices.isEmpty()) { -

1270 const QPathVertex &last = m_vertices.last(); -

1271 if (vertex.x == last.x && vertex.y == last.y) -

1272 return m_vertices.size() - 1; -

1273 -

1274 for (int i = 0; i < m_vertices.size(); ++i) { -

1275 const QPathVertex &v = m_vertices.at(i); -

1276 if (qFuzzyCompare(v.x, vertex.x) && qFuzzyCompare(v.y, vertex.y)) { -

1277 return i; -

1278 } -

1279 } -

1280 } -

1281 -

1282 m_vertices << vertex; -

1283 return m_vertices.size() - 1; -

1284 } -

1285 -

1286 static void addLineTo(QPainterPath &path, const QPointF &point) -

1287 { -

1288 const int elementCount = path.elementCount(); -

1289 if (elementCount >= 2) { -

1290 const QPainterPath::Element &middle = path.elementAt(elementCount - 1); -

1291 if (middle.type == QPainterPath::LineToElement) { -

1292 const QPointF first = path.elementAt(elementCount - 2); -

1293 const QPointF d1 = point - first; -

1294 const QPointF d2 = middle - first; -

1295 -

1296 const QPointF p(-d1.y(), d1.x()); -

1297 -

1298 if (qFuzzyIsNull(dot(p, d2))) { -

1299 path.setElementPositionAt(elementCount - 1, point.x(), point.y()); -

1300 return; -

1301 } -

1302 } -

1303 } -

1304 -

1305 path.lineTo(point); -

1306 } -

1307 -

1308 static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal) -

1309 { -

1310 QWingedEdge::TraversalStatus status; -

1311 status.edge = edge; -

1312 status.traversal = traversal; -

1313 status.direction = QPathEdge::Forward; -

1314 -

1315 path.moveTo(*list.vertex(list.edge(edge)->first)); -

1316 -

1317 do { -

1318 const QPathEdge *ep = list.edge(status.edge); -

1319 -

1320 addLineTo(path, *list.vertex(ep->vertex(status.direction))); -

1321 -

1322 if (status.traversal == QPathEdge::LeftTraversal) -

1323 ep->flag &= ~16; -

1324 else -

1325 ep->flag &= ~32; -

1326 -

1327 status = list.next(status); -

1328 } while (status.edge != edge); -

1329 } -

1330 -

1331 void QWingedEdge::simplify() -

1332 { -

1333 for (int i = 0; i < edgeCount(); ++i) { -

1334 const QPathEdge *ep = edge(i); -

1335 -

1336 // if both sides are part of the inside then we can collapse the edge -

1337 int flag = 0x3 << 4; -

1338 if ((ep->flag & flag) == flag) { -

1339 removeEdge(i); -

1340 -

1341 ep->flag &= ~flag; -

1342 } -

1343 } -

1344 } -

1345 -

1346 QPainterPath QWingedEdge::toPath() const -

1347 { -

1348 QPainterPath path; -

1349 -

1350 for (int i = 0; i < edgeCount(); ++i) { -

1351 const QPathEdge *ep = edge(i); -

1352 -

1353 if (ep->flag & 16) { -

1354 add(path, *this, i, QPathEdge::LeftTraversal); -

1355 } -

1356 -

1357 if (ep->flag & 32) -

1358 add(path, *this, i, QPathEdge::RightTraversal); -

1359 } -

1360 -

1361 return path; -

1362 } -

1363 -

1364 bool QPathClipper::intersect() -

1365 { -

1366 if (subjectPath == clipPath) -

1367 return true; -

1368 -

1369 QRectF r1 = subjectPath.controlPointRect(); -

1370 QRectF r2 = clipPath.controlPointRect(); -

1371 if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) || -

1372 qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) { -

1373 // no way we could intersect -

1374 return false; -

1375 } -

1376 -

1377 bool subjectIsRect = pathToRect(subjectPath); -

1378 bool clipIsRect = pathToRect(clipPath); -

1379 -

1380 if (subjectIsRect && clipIsRect) -

1381 return true; -

1382 else if (subjectIsRect) -

1383 return clipPath.intersects(r1); -

1384 else if (clipIsRect) -

1385 return subjectPath.intersects(r2); -

1386 -

1387 QPathSegments a(subjectPath.elementCount()); -

1388 a.setPath(subjectPath); -

1389 QPathSegments b(clipPath.elementCount()); -

1390 b.setPath(clipPath); -

1391 -

1392 QIntersectionFinder finder; -

1393 if (finder.hasIntersections(a, b)) -

1394 return true; -

1395 -

1396 for (int i = 0; i < clipPath.elementCount(); ++i) { -

1397 if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) { -

1398 const QPointF point = clipPath.elementAt(i); -

1399 if (r1.contains(point) && subjectPath.contains(point)) -

1400 return true; -

1401 } -

1402 } -

1403 -

1404 for (int i = 0; i < subjectPath.elementCount(); ++i) { -

1405 if (subjectPath.elementAt(i).type == QPainterPath::MoveToElement) { -

1406 const QPointF point = subjectPath.elementAt(i); -

1407 if (r2.contains(point) && clipPath.contains(point)) -

1408 return true; -

1409 } -

1410 } -

1411 -

1412 return false; -

1413 } -

1414 -

1415 bool QPathClipper::contains() -

1416 { -

1417 if (subjectPath == clipPath) -

1418 return false; -

1419 -

1420 QRectF r1 = subjectPath.controlPointRect(); -

1421 QRectF r2 = clipPath.controlPointRect(); -

1422 if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) || -

1423 qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) { -

1424 // no intersection -> not contained -

1425 return false; -

1426 } -

1427 -

1428 bool clipIsRect = pathToRect(clipPath); -

1429 if (clipIsRect) -

1430 return subjectPath.contains(r2); -

1431 -

1432 QPathSegments a(subjectPath.elementCount()); -

1433 a.setPath(subjectPath); -

1434 QPathSegments b(clipPath.elementCount()); -

1435 b.setPath(clipPath); -

1436 -

1437 QIntersectionFinder finder; -

1438 if (finder.hasIntersections(a, b)) -

1439 return false; -

1440 -

1441 for (int i = 0; i < clipPath.elementCount(); ++i) { -

1442 if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) { -

1443 const QPointF point = clipPath.elementAt(i); -

1444 if (!r1.contains(point) || !subjectPath.contains(point)) -

1445 return false; -

1446 } -

1447 } -

1448 -

1449 return true; -

1450 } -

1451 -

1452 QPathClipper::QPathClipper(const QPainterPath &subject, -

1453 const QPainterPath &clip) -

1454 : subjectPath(subject) -

1455 , clipPath(clip) -

1456 { -

1457 aMask = subjectPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1; -

1458 bMask = clipPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1; -

1459 } -

1460 -

1461 template <typename Iterator, typename Equality> -

1462 Iterator qRemoveDuplicates(Iterator begin, Iterator end, Equality eq) -

1463 { -

1464 if (begin == end) -

1465 return end; -

1466 -

1467 Iterator last = begin; -

1468 ++begin; -

1469 Iterator insert = begin; -

1470 for (Iterator it = begin; it != end; ++it) { -

1471 if (!eq(*it, *last)) { -

1472 *insert++ = *it; -

1473 last = it; -

1474 } -

1475 } -

1476 -

1477 return insert; -

1478 } -

1479 -

1480 static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal) -

1481 { -

1482 QWingedEdge::TraversalStatus status; -

1483 status.edge = edge; -

1484 status.traversal = traversal; -

1485 status.direction = QPathEdge::Forward; -

1486 -

1487 do { -

1488 if (status.traversal == QPathEdge::LeftTraversal) -

1489 list.edge(status.edge)->flag |= 1; -

1490 else -

1491 list.edge(status.edge)->flag |= 2; -

1492 -

1493 status = list.next(status); -

1494 } while (status.edge != edge); -

1495 } -

1496 -

1497 template <typename InputIterator> -

1498 InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val) -

1499 { -

1500 while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val))) -

1501 ++first; -

1502 return first; -

1503 } -

1504 -

1505 static bool fuzzyCompare(qreal a, qreal b) -

1506 { -

1507 return qFuzzyCompare(a, b); -

1508 } -

1509 -

1510 bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect) -

1511 { -

1512 if (path.elementCount() != 5) -

1513 return false; -

1514 -

1515 const bool mightBeRect = path.elementAt(0).isMoveTo() -

1516 && path.elementAt(1).isLineTo() -

1517 && path.elementAt(2).isLineTo() -

1518 && path.elementAt(3).isLineTo() -

1519 && path.elementAt(4).isLineTo(); -

1520 -

1521 if (!mightBeRect) -

1522 return false; -

1523 -

1524 const qreal x1 = path.elementAt(0).x; -

1525 const qreal y1 = path.elementAt(0).y; -

1526 -

1527 const qreal x2 = path.elementAt(1).x; -

1528 const qreal y2 = path.elementAt(2).y; -

1529 -

1530 if (path.elementAt(1).y != y1) -

1531 return false; -

1532 -

1533 if (path.elementAt(2).x != x2) -

1534 return false; -

1535 -

1536 if (path.elementAt(3).x != x1 || path.elementAt(3).y != y2) -

1537 return false; -

1538 -

1539 if (path.elementAt(4).x != x1 || path.elementAt(4).y != y1) -

1540 return false; -

1541 -

1542 if (rect) -

1543 rect->setCoords(x1, y1, x2, y2); -

1544 -

1545 return true; -

1546 } -

1547 -

1548 -

1549 QPainterPath QPathClipper::clip(Operation operation) -

1550 { -

1551 op = operation; -

1552 -

1553 if (op != Simplify) { -

1554 if (subjectPath == clipPath) -

1555 return op == BoolSub ? QPainterPath() : subjectPath; -

1556 -

1557 bool subjectIsRect = pathToRect(subjectPath, 0); -

1558 bool clipIsRect = pathToRect(clipPath, 0); -

1559 -

1560 const QRectF clipBounds = clipPath.boundingRect(); -

1561 const QRectF subjectBounds = subjectPath.boundingRect(); -

1562 -

1563 if (!clipBounds.intersects(subjectBounds)) { -

1564 switch (op) { -

1565 case BoolSub: -

1566 return subjectPath; -

1567 case BoolAnd: -

1568 return QPainterPath(); -

1569 case BoolOr: { -

1570 QPainterPath result = subjectPath; -

1571 if (result.fillRule() == clipPath.fillRule()) { -

1572 result.addPath(clipPath); -

1573 } else if (result.fillRule() == Qt::WindingFill) { -

1574 result = result.simplified(); -

1575 result.addPath(clipPath); -

1576 } else { -

1577 result.addPath(clipPath.simplified()); -

1578 } -

1579 return result; -

1580 } -

1581 default: -

1582 break; -

1583 } -

1584 } -

1585 -

1586 if (clipBounds.contains(subjectBounds)) { -

1587 if (clipIsRect) { -

1588 switch (op) { -

1589 case BoolSub: -

1590 return QPainterPath(); -

1591 case BoolAnd: -

1592 return subjectPath; -

1593 case BoolOr: -

1594 return clipPath; -

1595 default: -

1596 break; -

1597 } -

1598 } -

1599 } else if (subjectBounds.contains(clipBounds)) { -

1600 if (subjectIsRect) { -

1601 switch (op) { -

1602 case BoolSub: -

1603 if (clipPath.fillRule() == Qt::OddEvenFill) { -

1604 QPainterPath result = clipPath; -

1605 result.addRect(subjectBounds); -

1606 return result; -

1607 } else { -

1608 QPainterPath result = clipPath.simplified(); -

1609 result.addRect(subjectBounds); -

1610 return result; -

1611 } -

1612 case BoolAnd: -

1613 return clipPath; -

1614 case BoolOr: -

1615 return subjectPath; -

1616 default: -

1617 break; -

1618 } -

1619 } -

1620 } -

1621 -

1622 if (op == BoolAnd) { -

1623 if (subjectIsRect) -

1624 return intersect(clipPath, subjectBounds); -

1625 else if (clipIsRect) -

1626 return intersect(subjectPath, clipBounds); -

1627 } -

1628 } -

1629 -

1630 QWingedEdge list(subjectPath, clipPath); -

1631 -

1632 doClip(list, ClipMode); -

1633 -

1634 QPainterPath path = list.toPath(); -

1635 return path; -

1636 } -

1637 -

1638 bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode) -

1639 { -

1640 QVector<qreal> y_coords; -

1641 y_coords.reserve(list.vertexCount()); -

1642

for (int i = 0; i < list.vertexCount(); ++i)

i < list.vertexCount()	Description
TRUE	never evaluated
FALSE	never evaluated

1643

y_coords << list.vertex(i)->y;

never executed: y_coords << list.vertex(i)->y;

1644 -

1645 std::sort(y_coords.begin(), y_coords.end()); -

1646 y_coords.resize(qRemoveDuplicates(y_coords.begin(), y_coords.end(), fuzzyCompare) - y_coords.begin()); -

1647 -

1648 #ifdef QDEBUG_CLIPPER -

1649 printf("sorted y coords:\n"); -

1650 for (int i = 0; i < y_coords.size(); ++i) { -

1651 printf("%.9f\n", y_coords[.at(i]);)); -

1652 } -

1653 #endif -

1654 -

1655 bool found; -

1656 do { -

1657 found = false; -

1658 int index = 0; -

1659 qreal maxHeight = 0; -

1660

for (int i = 0; i < list.edgeCount(); ++i) {

i < list.edgeCount()	Description
TRUE	never evaluated
FALSE	never evaluated

1661 QPathEdge *edge = list.edge(i); -

1662 -

1663 // have both sides of this edge already been handled? -

1664

if ((edge->flag & 0x3) == 0x3)

(edge->flag & 0x3) == 0x3	Description
TRUE	never evaluated
FALSE	never evaluated

1665

continue;

never executed: continue;

1666 -

1667 QPathVertex *a = list.vertex(edge->first); -

1668 QPathVertex *b = list.vertex(edge->second); -

1669 -

1670

if (qFuzzyCompare(a->y, b->y))

qFuzzyCompare(a->y, b->y)	Description
TRUE	never evaluated
FALSE	never evaluated

1671

continue;

never executed: continue;

1672 -

1673 found = true; -

1674 -

1675 qreal height = qAbs(a->y - b->y); -

1676

if (height > maxHeight) {

height > maxHeight	Description
TRUE	never evaluated
FALSE	never evaluated

1677 index = i; -

1678 maxHeight = height; -

1679

}

never executed: end of block

1680

}

never executed: end of block

1681 -

1682

if (found) {

found	Description
TRUE	never evaluated
FALSE	never evaluated

1683 QPathEdge *edge = list.edge(index); -

1684 -

1685 QPathVertex *a = list.vertex(edge->first); -

1686 QPathVertex *b = list.vertex(edge->second); -

1687 -

1688 // FIXME: this can be optimized by using binary search -

1689 const int first = qFuzzyFind(y_coords.begincbegin(), y_coords.endcend(), qMin(a->y, b->y)) - y_coords.begincbegin(); -

1690 const int last = qFuzzyFind(y_coords.begincbegin() + first, y_coords.endcend(), qMax(a->y, b->y)) - y_coords.begincbegin(); -

1691 -

1692 Q_ASSERT(first < y_coords.size() - 1); -

1693 Q_ASSERT(last < y_coords.size()); -

1694 -

1695 qreal bestY = 0.5 * (y_coords[first] + y_coords[first+1]);qreal biggestGap = y_coords[.at(first + 1]) - y_coords[.at(first];); -

1696 int bestIdx = first; -

1697

for (int i = first + 1; i < last; ++i) {

i < last	Description
TRUE	never evaluated
FALSE	never evaluated

1698 qreal gap = y_coords[.at(i + 1]) - y_coords[.at(i];); -

1699 -

1700

if (gap > biggestGap) {

gap > biggestGap	Description
TRUE	never evaluated
FALSE	never evaluated

1701 bestIdx = i; -

1702 biggestGap = gap; -

1703

}

never executed: end of block

1704

}

never executed: end of block

1705 const qreal bestY = 0.5 * (y_coords[i].at(bestIdx) + y_coords[i.at(bestIdx + 1]); -

biggestGap = gap;

}

}));

1706 -

1707 #ifdef QDEBUG_CLIPPER -

1708 printf("y: %.9f, gap: %.9f\n", bestY, biggestGap); -

1709 #endif -

1710 -

1711

if (handleCrossingEdges(list, bestY, mode) && mode == CheckMode)

handleCrossing..., bestY, mode)	Description
TRUE	never evaluated
FALSE	never evaluated

mode == CheckMode	Description
TRUE	never evaluated
FALSE	never evaluated

1712

return true;

never executed: return true;

1713 -

1714 edge->flag |= 0x3; -

1715

}

never executed: end of block

1716

} while (found);

never executed: end of block

found	Description
TRUE	never evaluated
FALSE	never evaluated

1717 -

1718

if (mode == ClipMode)

mode == ClipMode	Description
TRUE	never evaluated
FALSE	never evaluated

1719

list.simplify();

never executed: list.simplify();

1720 -

1721

return false;

never executed: return false;

1722 } -

1723 -

1724 static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal) -

1725 { -

1726 QWingedEdge::TraversalStatus status; -

1727 status.edge = edge; -

1728 status.traversal = traversal; -

1729 status.direction = QPathEdge::Forward; -

1730 -

1731 do { -

1732 int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2; -

1733 -

1734 QPathEdge *ep = list.edge(status.edge); -

1735 -

1736 ep->flag |= (flag | (flag << 4)); -

1737 -

1738 #ifdef QDEBUG_CLIPPER -

1739 qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag; -

1740 #endif -

1741 -

1742 status = list.next(status); -

1743 } while (status.edge != edge); -

1744 } -

1745 -

1746 struct QCrossingEdge -

1747 { -

1748 int edge; -

1749 qreal x; -

1750 -

1751 bool operator<(const QCrossingEdge &edge) const -

1752 { -

1753 return x < edge.x; -

1754 } -

1755 }; -

1756 Q_DECLARE_TYPEINFO(QCrossingEdge, Q_PRIMITIVE_TYPE); -

1757 -

1758 static bool bool_op(bool a, bool b, QPathClipper::Operation op) -

1759 { -

1760 switch (op) { -

1761 case QPathClipper::BoolAnd: -

1762 return a && b; -

1763 case QPathClipper::BoolOr: // fall-through -

1764 case QPathClipper::Simplify: -

1765 return a || b; -

1766 case QPathClipper::BoolSub: -

1767 return a && !b; -

1768 default: -

1769 Q_ASSERT(false); -

1770 return false; -

1771 } -

1772 } -

1773 -

1774 bool QWingedEdge::isInside(qreal x, qreal y) const -

1775 { -

1776 int winding = 0; -

1777 for (int i = 0; i < edgeCount(); ++i) { -

1778 const QPathEdge *ep = edge(i); -

1779 -

1780 // left xor right -

1781 int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1; -

1782 -

1783 if (!w) -

1784 continue; -

1785 -

1786 QPointF a = *vertex(ep->first); -

1787 QPointF b = *vertex(ep->second); -

1788 -

1789 if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { -

1790 qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); -

1791 -

1792 if (intersectionX > x) -

1793 winding += w; -

1794 } -

1795 } -

1796 -

1797 return winding & 1; -

1798 } -

1799 -

1800 static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y) -

1801 { -

1802 QVector<QCrossingEdge> crossings; -

1803 for (int i = 0; i < list.edgeCount(); ++i) { -

1804 const QPathEdge *edge = list.edge(i); -

1805 QPointF a = *list.vertex(edge->first); -

1806 QPointF b = *list.vertex(edge->second); -

1807 -

1808 if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { -

1809 const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); -

1810 const QCrossingEdge edge = { i, intersection }; -

1811 crossings << edge; -

1812 } -

1813 } -

1814 return crossings; -

1815 } -

1816 -

1817 bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode) -

1818 { -

1819 QVector<QCrossingEdge> crossings = findCrossings(list, y); -

1820 -

1821 Q_ASSERT(!crossings.isEmpty()); -

1822 std::sort(crossings.begin(), crossings.end()); -

1823 -

1824 int windingA = 0; -

1825 int windingB = 0; -

1826 -

1827 int windingD = 0; -

1828 -

1829 #ifdef QDEBUG_CLIPPER -

1830 qDebug() << "crossings:" << crossings.size(); -

1831 #endif -

1832 for (int i = 0; i < crossings.size() - 1; ++i) { -

1833 int ei = crossings.at(i).edge; -

1834 const QPathEdge *edge = list.edge(ei); -

1835 -

1836 windingA += edge->windingA; -

1837 windingB += edge->windingB; -

1838 -

1839 const bool hasLeft = (edge->flag >> 4) & 1; -

1840 const bool hasRight = (edge->flag >> 4) & 2; -

1841 -

1842 windingD += hasLeft ^ hasRight; -

1843 -

1844 const bool inA = (windingA & aMask) != 0; -

1845 const bool inB = (windingB & bMask) != 0; -

1846 const bool inD = (windingD & 0x1) != 0; -

1847 -

1848 const bool inside = bool_op(inA, inB, op); -

1849 const bool add = inD ^ inside; -

1850 -

1851 #ifdef QDEBUG_CLIPPER -

1852 printf("y %f, x %f, inA: %d, inB: %d, inD: %d, inside: %d, flag: %x, bezier: %p, edge: %d\n", y, crossings.at(i).x, inA, inB, inD, inside, edge->flag, edge->bezier, ei); -

1853 #endif -

1854 -

1855 if (add) { -

1856 if (mode == CheckMode) -

1857 return true; -

1858 -

1859 qreal y0 = list.vertex(edge->first)->y; -

1860 qreal y1 = list.vertex(edge->second)->y; -

1861 -

1862 if (y0 < y1) { -

1863 if (!(edge->flag & 1)) -

1864 traverse(list, ei, QPathEdge::LeftTraversal); -

1865 -

1866 if (!(edge->flag & 2)) -

1867 clear(list, ei, QPathEdge::RightTraversal); -

1868 } else { -

1869 if (!(edge->flag & 1)) -

1870 clear(list, ei, QPathEdge::LeftTraversal); -

1871 -

1872 if (!(edge->flag & 2)) -

1873 traverse(list, ei, QPathEdge::RightTraversal); -

1874 } -

1875 -

1876 ++windingD; -

1877 } else { -

1878 if (!(edge->flag & 1)) -

1879 clear(list, ei, QPathEdge::LeftTraversal); -

1880 -

1881 if (!(edge->flag & 2)) -

1882 clear(list, ei, QPathEdge::RightTraversal); -

1883 } -

1884 } -

1885 -

1886 return false; -

1887 } -

1888 -

1889 namespace { -

1890 -

1891 QVector<QPainterPath> toSubpaths(const QPainterPath &path) -

1892 { -

1893 -

1894 QVector<QPainterPath> subpaths; -

1895 if (path.isEmpty()) -

1896 return subpaths; -

1897 -

1898 QPainterPath current; -

1899 for (int i = 0; i < path.elementCount(); ++i) { -

1900 const QPainterPath::Element &e = path.elementAt(i); -

1901 switch (e.type) { -

1902 case QPainterPath::MoveToElement: -

1903 if (current.elementCount() > 1) -

1904 subpaths += current; -

1905 current = QPainterPath(); -

1906 current.moveTo(e); -

1907 break; -

1908 case QPainterPath::LineToElement: -

1909 current.lineTo(e); -

1910 break; -

1911 case QPainterPath::CurveToElement: { -

1912 current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2)); -

1913 i+=2; -

1914 break; -

1915 } -

1916 case QPainterPath::CurveToDataElement: -

1917 Q_ASSERT(!"toSubpaths(), bad element type"); -

1918 break; -

1919 } -

1920 } -

1921 -

1922 if (current.elementCount() > 1) -

1923 subpaths << current; -

1924 -

1925 return subpaths; -

1926 } -

1927 -

1928 enum Edge -

1929 { -

1930 Left, Top, Right, Bottom -

1931 }; -

1932 -

1933 static bool isVertical(Edge edge) -

1934 { -

1935 return edge == Left || edge == Right; -

1936 } -

1937 -

1938 template <Edge edge> -

1939 bool compare(const QPointF &p, qreal t) -

1940 { -

1941 switch (edge) -

1942 { -

1943 case Left: -

1944 return p.x() < t; -

1945 case Right: -

1946 return p.x() > t; -

1947 case Top: -

1948 return p.y() < t; -

1949 default: -

1950 return p.y() > t; -

1951 } -

1952 } -

1953 -

1954 template <Edge edge> -

1955 QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t) -

1956 { -

1957 QLineF line(a, b); -

1958 switch (edge) { -

1959 case Left: // fall-through -

1960 case Right: -

1961 return line.pointAt((t - a.x()) / (b.x() - a.x())); -

1962 default: -

1963 return line.pointAt((t - a.y()) / (b.y() - a.y())); -

1964 } -

1965 } -

1966 -

1967 void addLine(QPainterPath &path, const QLineF &line) -

1968 { -

1969 if (path.elementCount() > 0) -

1970 path.lineTo(line.p1()); -

1971 else -

1972 path.moveTo(line.p1()); -

1973 -

1974 path.lineTo(line.p2()); -

1975 } -

1976 -

1977 template <Edge edge> -

1978 void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result) -

1979 { -

1980 bool outA = compare<edge>(a, t); -

1981 bool outB = compare<edge>(b, t); -

1982 if (outA && outB) -

1983 return; -

1984 -

1985 if (outA) -

1986 addLine(result, QLineF(intersectLine<edge>(a, b, t), b)); -

1987 else if(outB) -

1988 addLine(result, QLineF(a, intersectLine<edge>(a, b, t))); -

1989 else -

1990 addLine(result, QLineF(a, b)); -

1991 } -

1992 -

1993 void addBezier(QPainterPath &path, const QBezier &bezier) -

1994 { -

1995 if (path.elementCount() > 0) -

1996 path.lineTo(bezier.pt1()); -

1997 else -

1998 path.moveTo(bezier.pt1()); -

1999 -

2000 path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4()); -

2001 } -

2002 -

2003 template <Edge edge> -

2004 void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result) -

2005 { -

2006 QBezier bezier = QBezier::fromPoints(a, b, c, d); -

2007 -

2008 bool outA = compare<edge>(a, t); -

2009 bool outB = compare<edge>(b, t); -

2010 bool outC = compare<edge>(c, t); -

2011 bool outD = compare<edge>(d, t); -

2012 -

2013 int outCount = int(outA) + int(outB) + int(outC) + int(outD); -

2014 -

2015 if (outCount == 4) -

2016 return; -

2017 -

2018 if (outCount == 0) { -

2019 addBezier(result, bezier); -

2020 return; -

2021 } -

2022 -

2023 QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform(); -

2024 QBezier unflipped = bezier; -

2025 QBezier flipped = bezier.mapBy(flip); -

2026 -

2027 qreal t0 = 0, t1 = 1; -

2028 int stationary = flipped.stationaryYPoints(t0, t1); -

2029 -

2030 qreal segments[4]; -

2031 QPointF points[4]; -

2032 points[0] = unflipped.pt1(); -

2033 segments[0] = 0; -

2034 -

2035 int segmentCount = 0; -

2036 if (stationary > 0) { -

2037 ++segmentCount; -

2038 segments[segmentCount] = t0; -

2039 points[segmentCount] = unflipped.pointAt(t0); -

2040 } -

2041 if (stationary > 1) { -

2042 ++segmentCount; -

2043 segments[segmentCount] = t1; -

2044 points[segmentCount] = unflipped.pointAt(t1); -

2045 } -

2046 ++segmentCount; -

2047 segments[segmentCount] = 1; -

2048 points[segmentCount] = unflipped.pt4(); -

2049 -

2050 qreal lastIntersection = 0; -

2051 for (int i = 0; i < segmentCount; ++i) { -

2052 outA = compare<edge>(points[i], t); -

2053 outB = compare<edge>(points[i+1], t); -

2054 -

2055 if (outA != outB) { -

2056 qreal intersection = flipped.tForY(segments[i], segments[i+1], t); -

2057 -

2058 if (outB) -

2059 addBezier(result, unflipped.getSubRange(lastIntersection, intersection)); -

2060 -

2061 lastIntersection = intersection; -

2062 } -

2063 } -

2064 -

2065 if (!outB) -

2066 addBezier(result, unflipped.getSubRange(lastIntersection, 1)); -

2067 } -

2068 -

2069 // clips a single subpath against a single edge -

2070 template <Edge edge> -

2071 QPainterPath clip(const QPainterPath &path, qreal t) -

2072 { -

2073 QPainterPath result; -

2074 for (int i = 1; i < path.elementCount(); ++i) { -

2075 const QPainterPath::Element &element = path.elementAt(i); -

2076 Q_ASSERT(!element.isMoveTo()); -

2077 if (element.isLineTo()) { -

2078 clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result); -

2079 } else { -

2080 clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result); -

2081 i += 2; -

2082 } -

2083 } -

2084 -

2085 int last = path.elementCount() - 1; -

2086 if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0))) -

2087 clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result); -

2088 -

2089 return result; -

2090 } -

2091 -

2092 QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect) -

2093 { -

2094 QVector<QPainterPath> subpaths = toSubpaths(path); -

2095 -

2096 QPainterPath result; -

2097 result.setFillRule(path.fillRule()); -

2098 for (int i = 0; i < subpaths.size(); ++i) { -

2099 QPainterPath subPath = subpaths.at(i); -

2100 QRectF bounds = subPath.boundingRect(); -

2101 if (bounds.intersects(rect)) { -

2102 if (bounds.left() < rect.left()) -

2103 subPath = clip<Left>(subPath, rect.left()); -

2104 if (bounds.right() > rect.right()) -

2105 subPath = clip<Right>(subPath, rect.right()); -

2106 -

2107 bounds = subPath.boundingRect(); -

2108 -

2109 if (bounds.top() < rect.top()) -

2110 subPath = clip<Top>(subPath, rect.top()); -

2111 if (bounds.bottom() > rect.bottom()) -

2112 subPath = clip<Bottom>(subPath, rect.bottom()); -

2113 -

2114 if (subPath.elementCount() > 1) -

2115 result.addPath(subPath); -

2116 } -

2117 } -

2118 return result; -

2119 } -

2120 -

2121 } -

2122 -

2123 QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect) -

2124 { -

2125 return intersectPath(path, rect); -

2126 } -

2127 -

2128 QT_END_NAMESPACE -

Source code

Switch to Preprocessed file

Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9