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 | #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 | static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal) |

1462 | { |

1463 | QWingedEdge::TraversalStatus status; |

1464 | status.edge = edge; |

1465 | status.traversal = traversal; |

1466 | status.direction = QPathEdge::Forward; |

1467 | |

1468 | do { |

1469 | if (status.traversal == QPathEdge::LeftTraversal) |

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

1471 | else |

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

1473 | |

1474 | status = list.next(status); |

1475 | } while (status.edge != edge); |

1476 | } |

1477 | |

1478 | template <typename InputIterator> |

1479 | InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val) |

1480 | { |

1481 | while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val))) |

1482 | ++first; |

1483 | return first; |

1484 | } |

1485 | |

1486 | static bool fuzzyCompare(qreal a, qreal b) |

1487 | { |

1488 | return qFuzzyCompare(a, b); |

1489 | } |

1490 | |

1491 | bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect) |

1492 | { |

1493 | if (path.elementCount() != 5) |

1494 | return false; |

1495 | |

1496 | const bool mightBeRect = path.elementAt(0).isMoveTo() |

1497 | && path.elementAt(1).isLineTo() |

1498 | && path.elementAt(2).isLineTo() |

1499 | && path.elementAt(3).isLineTo() |

1500 | && path.elementAt(4).isLineTo(); |

1501 | |

1502 | if (!mightBeRect) |

1503 | return false; |

1504 | |

1505 | const qreal x1 = path.elementAt(0).x; |

1506 | const qreal y1 = path.elementAt(0).y; |

1507 | |

1508 | const qreal x2 = path.elementAt(1).x; |

1509 | const qreal y2 = path.elementAt(2).y; |

1510 | |

1511 | if (path.elementAt(1).y != y1) |

1512 | return false; |

1513 | |

1514 | if (path.elementAt(2).x != x2) |

1515 | return false; |

1516 | |

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

1518 | return false; |

1519 | |

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

1521 | return false; |

1522 | |

1523 | if (rect) |

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

1525 | |

1526 | return true; |

1527 | } |

1528 | |

1529 | |

1530 | QPainterPath QPathClipper::clip(Operation operation) |

1531 | { |

1532 | op = operation; |

1533 | |

1534 | if (op != Simplify) { |

1535 | if (subjectPath == clipPath) |

1536 | return op == BoolSub ? QPainterPath() : subjectPath; |

1537 | |

1538 | bool subjectIsRect = pathToRect(subjectPath, 0); |

1539 | bool clipIsRect = pathToRect(clipPath, 0); |

1540 | |

1541 | const QRectF clipBounds = clipPath.boundingRect(); |

1542 | const QRectF subjectBounds = subjectPath.boundingRect(); |

1543 | |

1544 | if (!clipBounds.intersects(subjectBounds)) { |

1545 | switch (op) { |

1546 | case BoolSub: |

1547 | return subjectPath; |

1548 | case BoolAnd: |

1549 | return QPainterPath(); |

1550 | case BoolOr: { |

1551 | QPainterPath result = subjectPath; |

1552 | if (result.fillRule() == clipPath.fillRule()) { |

1553 | result.addPath(clipPath); |

1554 | } else if (result.fillRule() == Qt::WindingFill) { |

1555 | result = result.simplified(); |

1556 | result.addPath(clipPath); |

1557 | } else { |

1558 | result.addPath(clipPath.simplified()); |

1559 | } |

1560 | return result; |

1561 | } |

1562 | default: |

1563 | break; |

1564 | } |

1565 | } |

1566 | |

1567 | if (clipBounds.contains(subjectBounds)) { |

1568 | if (clipIsRect) { |

1569 | switch (op) { |

1570 | case BoolSub: |

1571 | return QPainterPath(); |

1572 | case BoolAnd: |

1573 | return subjectPath; |

1574 | case BoolOr: |

1575 | return clipPath; |

1576 | default: |

1577 | break; |

1578 | } |

1579 | } |

1580 | } else if (subjectBounds.contains(clipBounds)) { |

1581 | if (subjectIsRect) { |

1582 | switch (op) { |

1583 | case BoolSub: |

1584 | if (clipPath.fillRule() == Qt::OddEvenFill) { |

1585 | QPainterPath result = clipPath; |

1586 | result.addRect(subjectBounds); |

1587 | return result; |

1588 | } else { |

1589 | QPainterPath result = clipPath.simplified(); |

1590 | result.addRect(subjectBounds); |

1591 | return result; |

1592 | } |

1593 | case BoolAnd: |

1594 | return clipPath; |

1595 | case BoolOr: |

1596 | return subjectPath; |

1597 | default: |

1598 | break; |

1599 | } |

1600 | } |

1601 | } |

1602 | |

1603 | if (op == BoolAnd) { |

1604 | if (subjectIsRect) |

1605 | return intersect(clipPath, subjectBounds); |

1606 | else if (clipIsRect) |

1607 | return intersect(subjectPath, clipBounds); |

1608 | } |

1609 | } |

1610 | |

1611 | QWingedEdge list(subjectPath, clipPath); |

1612 | |

1613 | doClip(list, ClipMode); |

1614 | |

1615 | QPainterPath path = list.toPath(); |

1616 | return path; |

1617 | } |

1618 | |

1619 | bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode) |

1620 | { |

1621 | QVector<qreal> y_coords; |

1622 | y_coords.reserve(list.vertexCount()); |

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

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

1625 | |

1626 | std::sort(y_coords.begin(), y_coords.end()); |

1627 | y_coords.erase(std::unique(y_coords.begin(), y_coords.end(), fuzzyCompare), y_coords.end()); |

1628 | |

1629 | #ifdef QDEBUG_CLIPPER |

1630 | printf("sorted y coords:\n"); |

1631 | for (int i = 0; i < y_coords.size(); ++i) { |

1632 | printf("%.9f\n", y_coords.at(i)); |

1633 | } |

1634 | #endif |

1635 | |

1636 | bool found; |

1637 | do { |

1638 | found = false; |

1639 | int index = 0; |

1640 | qreal maxHeight = 0; |

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

1642 | QPathEdge *edge = list.edge(i); |

1643 | |

1644 | // have both sides of this edge already been handled? |

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

1646 | continue; |

1647 | |

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

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

1650 | |

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

1652 | continue; |

1653 | |

1654 | found = true; |

1655 | |

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

1657 | if (height > maxHeight) { |

1658 | index = i; |

1659 | maxHeight = height; |

1660 | } |

1661 | } |

1662 | |

1663 | if (found) { |

1664 | QPathEdge *edge = list.edge(index); |

1665 | |

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

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

1668 | |

1669 | // FIXME: this can be optimized by using binary search |

1670 | const int first = qFuzzyFind(y_coords.cbegin(), y_coords.cend(), qMin(a->y, b->y)) - y_coords.cbegin(); |

1671 | const int last = qFuzzyFind(y_coords.cbegin() + first, y_coords.cend(), qMax(a->y, b->y)) - y_coords.cbegin(); |

1672 | |

1673 | Q_ASSERT(first < y_coords.size() - 1); |

1674 | Q_ASSERT(last < y_coords.size()); |

1675 | |

1676 | qreal biggestGap = y_coords.at(first + 1) - y_coords.at(first); |

1677 | int bestIdx = first; |

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

1679 | qreal gap = y_coords.at(i + 1) - y_coords.at(i); |

1680 | |

1681 | if (gap > biggestGap) { |

1682 | bestIdx = i; |

1683 | biggestGap = gap; |

1684 | } |

1685 | } |

1686 | const qreal bestY = 0.5 * (y_coords.at(bestIdx) + y_coords.at(bestIdx + 1)); |

1687 | |

1688 | #ifdef QDEBUG_CLIPPER |

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

1690 | #endif |

1691 | |

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

1693 | return true; |

1694 | |

1695 | edge->flag |= 0x3; |

1696 | } |

1697 | } while (found); |

1698 | |

1699 | if (mode == ClipMode) |

1700 | list.simplify(); |

1701 | |

1702 | return false; |

1703 | } |

1704 | |

1705 | static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal) |

1706 | { |

1707 | QWingedEdge::TraversalStatus status; |

1708 | status.edge = edge; |

1709 | status.traversal = traversal; |

1710 | status.direction = QPathEdge::Forward; |

1711 | |

1712 | do { |

1713 | int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2; |

1714 | |

1715 | QPathEdge *ep = list.edge(status.edge); |

1716 | |

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

1718 | |

1719 | #ifdef QDEBUG_CLIPPER |

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

1721 | #endif |

1722 | |

1723 | status = list.next(status); |

1724 | } while (status.edge != edge); |

1725 | } |

1726 | |

1727 | struct QCrossingEdge |

1728 | { |

1729 | int edge; |

1730 | qreal x; |

1731 | |

1732 | bool operator<(const QCrossingEdge &edge) const |

1733 | { |

1734 | return x < edge.x; |

1735 | } |

1736 | }; |

1737 | Q_DECLARE_TYPEINFO(QCrossingEdge, Q_PRIMITIVE_TYPE); |

1738 | |

1739 | static bool bool_op(bool a, bool b, QPathClipper::Operation op) |

1740 | { |

1741 | switch (op) { |

1742 | case QPathClipper::BoolAnd: |

1743 | return a && b; |

1744 | case QPathClipper::BoolOr: |

1745 | case QPathClipper::Simplify: |

1746 | return a || b; |

1747 | case QPathClipper::BoolSub: |

1748 | return a && !b; |

1749 | default: |

1750 | Q_ASSERT(false); |

1751 | return false; |

1752 | } |

1753 | } |

1754 | |

1755 | bool QWingedEdge::isInside(qreal x, qreal y) const |

1756 | { |

1757 | int winding = 0; |

1758 | for (int i = 0; i < edgeCount(); ++i) { |

1759 | const QPathEdge *ep = edge(i); |

1760 | |

1761 | // left xor right |

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

1763 | |

1764 | if (!w) |

1765 | continue; |

1766 | |

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

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

1769 | |

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

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

1772 | |

1773 | if (intersectionX > x) |

1774 | winding += w; |

1775 | } |

1776 | } |

1777 | |

1778 | return winding & 1; |

1779 | } |

1780 | |

1781 | static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y) |

1782 | { |

1783 | QVector<QCrossingEdge> crossings; |

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

1785 | const QPathEdge *edge = list.edge(i); |

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

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

1788 | |

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

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

1791 | const QCrossingEdge edge = { i, intersection }; |

1792 | crossings << edge; |

1793 | } |

1794 | } |

1795 | return crossings; |

1796 | } |

1797 | |

1798 | bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode) |

1799 | { |

1800 | QVector<QCrossingEdge> crossings = findCrossings(list, y); |

1801 | |

1802 | Q_ASSERT(!crossings.isEmpty()); |

1803 | std::sort(crossings.begin(), crossings.end()); |

1804 | |

1805 | int windingA = 0; |

1806 | int windingB = 0; |

1807 | |

1808 | int windingD = 0; |

1809 | |

1810 | #ifdef QDEBUG_CLIPPER |

1811 | qDebug() << "crossings:"<< crossings.size(); |

1812 | #endif |

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

1814 | int ei = crossings.at(i).edge; |

1815 | const QPathEdge *edge = list.edge(ei); |

1816 | |

1817 | windingA += edge->windingA; |

1818 | windingB += edge->windingB; |

1819 | |

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

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

1822 | |

1823 | windingD += hasLeft ^ hasRight; |

1824 | |

1825 | const bool inA = (windingA & aMask) != 0; |

1826 | const bool inB = (windingB & bMask) != 0; |

1827 | const bool inD = (windingD & 0x1) != 0; |

1828 | |

1829 | const bool inside = bool_op(inA, inB, op); |

1830 | const bool add = inD ^ inside; |

1831 | |

1832 | #ifdef QDEBUG_CLIPPER |

1833 | 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); |

1834 | #endif |

1835 | |

1836 | if (add) { |

1837 | if (mode == CheckMode) |

1838 | return true; |

1839 | |

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

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

1842 | |

1843 | if (y0 < y1) { |

1844 | if (!(edge->flag & 1)) |

1845 | traverse(list, ei, QPathEdge::LeftTraversal); |

1846 | |

1847 | if (!(edge->flag & 2)) |

1848 | clear(list, ei, QPathEdge::RightTraversal); |

1849 | } else { |

1850 | if (!(edge->flag & 1)) |

1851 | clear(list, ei, QPathEdge::LeftTraversal); |

1852 | |

1853 | if (!(edge->flag & 2)) |

1854 | traverse(list, ei, QPathEdge::RightTraversal); |

1855 | } |

1856 | |

1857 | ++windingD; |

1858 | } else { |

1859 | if (!(edge->flag & 1)) |

1860 | clear(list, ei, QPathEdge::LeftTraversal); |

1861 | |

1862 | if (!(edge->flag & 2)) |

1863 | clear(list, ei, QPathEdge::RightTraversal); |

1864 | } |

1865 | } |

1866 | |

1867 | return false; |

1868 | } |

1869 | |

1870 | namespace { |

1871 | |

1872 | QVector<QPainterPath> toSubpaths(const QPainterPath &path) |

1873 | { |

1874 | |

1875 | QVector<QPainterPath> subpaths; |

1876 | if (path.isEmpty()) |

1877 | return subpaths; |

1878 | |

1879 | QPainterPath current; |

1880 | for (int i = 0; i < path.elementCount(); ++i) { |

1881 | const QPainterPath::Element &e = path.elementAt(i); |

1882 | switch (e.type) { |

1883 | case QPainterPath::MoveToElement: |

1884 | if (current.elementCount() > 1) |

1885 | subpaths += current; |

1886 | current = QPainterPath(); |

1887 | current.moveTo(e); |

1888 | break; |

1889 | case QPainterPath::LineToElement: |

1890 | current.lineTo(e); |

1891 | break; |

1892 | case QPainterPath::CurveToElement: { |

1893 | current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2)); |

1894 | i+=2; |

1895 | break; |

1896 | } |

1897 | case QPainterPath::CurveToDataElement: |

1898 | Q_ASSERT(!"toSubpaths(), bad element type"); |

1899 | break; |

1900 | } |

1901 | } |

1902 | |

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

1904 | subpaths << current; |

1905 | |

1906 | return subpaths; |

1907 | } |

1908 | |

1909 | enum Edge |

1910 | { |

1911 | Left, Top, Right, Bottom |

1912 | }; |

1913 | |

1914 | static bool isVertical(Edge edge) |

1915 | { |

1916 | return edge == Left || edge == Right; |

1917 | } |

1918 | |

1919 | template <Edge edge> |

1920 | bool compare(const QPointF &p, qreal t) |

1921 | { |

1922 | switch (edge) |

1923 | { |

1924 | case Left: |

1925 | return p.x() < t; |

1926 | case Right: |

1927 | return p.x() > t; |

1928 | case Top: |

1929 | return p.y() < t; |

1930 | default: |

1931 | return p.y() > t; |

1932 | } |

1933 | } |

1934 | |

1935 | template <Edge edge> |

1936 | QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t) |

1937 | { |

1938 | QLineF line(a, b); |

1939 | switch (edge) { |

1940 | case Left: |

1941 | case Right: |

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

1943 | default: |

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

1945 | } |

1946 | } |

1947 | |

1948 | void addLine(QPainterPath &path, const QLineF &line) |

1949 | { |

1950 | if (path.elementCount() > 0) |

1951 | path.lineTo(line.p1()); |

1952 | else |

1953 | path.moveTo(line.p1()); |

1954 | |

1955 | path.lineTo(line.p2()); |

1956 | } |

1957 | |

1958 | template <Edge edge> |

1959 | void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result) |

1960 | { |

1961 | bool outA = compare<edge>(a, t); |

1962 | bool outB = compare<edge>(b, t); |

1963 | if (outA && outB) |

1964 | return; |

1965 | |

1966 | if (outA) |

1967 | addLine(result, QLineF(intersectLine<edge>(a, b, t), b)); |

1968 | else if(outB) |

1969 | addLine(result, QLineF(a, intersectLine<edge>(a, b, t))); |

1970 | else |

1971 | addLine(result, QLineF(a, b)); |

1972 | } |

1973 | |

1974 | void addBezier(QPainterPath &path, const QBezier &bezier) |

1975 | { |

1976 | if (path.elementCount() > 0) |

1977 | path.lineTo(bezier.pt1()); |

1978 | else |

1979 | path.moveTo(bezier.pt1()); |

1980 | |

1981 | path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4()); |

1982 | } |

1983 | |

1984 | template <Edge edge> |

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

1986 | { |

1987 | QBezier bezier = QBezier::fromPoints(a, b, c, d); |

1988 | |

1989 | bool outA = compare<edge>(a, t); |

1990 | bool outB = compare<edge>(b, t); |

1991 | bool outC = compare<edge>(c, t); |

1992 | bool outD = compare<edge>(d, t); |

1993 | |

1994 | int outCount = int(outA) + int(outB) + int(outC) + int(outD); |

1995 | |

1996 | if (outCount == 4) |

1997 | return; |

1998 | |

1999 | if (outCount == 0) { |

2000 | addBezier(result, bezier); |

2001 | return; |

2002 | } |

2003 | |

2004 | QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform(); |

2005 | QBezier unflipped = bezier; |

2006 | QBezier flipped = bezier.mapBy(flip); |

2007 | |

2008 | qreal t0 = 0, t1 = 1; |

2009 | int stationary = flipped.stationaryYPoints(t0, t1); |

2010 | |

2011 | qreal segments[4]; |

2012 | QPointF points[4]; |

2013 | points[0] = unflipped.pt1(); |

2014 | segments[0] = 0; |

2015 | |

2016 | int segmentCount = 0; |

2017 | if (stationary > 0) { |

2018 | ++segmentCount; |

2019 | segments[segmentCount] = t0; |

2020 | points[segmentCount] = unflipped.pointAt(t0); |

2021 | } |

2022 | if (stationary > 1) { |

2023 | ++segmentCount; |

2024 | segments[segmentCount] = t1; |

2025 | points[segmentCount] = unflipped.pointAt(t1); |

2026 | } |

2027 | ++segmentCount; |

2028 | segments[segmentCount] = 1; |

2029 | points[segmentCount] = unflipped.pt4(); |

2030 | |

2031 | qreal lastIntersection = 0; |

2032 | for (int i = 0; i < segmentCount; ++i) { |

2033 | outA = compare<edge>(points[i], t); |

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

2035 | |

2036 | if (outA != outB) { |

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

2038 | |

2039 | if (outB) |

2040 | addBezier(result, unflipped.getSubRange(lastIntersection, intersection)); |

2041 | |

2042 | lastIntersection = intersection; |

2043 | } |

2044 | } |

2045 | |

2046 | if (!outB) |

2047 | addBezier(result, unflipped.getSubRange(lastIntersection, 1)); |

2048 | } |

2049 | |

2050 | // clips a single subpath against a single edge |

2051 | template <Edge edge> |

2052 | QPainterPath clip(const QPainterPath &path, qreal t) |

2053 | { |

2054 | QPainterPath result; |

2055 | for (int i = 1; i < path.elementCount(); ++i) { |

2056 | const QPainterPath::Element &element = path.elementAt(i); |

2057 | Q_ASSERT(!element.isMoveTo()); |

2058 | if (element.isLineTo()) { |

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

2060 | } else { |

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

2062 | i += 2; |

2063 | } |

2064 | } |

2065 | |

2066 | int last = path.elementCount() - 1; |

2067 | if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0))) |

2068 | clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result); |

2069 | |

2070 | return result; |

2071 | } |

2072 | |

2073 | QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect) |

2074 | { |

2075 | QVector<QPainterPath> subpaths = toSubpaths(path); |

2076 | |

2077 | QPainterPath result; |

2078 | result.setFillRule(path.fillRule()); |

2079 | for (int i = 0; i < subpaths.size(); ++i) { |

2080 | QPainterPath subPath = subpaths.at(i); |

2081 | QRectF bounds = subPath.boundingRect(); |

2082 | if (bounds.intersects(rect)) { |

2083 | if (bounds.left() < rect.left()) |

2084 | subPath = clip<Left>(subPath, rect.left()); |

2085 | if (bounds.right() > rect.right()) |

2086 | subPath = clip<Right>(subPath, rect.right()); |

2087 | |

2088 | bounds = subPath.boundingRect(); |

2089 | |

2090 | if (bounds.top() < rect.top()) |

2091 | subPath = clip<Top>(subPath, rect.top()); |

2092 | if (bounds.bottom() > rect.bottom()) |

2093 | subPath = clip<Bottom>(subPath, rect.bottom()); |

2094 | |

2095 | if (subPath.elementCount() > 1) |

2096 | result.addPath(subPath); |

2097 | } |

2098 | } |

2099 | // The algorithm above might return one side of \a rect if there was no intersection, |

2100 | // so only return intersections that are not empty rectangles. |

2101 | if (result.boundingRect().isEmpty()) |

2102 | return QPainterPath(); |

2103 | else |

2104 | return result; |

2105 | } |

2106 | |

2107 | } |

2108 | |

2109 | QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect) |

2110 | { |

2111 | return intersectPath(path, rect); |

2112 | } |

2113 | |

2114 | QT_END_NAMESPACE |

2115 |