| /**************************************************************************** |
| ** |
| ** Copyright (C) 2016 The Qt Company Ltd. |
| ** Contact: https://www.qt.io/licensing/ |
| ** |
| ** This file is part of the QtGui module of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:LGPL$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see https://www.qt.io/terms-conditions. For further |
| ** information use the contact form at https://www.qt.io/contact-us. |
| ** |
| ** GNU Lesser General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU Lesser |
| ** General Public License version 3 as published by the Free Software |
| ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
| ** packaging of this file. Please review the following information to |
| ** ensure the GNU Lesser General Public License version 3 requirements |
| ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
| ** |
| ** GNU General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU |
| ** General Public License version 2.0 or (at your option) the GNU General |
| ** Public license version 3 or any later version approved by the KDE Free |
| ** Qt Foundation. The licenses are as published by the Free Software |
| ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
| ** included in the packaging of this file. Please review the following |
| ** information to ensure the GNU General Public License requirements will |
| ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
| ** https://www.gnu.org/licenses/gpl-3.0.html. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #include "qpathclipper_p.h" |
| |
| #include <private/qbezier_p.h> |
| #include <private/qdatabuffer_p.h> |
| #include <private/qnumeric_p.h> |
| #include <qmath.h> |
| #include <algorithm> |
| |
| /** |
| The algorithm is as follows: |
| |
| 1. Find all intersections between the two paths (including self-intersections), |
| and build a winged edge structure of non-intersecting parts. |
| 2. While there are more unhandled edges: |
| 3. Pick a y-coordinate from an unhandled edge. |
| 4. Intersect the horizontal line at y-coordinate with all edges. |
| 5. Traverse intersections left to right deciding whether each subpath should be added or not. |
| 6. If the subpath should be added, traverse the winged-edge structure and add the edges to |
| a separate winged edge structure. |
| 7. Mark all edges in subpaths crossing the horizontal line as handled. |
| 8. (Optional) Simplify the resulting winged edge structure by merging shared edges. |
| 9. Convert the resulting winged edge structure to a painter path. |
| */ |
| |
| #include <qdebug.h> |
| |
| QT_BEGIN_NAMESPACE |
| |
| static inline bool fuzzyIsNull(qreal d) |
| { |
| if (sizeof(qreal) == sizeof(double)) |
| return qAbs(d) <= 1e-12; |
| else |
| return qAbs(d) <= 1e-5f; |
| } |
| |
| static inline bool comparePoints(const QPointF &a, const QPointF &b) |
| { |
| return fuzzyIsNull(a.x() - b.x()) |
| && fuzzyIsNull(a.y() - b.y()); |
| } |
| |
| //#define QDEBUG_CLIPPER |
| static qreal dot(const QPointF &a, const QPointF &b) |
| { |
| return a.x() * b.x() + a.y() * b.y(); |
| } |
| |
| static void normalize(double &x, double &y) |
| { |
| double reciprocal = 1 / qSqrt(x * x + y * y); |
| x *= reciprocal; |
| y *= reciprocal; |
| } |
| |
| struct QIntersection |
| { |
| qreal alphaA; |
| qreal alphaB; |
| |
| QPointF pos; |
| }; |
| |
| class QIntersectionFinder |
| { |
| public: |
| void produceIntersections(QPathSegments &segments); |
| bool hasIntersections(const QPathSegments &a, const QPathSegments &b) const; |
| |
| private: |
| bool linesIntersect(const QLineF &a, const QLineF &b) const; |
| }; |
| |
| bool QIntersectionFinder::linesIntersect(const QLineF &a, const QLineF &b) const |
| { |
| const QPointF p1 = a.p1(); |
| const QPointF p2 = a.p2(); |
| |
| const QPointF q1 = b.p1(); |
| const QPointF q2 = b.p2(); |
| |
| if (comparePoints(p1, p2) || comparePoints(q1, q2)) |
| return false; |
| |
| const bool p1_equals_q1 = comparePoints(p1, q1); |
| const bool p2_equals_q2 = comparePoints(p2, q2); |
| |
| if (p1_equals_q1 && p2_equals_q2) |
| return true; |
| |
| const bool p1_equals_q2 = comparePoints(p1, q2); |
| const bool p2_equals_q1 = comparePoints(p2, q1); |
| |
| if (p1_equals_q2 && p2_equals_q1) |
| return true; |
| |
| const QPointF pDelta = p2 - p1; |
| const QPointF qDelta = q2 - q1; |
| |
| const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x(); |
| |
| if (qFuzzyIsNull(par)) { |
| const QPointF normal(-pDelta.y(), pDelta.x()); |
| |
| // coinciding? |
| if (qFuzzyIsNull(dot(normal, q1 - p1))) { |
| const qreal dp = dot(pDelta, pDelta); |
| |
| const qreal tq1 = dot(pDelta, q1 - p1); |
| const qreal tq2 = dot(pDelta, q2 - p1); |
| |
| if ((tq1 > 0 && tq1 < dp) || (tq2 > 0 && tq2 < dp)) |
| return true; |
| |
| const qreal dq = dot(qDelta, qDelta); |
| |
| const qreal tp1 = dot(qDelta, p1 - q1); |
| const qreal tp2 = dot(qDelta, p2 - q1); |
| |
| if ((tp1 > 0 && tp1 < dq) || (tp2 > 0 && tp2 < dq)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| const qreal invPar = 1 / par; |
| |
| const qreal tp = (qDelta.y() * (q1.x() - p1.x()) - |
| qDelta.x() * (q1.y() - p1.y())) * invPar; |
| |
| if (tp < 0 || tp > 1) |
| return false; |
| |
| const qreal tq = (pDelta.y() * (q1.x() - p1.x()) - |
| pDelta.x() * (q1.y() - p1.y())) * invPar; |
| |
| return tq >= 0 && tq <= 1; |
| } |
| |
| bool QIntersectionFinder::hasIntersections(const QPathSegments &a, const QPathSegments &b) const |
| { |
| if (a.segments() == 0 || b.segments() == 0) |
| return false; |
| |
| const QRectF &rb0 = b.elementBounds(0); |
| |
| qreal minX = rb0.left(); |
| qreal minY = rb0.top(); |
| qreal maxX = rb0.right(); |
| qreal maxY = rb0.bottom(); |
| |
| for (int i = 1; i < b.segments(); ++i) { |
| const QRectF &r = b.elementBounds(i); |
| minX = qMin(minX, r.left()); |
| minY = qMin(minY, r.top()); |
| maxX = qMax(maxX, r.right()); |
| maxY = qMax(maxY, r.bottom()); |
| } |
| |
| QRectF rb(minX, minY, maxX - minX, maxY - minY); |
| |
| for (int i = 0; i < a.segments(); ++i) { |
| const QRectF &r1 = a.elementBounds(i); |
| |
| if (r1.left() > rb.right() || rb.left() > r1.right()) |
| continue; |
| if (r1.top() > rb.bottom() || rb.top() > r1.bottom()) |
| continue; |
| |
| for (int j = 0; j < b.segments(); ++j) { |
| const QRectF &r2 = b.elementBounds(j); |
| |
| if (r1.left() > r2.right() || r2.left() > r1.right()) |
| continue; |
| if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) |
| continue; |
| |
| if (linesIntersect(a.lineAt(i), b.lineAt(j))) |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| namespace { |
| struct TreeNode |
| { |
| qreal splitLeft; |
| qreal splitRight; |
| bool leaf; |
| |
| int lowestLeftIndex; |
| int lowestRightIndex; |
| |
| union { |
| struct { |
| int first; |
| int last; |
| } interval; |
| struct { |
| int left; |
| int right; |
| } children; |
| } index; |
| }; |
| |
| struct RectF |
| { |
| qreal x1; |
| qreal y1; |
| qreal x2; |
| qreal y2; |
| }; |
| |
| class SegmentTree |
| { |
| public: |
| SegmentTree(QPathSegments &segments); |
| |
| void produceIntersections(int segment); |
| |
| private: |
| TreeNode buildTree(int first, int last, int depth, const RectF &bounds); |
| |
| void produceIntersectionsLeaf(const TreeNode &node, int segment); |
| void produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis); |
| void intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections); |
| |
| QPathSegments &m_segments; |
| QVector<int> m_index; |
| |
| RectF m_bounds; |
| |
| QVector<TreeNode> m_tree; |
| QDataBuffer<QIntersection> m_intersections; |
| }; |
| |
| SegmentTree::SegmentTree(QPathSegments &segments) |
| : m_segments(segments), |
| m_intersections(0) |
| { |
| m_bounds.x1 = qt_inf(); |
| m_bounds.y1 = qt_inf(); |
| m_bounds.x2 = -qt_inf(); |
| m_bounds.y2 = -qt_inf(); |
| |
| m_index.resize(m_segments.segments()); |
| |
| for (int i = 0; i < m_index.size(); ++i) { |
| m_index[i] = i; |
| |
| const QRectF &segmentBounds = m_segments.elementBounds(i); |
| |
| if (segmentBounds.left() < m_bounds.x1) |
| m_bounds.x1 = segmentBounds.left(); |
| if (segmentBounds.top() < m_bounds.y1) |
| m_bounds.y1 = segmentBounds.top(); |
| if (segmentBounds.right() > m_bounds.x2) |
| m_bounds.x2 = segmentBounds.right(); |
| if (segmentBounds.bottom() > m_bounds.y2) |
| m_bounds.y2 = segmentBounds.bottom(); |
| } |
| |
| m_tree.resize(1); |
| |
| TreeNode root = buildTree(0, m_index.size(), 0, m_bounds); |
| m_tree[0] = root; |
| } |
| |
| static inline qreal coordinate(const QPointF &pos, int axis) |
| { |
| return axis == 0 ? pos.x() : pos.y(); |
| } |
| |
| TreeNode SegmentTree::buildTree(int first, int last, int depth, const RectF &bounds) |
| { |
| if (depth >= 24 || (last - first) <= 10) { |
| TreeNode node = {}; |
| node.leaf = true; |
| node.index.interval.first = first; |
| node.index.interval.last = last; |
| |
| return node; |
| } |
| |
| int splitAxis = (depth & 1); |
| |
| TreeNode node; |
| node.leaf = false; |
| |
| qreal split = 0.5f * ((&bounds.x1)[splitAxis] + (&bounds.x2)[splitAxis]); |
| |
| node.splitLeft = (&bounds.x1)[splitAxis]; |
| node.splitRight = (&bounds.x2)[splitAxis]; |
| |
| node.lowestLeftIndex = INT_MAX; |
| node.lowestRightIndex = INT_MAX; |
| |
| const int treeSize = m_tree.size(); |
| |
| node.index.children.left = treeSize; |
| node.index.children.right = treeSize + 1; |
| |
| m_tree.resize(treeSize + 2); |
| |
| int l = first; |
| int r = last - 1; |
| |
| // partition into left and right sets |
| while (l <= r) { |
| const int index = m_index.at(l); |
| const QRectF &segmentBounds = m_segments.elementBounds(index); |
| |
| qreal lowCoordinate = coordinate(segmentBounds.topLeft(), splitAxis); |
| |
| if (coordinate(segmentBounds.center(), splitAxis) < split) { |
| qreal highCoordinate = coordinate(segmentBounds.bottomRight(), splitAxis); |
| if (highCoordinate > node.splitLeft) |
| node.splitLeft = highCoordinate; |
| if (index < node.lowestLeftIndex) |
| node.lowestLeftIndex = index; |
| ++l; |
| } else { |
| if (lowCoordinate < node.splitRight) |
| node.splitRight = lowCoordinate; |
| if (index < node.lowestRightIndex) |
| node.lowestRightIndex = index; |
| qSwap(m_index[l], m_index[r]); |
| --r; |
| } |
| } |
| |
| RectF lbounds = bounds; |
| (&lbounds.x2)[splitAxis] = node.splitLeft; |
| |
| RectF rbounds = bounds; |
| (&rbounds.x1)[splitAxis] = node.splitRight; |
| |
| TreeNode left = buildTree(first, l, depth + 1, lbounds); |
| m_tree[node.index.children.left] = left; |
| |
| TreeNode right = buildTree(l, last, depth + 1, rbounds); |
| m_tree[node.index.children.right] = right; |
| |
| return node; |
| } |
| |
| void SegmentTree::intersectLines(const QLineF &a, const QLineF &b, QDataBuffer<QIntersection> &intersections) |
| { |
| const QPointF p1 = a.p1(); |
| const QPointF p2 = a.p2(); |
| |
| const QPointF q1 = b.p1(); |
| const QPointF q2 = b.p2(); |
| |
| if (comparePoints(p1, p2) || comparePoints(q1, q2)) |
| return; |
| |
| const bool p1_equals_q1 = comparePoints(p1, q1); |
| const bool p2_equals_q2 = comparePoints(p2, q2); |
| |
| if (p1_equals_q1 && p2_equals_q2) |
| return; |
| |
| const bool p1_equals_q2 = comparePoints(p1, q2); |
| const bool p2_equals_q1 = comparePoints(p2, q1); |
| |
| if (p1_equals_q2 && p2_equals_q1) |
| return; |
| |
| const QPointF pDelta = p2 - p1; |
| const QPointF qDelta = q2 - q1; |
| |
| const qreal par = pDelta.x() * qDelta.y() - pDelta.y() * qDelta.x(); |
| |
| if (qFuzzyIsNull(par)) { |
| const QPointF normal(-pDelta.y(), pDelta.x()); |
| |
| // coinciding? |
| if (qFuzzyIsNull(dot(normal, q1 - p1))) { |
| const qreal invDp = 1 / dot(pDelta, pDelta); |
| |
| const qreal tq1 = dot(pDelta, q1 - p1) * invDp; |
| const qreal tq2 = dot(pDelta, q2 - p1) * invDp; |
| |
| if (tq1 > 0 && tq1 < 1) { |
| QIntersection intersection; |
| intersection.alphaA = tq1; |
| intersection.alphaB = 0; |
| intersection.pos = q1; |
| intersections.add(intersection); |
| } |
| |
| if (tq2 > 0 && tq2 < 1) { |
| QIntersection intersection; |
| intersection.alphaA = tq2; |
| intersection.alphaB = 1; |
| intersection.pos = q2; |
| intersections.add(intersection); |
| } |
| |
| const qreal invDq = 1 / dot(qDelta, qDelta); |
| |
| const qreal tp1 = dot(qDelta, p1 - q1) * invDq; |
| const qreal tp2 = dot(qDelta, p2 - q1) * invDq; |
| |
| if (tp1 > 0 && tp1 < 1) { |
| QIntersection intersection; |
| intersection.alphaA = 0; |
| intersection.alphaB = tp1; |
| intersection.pos = p1; |
| intersections.add(intersection); |
| } |
| |
| if (tp2 > 0 && tp2 < 1) { |
| QIntersection intersection; |
| intersection.alphaA = 1; |
| intersection.alphaB = tp2; |
| intersection.pos = p2; |
| intersections.add(intersection); |
| } |
| } |
| |
| return; |
| } |
| |
| // if the lines are not parallel and share a common end point, then they |
| // don't intersect |
| if (p1_equals_q1 || p1_equals_q2 || p2_equals_q1 || p2_equals_q2) |
| return; |
| |
| |
| const qreal tp = (qDelta.y() * (q1.x() - p1.x()) - |
| qDelta.x() * (q1.y() - p1.y())) / par; |
| const qreal tq = (pDelta.y() * (q1.x() - p1.x()) - |
| pDelta.x() * (q1.y() - p1.y())) / par; |
| |
| if (tp<0 || tp>1 || tq<0 || tq>1) |
| return; |
| |
| const bool p_zero = qFuzzyIsNull(tp); |
| const bool p_one = qFuzzyIsNull(tp - 1); |
| |
| const bool q_zero = qFuzzyIsNull(tq); |
| const bool q_one = qFuzzyIsNull(tq - 1); |
| |
| if ((q_zero || q_one) && (p_zero || p_one)) |
| return; |
| |
| QPointF pt; |
| if (p_zero) { |
| pt = p1; |
| } else if (p_one) { |
| pt = p2; |
| } else if (q_zero) { |
| pt = q1; |
| } else if (q_one) { |
| pt = q2; |
| } else { |
| pt = q1 + (q2 - q1) * tq; |
| } |
| |
| QIntersection intersection; |
| intersection.alphaA = tp; |
| intersection.alphaB = tq; |
| intersection.pos = pt; |
| intersections.add(intersection); |
| } |
| |
| void SegmentTree::produceIntersections(int segment) |
| { |
| const QRectF &segmentBounds = m_segments.elementBounds(segment); |
| |
| RectF sbounds; |
| sbounds.x1 = segmentBounds.left(); |
| sbounds.y1 = segmentBounds.top(); |
| sbounds.x2 = segmentBounds.right(); |
| sbounds.y2 = segmentBounds.bottom(); |
| |
| produceIntersections(m_tree.at(0), segment, sbounds, m_bounds, 0); |
| } |
| |
| void SegmentTree::produceIntersectionsLeaf(const TreeNode &node, int segment) |
| { |
| const QRectF &r1 = m_segments.elementBounds(segment); |
| const QLineF lineA = m_segments.lineAt(segment); |
| |
| for (int i = node.index.interval.first; i < node.index.interval.last; ++i) { |
| const int other = m_index.at(i); |
| if (other >= segment) |
| continue; |
| |
| const QRectF &r2 = m_segments.elementBounds(other); |
| |
| if (r1.left() > r2.right() || r2.left() > r1.right()) |
| continue; |
| if (r1.top() > r2.bottom() || r2.top() > r1.bottom()) |
| continue; |
| |
| m_intersections.reset(); |
| |
| const QLineF lineB = m_segments.lineAt(other); |
| |
| intersectLines(lineA, lineB, m_intersections); |
| |
| for (int k = 0; k < m_intersections.size(); ++k) { |
| QPathSegments::Intersection i_isect, j_isect; |
| i_isect.t = m_intersections.at(k).alphaA; |
| j_isect.t = m_intersections.at(k).alphaB; |
| |
| i_isect.vertex = j_isect.vertex = m_segments.addPoint(m_intersections.at(k).pos); |
| |
| i_isect.next = 0; |
| j_isect.next = 0; |
| |
| m_segments.addIntersection(segment, i_isect); |
| m_segments.addIntersection(other, j_isect); |
| } |
| } |
| } |
| |
| void SegmentTree::produceIntersections(const TreeNode &node, int segment, const RectF &segmentBounds, const RectF &nodeBounds, int axis) |
| { |
| if (node.leaf) { |
| produceIntersectionsLeaf(node, segment); |
| return; |
| } |
| |
| RectF lbounds = nodeBounds; |
| (&lbounds.x2)[axis] = node.splitLeft; |
| |
| RectF rbounds = nodeBounds; |
| (&rbounds.x1)[axis] = node.splitRight; |
| |
| if (segment > node.lowestLeftIndex && (&segmentBounds.x1)[axis] <= node.splitLeft) |
| produceIntersections(m_tree.at(node.index.children.left), segment, segmentBounds, lbounds, !axis); |
| |
| if (segment > node.lowestRightIndex && (&segmentBounds.x2)[axis] >= node.splitRight) |
| produceIntersections(m_tree.at(node.index.children.right), segment, segmentBounds, rbounds, !axis); |
| } |
| |
| } |
| |
| void QIntersectionFinder::produceIntersections(QPathSegments &segments) |
| { |
| SegmentTree tree(segments); |
| |
| for (int i = 0; i < segments.segments(); ++i) |
| tree.produceIntersections(i); |
| } |
| |
| class QKdPointTree |
| { |
| public: |
| enum Traversal { |
| TraverseBoth, |
| TraverseLeft, |
| TraverseRight, |
| TraverseNone |
| }; |
| |
| struct Node { |
| int point; |
| int id; |
| |
| Node *left; |
| Node *right; |
| }; |
| |
| QKdPointTree(const QPathSegments &segments) |
| : m_segments(&segments) |
| , m_nodes(m_segments->points()) |
| , m_id(0) |
| { |
| m_nodes.resize(m_segments->points()); |
| |
| for (int i = 0; i < m_nodes.size(); ++i) { |
| m_nodes.at(i).point = i; |
| m_nodes.at(i).id = -1; |
| } |
| |
| m_rootNode = build(0, m_nodes.size()); |
| } |
| |
| int build(int begin, int end, int depth = 0); |
| |
| Node *rootNode() |
| { |
| return &m_nodes.at(m_rootNode); |
| } |
| |
| inline int nextId() |
| { |
| return m_id++; |
| } |
| |
| private: |
| const QPathSegments *m_segments; |
| QDataBuffer<Node> m_nodes; |
| |
| int m_rootNode; |
| int m_id; |
| }; |
| |
| template <typename T> |
| void qTraverseKdPointTree(QKdPointTree::Node &node, T &t, int depth = 0) |
| { |
| QKdPointTree::Traversal status = t(node, depth); |
| |
| const bool traverseRight = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseRight); |
| const bool traverseLeft = (status == QKdPointTree::TraverseBoth || status == QKdPointTree::TraverseLeft); |
| |
| if (traverseLeft && node.left) |
| QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.left, t, depth + 1); |
| |
| if (traverseRight && node.right) |
| QT_PREPEND_NAMESPACE(qTraverseKdPointTree<T>)(*node.right, t, depth + 1); |
| } |
| |
| static inline qreal component(const QPointF &point, unsigned int i) |
| { |
| Q_ASSERT(i < 2); |
| const qreal components[] = { point.x(), point.y() }; |
| return components[i]; |
| } |
| |
| int QKdPointTree::build(int begin, int end, int depth) |
| { |
| Q_ASSERT(end > begin); |
| |
| const qreal pivot = component(m_segments->pointAt(m_nodes.at(begin).point), depth & 1); |
| |
| int first = begin + 1; |
| int last = end - 1; |
| |
| while (first <= last) { |
| const qreal value = component(m_segments->pointAt(m_nodes.at(first).point), depth & 1); |
| |
| if (value < pivot) |
| ++first; |
| else { |
| qSwap(m_nodes.at(first), m_nodes.at(last)); |
| --last; |
| } |
| } |
| |
| qSwap(m_nodes.at(last), m_nodes.at(begin)); |
| |
| if (last > begin) |
| m_nodes.at(last).left = &m_nodes.at(build(begin, last, depth + 1)); |
| else |
| m_nodes.at(last).left = nullptr; |
| |
| if (last + 1 < end) |
| m_nodes.at(last).right = &m_nodes.at(build(last + 1, end, depth + 1)); |
| else |
| m_nodes.at(last).right = nullptr; |
| |
| return last; |
| } |
| |
| class QKdPointFinder |
| { |
| public: |
| QKdPointFinder(int point, const QPathSegments &segments, QKdPointTree &tree) |
| : m_result(-1) |
| , m_segments(&segments) |
| , m_tree(&tree) |
| { |
| pointComponents[0] = segments.pointAt(point).x(); |
| pointComponents[1] = segments.pointAt(point).y(); |
| } |
| |
| inline QKdPointTree::Traversal operator()(QKdPointTree::Node &node, int depth) |
| { |
| if (m_result != -1) |
| return QKdPointTree::TraverseNone; |
| |
| const QPointF &nodePoint = m_segments->pointAt(node.point); |
| |
| const qreal pivotComponents[] = { nodePoint.x(), nodePoint.y() }; |
| |
| const qreal pivot = pivotComponents[depth & 1]; |
| const qreal value = pointComponents[depth & 1]; |
| |
| if (fuzzyIsNull(pivot - value)) { |
| const qreal pivot2 = pivotComponents[(depth + 1) & 1]; |
| const qreal value2 = pointComponents[(depth + 1) & 1]; |
| |
| if (fuzzyIsNull(pivot2 - value2)) { |
| if (node.id < 0) |
| node.id = m_tree->nextId(); |
| |
| m_result = node.id; |
| return QKdPointTree::TraverseNone; |
| } else |
| return QKdPointTree::TraverseBoth; |
| } else if (value < pivot) { |
| return QKdPointTree::TraverseLeft; |
| } else { |
| return QKdPointTree::TraverseRight; |
| } |
| } |
| |
| int result() const |
| { |
| return m_result; |
| } |
| |
| private: |
| qreal pointComponents[2]; |
| int m_result; |
| const QPathSegments *m_segments; |
| QKdPointTree *m_tree; |
| }; |
| |
| // merge all points that are within qFuzzyCompare range of each other |
| void QPathSegments::mergePoints() |
| { |
| QKdPointTree tree(*this); |
| |
| if (tree.rootNode()) { |
| QDataBuffer<QPointF> mergedPoints(points()); |
| QDataBuffer<int> pointIndices(points()); |
| |
| for (int i = 0; i < points(); ++i) { |
| QKdPointFinder finder(i, *this, tree); |
| QT_PREPEND_NAMESPACE(qTraverseKdPointTree<QKdPointFinder>)(*tree.rootNode(), finder); |
| |
| Q_ASSERT(finder.result() != -1); |
| |
| if (finder.result() >= mergedPoints.size()) |
| mergedPoints << m_points.at(i); |
| |
| pointIndices << finder.result(); |
| } |
| |
| for (int i = 0; i < m_segments.size(); ++i) { |
| m_segments.at(i).va = pointIndices.at(m_segments.at(i).va); |
| m_segments.at(i).vb = pointIndices.at(m_segments.at(i).vb); |
| } |
| |
| for (int i = 0; i < m_intersections.size(); ++i) |
| m_intersections.at(i).vertex = pointIndices.at(m_intersections.at(i).vertex); |
| |
| m_points.swap(mergedPoints); |
| } |
| } |
| |
| void QWingedEdge::intersectAndAdd() |
| { |
| QIntersectionFinder finder; |
| finder.produceIntersections(m_segments); |
| |
| m_segments.mergePoints(); |
| |
| for (int i = 0; i < m_segments.points(); ++i) |
| addVertex(m_segments.pointAt(i)); |
| |
| QDataBuffer<QPathSegments::Intersection> intersections(m_segments.segments()); |
| for (int i = 0; i < m_segments.segments(); ++i) { |
| intersections.reset(); |
| |
| int pathId = m_segments.pathId(i); |
| |
| const QPathSegments::Intersection *isect = m_segments.intersectionAt(i); |
| while (isect) { |
| intersections << *isect; |
| |
| if (isect->next) { |
| isect += isect->next; |
| } else { |
| isect = nullptr; |
| } |
| } |
| |
| std::sort(intersections.data(), intersections.data() + intersections.size()); |
| |
| int first = m_segments.segmentAt(i).va; |
| int second = m_segments.segmentAt(i).vb; |
| |
| int last = first; |
| for (int j = 0; j < intersections.size(); ++j) { |
| const QPathSegments::Intersection &isect = intersections.at(j); |
| |
| QPathEdge *ep = edge(addEdge(last, isect.vertex)); |
| |
| if (ep) { |
| const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(isect.vertex).y() ? 1 : -1; |
| if (pathId == 0) |
| ep->windingA += dir; |
| else |
| ep->windingB += dir; |
| } |
| |
| last = isect.vertex; |
| } |
| |
| QPathEdge *ep = edge(addEdge(last, second)); |
| |
| if (ep) { |
| const int dir = m_segments.pointAt(last).y() < m_segments.pointAt(second).y() ? 1 : -1; |
| if (pathId == 0) |
| ep->windingA += dir; |
| else |
| ep->windingB += dir; |
| } |
| } |
| } |
| |
| QWingedEdge::QWingedEdge() : |
| m_edges(0), |
| m_vertices(0), |
| m_segments(0) |
| { |
| } |
| |
| QWingedEdge::QWingedEdge(const QPainterPath &subject, const QPainterPath &clip) : |
| m_edges(subject.elementCount()), |
| m_vertices(subject.elementCount()), |
| m_segments(subject.elementCount()) |
| { |
| m_segments.setPath(subject); |
| m_segments.addPath(clip); |
| |
| intersectAndAdd(); |
| } |
| |
| QWingedEdge::TraversalStatus QWingedEdge::next(const QWingedEdge::TraversalStatus &status) const |
| { |
| const QPathEdge *sp = edge(status.edge); |
| Q_ASSERT(sp); |
| |
| TraversalStatus result; |
| result.edge = sp->next(status.traversal, status.direction); |
| result.traversal = status.traversal; |
| result.direction = status.direction; |
| |
| const QPathEdge *rp = edge(result.edge); |
| Q_ASSERT(rp); |
| |
| if (sp->vertex(status.direction) == rp->vertex(status.direction)) |
| result.flip(); |
| |
| return result; |
| } |
| |
| static bool isLine(const QBezier &bezier) |
| { |
| const bool equal_1_2 = comparePoints(bezier.pt1(), bezier.pt2()); |
| const bool equal_2_3 = comparePoints(bezier.pt2(), bezier.pt3()); |
| const bool equal_3_4 = comparePoints(bezier.pt3(), bezier.pt4()); |
| |
| // point? |
| if (equal_1_2 && equal_2_3 && equal_3_4) |
| return true; |
| |
| if (comparePoints(bezier.pt1(), bezier.pt4())) |
| return equal_1_2 || equal_3_4; |
| |
| return (equal_1_2 && equal_3_4) || (equal_1_2 && equal_2_3) || (equal_2_3 && equal_3_4); |
| } |
| |
| void QPathSegments::setPath(const QPainterPath &path) |
| { |
| m_points.reset(); |
| m_intersections.reset(); |
| m_segments.reset(); |
| |
| m_pathId = 0; |
| |
| addPath(path); |
| } |
| |
| void QPathSegments::addPath(const QPainterPath &path) |
| { |
| int firstSegment = m_segments.size(); |
| |
| bool hasMoveTo = false; |
| int lastMoveTo = 0; |
| int last = 0; |
| for (int i = 0; i < path.elementCount(); ++i) { |
| int current = m_points.size(); |
| |
| QPointF currentPoint; |
| if (path.elementAt(i).type == QPainterPath::CurveToElement) |
| currentPoint = path.elementAt(i+2); |
| else |
| currentPoint = path.elementAt(i); |
| |
| if (i > 0 && comparePoints(m_points.at(lastMoveTo), currentPoint)) |
| current = lastMoveTo; |
| else |
| m_points << currentPoint; |
| |
| switch (path.elementAt(i).type) { |
| case QPainterPath::MoveToElement: |
| if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo))) |
| m_segments << Segment(m_pathId, last, lastMoveTo); |
| hasMoveTo = true; |
| last = lastMoveTo = current; |
| break; |
| case QPainterPath::LineToElement: |
| m_segments << Segment(m_pathId, last, current); |
| last = current; |
| break; |
| case QPainterPath::CurveToElement: |
| { |
| QBezier bezier = QBezier::fromPoints(m_points.at(last), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2)); |
| if (isLine(bezier)) { |
| m_segments << Segment(m_pathId, last, current); |
| } else { |
| QRectF bounds = bezier.bounds(); |
| |
| // threshold based on similar algorithm as in qtriangulatingstroker.cpp |
| int threshold = qMin<float>(64, qMax(bounds.width(), bounds.height()) * (2 * qreal(3.14) / 6)); |
| |
| if (threshold < 3) threshold = 3; |
| qreal one_over_threshold_minus_1 = qreal(1) / (threshold - 1); |
| |
| for (int t = 1; t < threshold - 1; ++t) { |
| currentPoint = bezier.pointAt(t * one_over_threshold_minus_1); |
| |
| int index = m_points.size(); |
| m_segments << Segment(m_pathId, last, index); |
| last = index; |
| |
| m_points << currentPoint; |
| } |
| |
| m_segments << Segment(m_pathId, last, current); |
| } |
| } |
| last = current; |
| i += 2; |
| break; |
| default: |
| Q_ASSERT(false); |
| break; |
| } |
| } |
| |
| if (hasMoveTo && last != lastMoveTo && !comparePoints(m_points.at(last), m_points.at(lastMoveTo))) |
| m_segments << Segment(m_pathId, last, lastMoveTo); |
| |
| for (int i = firstSegment; i < m_segments.size(); ++i) { |
| const QLineF line = lineAt(i); |
| |
| qreal x1 = line.p1().x(); |
| qreal y1 = line.p1().y(); |
| qreal x2 = line.p2().x(); |
| qreal y2 = line.p2().y(); |
| |
| if (x2 < x1) |
| qSwap(x1, x2); |
| if (y2 < y1) |
| qSwap(y1, y2); |
| |
| m_segments.at(i).bounds = QRectF(x1, y1, x2 - x1, y2 - y1); |
| } |
| |
| ++m_pathId; |
| } |
| |
| qreal QWingedEdge::delta(int vertex, int a, int b) const |
| { |
| const QPathEdge *ap = edge(a); |
| const QPathEdge *bp = edge(b); |
| |
| double a_angle = ap->angle; |
| double b_angle = bp->angle; |
| |
| if (vertex == ap->second) |
| a_angle = ap->invAngle; |
| |
| if (vertex == bp->second) |
| b_angle = bp->invAngle; |
| |
| double result = b_angle - a_angle; |
| |
| if (result >= 128.) |
| return result - 128.; |
| else if (result < 0) |
| return result + 128.; |
| else |
| return result; |
| } |
| |
| QWingedEdge::TraversalStatus QWingedEdge::findInsertStatus(int vi, int ei) const |
| { |
| const QPathVertex *vp = vertex(vi); |
| |
| Q_ASSERT(vp); |
| Q_ASSERT(ei >= 0); |
| Q_ASSERT(vp->edge >= 0); |
| |
| int position = vp->edge; |
| qreal d = 128.; |
| |
| TraversalStatus status; |
| status.direction = edge(vp->edge)->directionTo(vi); |
| status.traversal = QPathEdge::RightTraversal; |
| status.edge = vp->edge; |
| |
| #ifdef QDEBUG_CLIPPER |
| const QPathEdge *ep = edge(ei); |
| qDebug() << "Finding insert status for edge" << ei << "at vertex" << QPointF(*vp) << ", angles: " << ep->angle << ep->invAngle; |
| #endif |
| |
| do { |
| status = next(status); |
| status.flip(); |
| |
| Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi); |
| qreal d2 = delta(vi, ei, status.edge); |
| |
| #ifdef QDEBUG_CLIPPER |
| const QPathEdge *op = edge(status.edge); |
| qDebug() << "Delta to edge" << status.edge << d2 << ", angles: " << op->angle << op->invAngle; |
| #endif |
| |
| if (d2 < d) { |
| position = status.edge; |
| d = d2; |
| } |
| } while (status.edge != vp->edge); |
| |
| status.traversal = QPathEdge::LeftTraversal; |
| status.direction = QPathEdge::Forward; |
| status.edge = position; |
| |
| if (edge(status.edge)->vertex(status.direction) != vi) |
| status.flip(); |
| |
| #ifdef QDEBUG_CLIPPER |
| qDebug() << "Inserting edge" << ei << "to" << (status.traversal == QPathEdge::LeftTraversal ? "left" : "right") << "of edge" << status.edge; |
| #endif |
| |
| Q_ASSERT(edge(status.edge)->vertex(status.direction) == vi); |
| |
| return status; |
| } |
| |
| void QWingedEdge::removeEdge(int ei) |
| { |
| QPathEdge *ep = edge(ei); |
| |
| TraversalStatus status; |
| status.direction = QPathEdge::Forward; |
| status.traversal = QPathEdge::RightTraversal; |
| status.edge = ei; |
| |
| TraversalStatus forwardRight = next(status); |
| forwardRight.flipDirection(); |
| |
| status.traversal = QPathEdge::LeftTraversal; |
| TraversalStatus forwardLeft = next(status); |
| forwardLeft.flipDirection(); |
| |
| status.direction = QPathEdge::Backward; |
| TraversalStatus backwardLeft = next(status); |
| backwardLeft.flipDirection(); |
| |
| status.traversal = QPathEdge::RightTraversal; |
| TraversalStatus backwardRight = next(status); |
| backwardRight.flipDirection(); |
| |
| edge(forwardRight.edge)->setNext(forwardRight.traversal, forwardRight.direction, forwardLeft.edge); |
| edge(forwardLeft.edge)->setNext(forwardLeft.traversal, forwardLeft.direction, forwardRight.edge); |
| |
| edge(backwardRight.edge)->setNext(backwardRight.traversal, backwardRight.direction, backwardLeft.edge); |
| edge(backwardLeft.edge)->setNext(backwardLeft.traversal, backwardLeft.direction, backwardRight.edge); |
| |
| ep->setNext(QPathEdge::Forward, ei); |
| ep->setNext(QPathEdge::Backward, ei); |
| |
| QPathVertex *a = vertex(ep->first); |
| QPathVertex *b = vertex(ep->second); |
| |
| a->edge = backwardRight.edge; |
| b->edge = forwardRight.edge; |
| } |
| |
| static int commonEdge(const QWingedEdge &list, int a, int b) |
| { |
| const QPathVertex *ap = list.vertex(a); |
| Q_ASSERT(ap); |
| |
| const QPathVertex *bp = list.vertex(b); |
| Q_ASSERT(bp); |
| |
| if (ap->edge < 0 || bp->edge < 0) |
| return -1; |
| |
| QWingedEdge::TraversalStatus status; |
| status.edge = ap->edge; |
| status.direction = list.edge(status.edge)->directionTo(a); |
| status.traversal = QPathEdge::RightTraversal; |
| |
| do { |
| const QPathEdge *ep = list.edge(status.edge); |
| |
| if ((ep->first == a && ep->second == b) |
| || (ep->first == b && ep->second == a)) |
| return status.edge; |
| |
| status = list.next(status); |
| status.flip(); |
| } while (status.edge != ap->edge); |
| |
| return -1; |
| } |
| |
| static double computeAngle(const QPointF &v) |
| { |
| #if 1 |
| if (v.x() == 0) { |
| return v.y() <= 0 ? 0 : 64.; |
| } else if (v.y() == 0) { |
| return v.x() <= 0 ? 32. : 96.; |
| } |
| |
| double vx = v.x(); |
| double vy = v.y(); |
| normalize(vx, vy); |
| if (vy < 0) { |
| if (vx < 0) { // 0 - 32 |
| return -32. * vx; |
| } else { // 96 - 128 |
| return 128. - 32. * vx; |
| } |
| } else { // 32 - 96 |
| return 64. + 32. * vx; |
| } |
| #else |
| // doesn't seem to be robust enough |
| return qAtan2(v.x(), v.y()) + Q_PI; |
| #endif |
| } |
| |
| int QWingedEdge::addEdge(const QPointF &a, const QPointF &b) |
| { |
| int fi = insert(a); |
| int si = insert(b); |
| |
| return addEdge(fi, si); |
| } |
| |
| int QWingedEdge::addEdge(int fi, int si) |
| { |
| if (fi == si) |
| return -1; |
| |
| int common = commonEdge(*this, fi, si); |
| if (common >= 0) |
| return common; |
| |
| m_edges << QPathEdge(fi, si); |
| |
| int ei = m_edges.size() - 1; |
| |
| QPathVertex *fp = vertex(fi); |
| QPathVertex *sp = vertex(si); |
| |
| QPathEdge *ep = edge(ei); |
| |
| const QPointF tangent = QPointF(*sp) - QPointF(*fp); |
| ep->angle = computeAngle(tangent); |
| ep->invAngle = ep->angle + 64; |
| if (ep->invAngle >= 128) |
| ep->invAngle -= 128; |
| |
| QPathVertex *vertices[2] = { fp, sp }; |
| QPathEdge::Direction dirs[2] = { QPathEdge::Backward, QPathEdge::Forward }; |
| |
| #ifdef QDEBUG_CLIPPER |
| printf("** Adding edge %d / vertices: %.07f %.07f, %.07f %.07f\n", ei, fp->x, fp->y, sp->x, sp->y); |
| #endif |
| |
| for (int i = 0; i < 2; ++i) { |
| QPathVertex *vp = vertices[i]; |
| if (vp->edge < 0) { |
| vp->edge = ei; |
| ep->setNext(dirs[i], ei); |
| } else { |
| int vi = ep->vertex(dirs[i]); |
| Q_ASSERT(vertex(vi) == vertices[i]); |
| |
| TraversalStatus os = findInsertStatus(vi, ei); |
| QPathEdge *op = edge(os.edge); |
| |
| Q_ASSERT(vertex(op->vertex(os.direction)) == vertices[i]); |
| |
| TraversalStatus ns = next(os); |
| ns.flipDirection(); |
| QPathEdge *np = edge(ns.edge); |
| |
| op->setNext(os.traversal, os.direction, ei); |
| np->setNext(ns.traversal, ns.direction, ei); |
| |
| int oe = os.edge; |
| int ne = ns.edge; |
| |
| os = next(os); |
| ns = next(ns); |
| |
| os.flipDirection(); |
| ns.flipDirection(); |
| |
| Q_ASSERT(os.edge == ei); |
| Q_ASSERT(ns.edge == ei); |
| |
| ep->setNext(os.traversal, os.direction, oe); |
| ep->setNext(ns.traversal, ns.direction, ne); |
| } |
| } |
| |
| Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Forward) >= 0); |
| Q_ASSERT(ep->next(QPathEdge::RightTraversal, QPathEdge::Backward) >= 0); |
| Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Forward) >= 0); |
| Q_ASSERT(ep->next(QPathEdge::LeftTraversal, QPathEdge::Backward) >= 0); |
| |
| return ei; |
| } |
| |
| int QWingedEdge::insert(const QPathVertex &vertex) |
| { |
| if (!m_vertices.isEmpty()) { |
| const QPathVertex &last = m_vertices.last(); |
| if (vertex.x == last.x && vertex.y == last.y) |
| return m_vertices.size() - 1; |
| |
| for (int i = 0; i < m_vertices.size(); ++i) { |
| const QPathVertex &v = m_vertices.at(i); |
| if (qFuzzyCompare(v.x, vertex.x) && qFuzzyCompare(v.y, vertex.y)) { |
| return i; |
| } |
| } |
| } |
| |
| m_vertices << vertex; |
| return m_vertices.size() - 1; |
| } |
| |
| static void addLineTo(QPainterPath &path, const QPointF &point) |
| { |
| const int elementCount = path.elementCount(); |
| if (elementCount >= 2) { |
| const QPainterPath::Element &middle = path.elementAt(elementCount - 1); |
| if (middle.type == QPainterPath::LineToElement) { |
| const QPointF first = path.elementAt(elementCount - 2); |
| const QPointF d1 = point - first; |
| const QPointF d2 = middle - first; |
| |
| const QPointF p(-d1.y(), d1.x()); |
| |
| if (qFuzzyIsNull(dot(p, d2))) { |
| path.setElementPositionAt(elementCount - 1, point.x(), point.y()); |
| return; |
| } |
| } |
| } |
| |
| path.lineTo(point); |
| } |
| |
| static void add(QPainterPath &path, const QWingedEdge &list, int edge, QPathEdge::Traversal traversal) |
| { |
| QWingedEdge::TraversalStatus status; |
| status.edge = edge; |
| status.traversal = traversal; |
| status.direction = QPathEdge::Forward; |
| |
| path.moveTo(*list.vertex(list.edge(edge)->first)); |
| |
| do { |
| const QPathEdge *ep = list.edge(status.edge); |
| |
| addLineTo(path, *list.vertex(ep->vertex(status.direction))); |
| |
| if (status.traversal == QPathEdge::LeftTraversal) |
| ep->flag &= ~16; |
| else |
| ep->flag &= ~32; |
| |
| status = list.next(status); |
| } while (status.edge != edge); |
| } |
| |
| void QWingedEdge::simplify() |
| { |
| for (int i = 0; i < edgeCount(); ++i) { |
| const QPathEdge *ep = edge(i); |
| |
| // if both sides are part of the inside then we can collapse the edge |
| int flag = 0x3 << 4; |
| if ((ep->flag & flag) == flag) { |
| removeEdge(i); |
| |
| ep->flag &= ~flag; |
| } |
| } |
| } |
| |
| QPainterPath QWingedEdge::toPath() const |
| { |
| QPainterPath path; |
| |
| for (int i = 0; i < edgeCount(); ++i) { |
| const QPathEdge *ep = edge(i); |
| |
| if (ep->flag & 16) { |
| add(path, *this, i, QPathEdge::LeftTraversal); |
| } |
| |
| if (ep->flag & 32) |
| add(path, *this, i, QPathEdge::RightTraversal); |
| } |
| |
| return path; |
| } |
| |
| bool QPathClipper::intersect() |
| { |
| if (subjectPath == clipPath) |
| return true; |
| |
| QRectF r1 = subjectPath.controlPointRect(); |
| QRectF r2 = clipPath.controlPointRect(); |
| if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) || |
| qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) { |
| // no way we could intersect |
| return false; |
| } |
| |
| bool subjectIsRect = pathToRect(subjectPath); |
| bool clipIsRect = pathToRect(clipPath); |
| |
| if (subjectIsRect && clipIsRect) |
| return true; |
| else if (subjectIsRect) |
| return clipPath.intersects(r1); |
| else if (clipIsRect) |
| return subjectPath.intersects(r2); |
| |
| QPathSegments a(subjectPath.elementCount()); |
| a.setPath(subjectPath); |
| QPathSegments b(clipPath.elementCount()); |
| b.setPath(clipPath); |
| |
| QIntersectionFinder finder; |
| if (finder.hasIntersections(a, b)) |
| return true; |
| |
| for (int i = 0; i < clipPath.elementCount(); ++i) { |
| if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) { |
| const QPointF point = clipPath.elementAt(i); |
| if (r1.contains(point) && subjectPath.contains(point)) |
| return true; |
| } |
| } |
| |
| for (int i = 0; i < subjectPath.elementCount(); ++i) { |
| if (subjectPath.elementAt(i).type == QPainterPath::MoveToElement) { |
| const QPointF point = subjectPath.elementAt(i); |
| if (r2.contains(point) && clipPath.contains(point)) |
| return true; |
| } |
| } |
| |
| return false; |
| } |
| |
| bool QPathClipper::contains() |
| { |
| if (subjectPath == clipPath) |
| return false; |
| |
| QRectF r1 = subjectPath.controlPointRect(); |
| QRectF r2 = clipPath.controlPointRect(); |
| if (qMax(r1.x(), r2.x()) > qMin(r1.x() + r1.width(), r2.x() + r2.width()) || |
| qMax(r1.y(), r2.y()) > qMin(r1.y() + r1.height(), r2.y() + r2.height())) { |
| // no intersection -> not contained |
| return false; |
| } |
| |
| bool clipIsRect = pathToRect(clipPath); |
| if (clipIsRect) |
| return subjectPath.contains(r2); |
| |
| QPathSegments a(subjectPath.elementCount()); |
| a.setPath(subjectPath); |
| QPathSegments b(clipPath.elementCount()); |
| b.setPath(clipPath); |
| |
| QIntersectionFinder finder; |
| if (finder.hasIntersections(a, b)) |
| return false; |
| |
| for (int i = 0; i < clipPath.elementCount(); ++i) { |
| if (clipPath.elementAt(i).type == QPainterPath::MoveToElement) { |
| const QPointF point = clipPath.elementAt(i); |
| if (!r1.contains(point) || !subjectPath.contains(point)) |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| QPathClipper::QPathClipper(const QPainterPath &subject, |
| const QPainterPath &clip) |
| : subjectPath(subject) |
| , clipPath(clip) |
| { |
| aMask = subjectPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1; |
| bMask = clipPath.fillRule() == Qt::WindingFill ? ~0x0 : 0x1; |
| } |
| |
| static void clear(QWingedEdge& list, int edge, QPathEdge::Traversal traversal) |
| { |
| QWingedEdge::TraversalStatus status; |
| status.edge = edge; |
| status.traversal = traversal; |
| status.direction = QPathEdge::Forward; |
| |
| do { |
| if (status.traversal == QPathEdge::LeftTraversal) |
| list.edge(status.edge)->flag |= 1; |
| else |
| list.edge(status.edge)->flag |= 2; |
| |
| status = list.next(status); |
| } while (status.edge != edge); |
| } |
| |
| template <typename InputIterator> |
| InputIterator qFuzzyFind(InputIterator first, InputIterator last, qreal val) |
| { |
| while (first != last && !QT_PREPEND_NAMESPACE(qFuzzyCompare)(qreal(*first), qreal(val))) |
| ++first; |
| return first; |
| } |
| |
| static bool fuzzyCompare(qreal a, qreal b) |
| { |
| return qFuzzyCompare(a, b); |
| } |
| |
| bool QPathClipper::pathToRect(const QPainterPath &path, QRectF *rect) |
| { |
| if (path.elementCount() != 5) |
| return false; |
| |
| const bool mightBeRect = path.elementAt(0).isMoveTo() |
| && path.elementAt(1).isLineTo() |
| && path.elementAt(2).isLineTo() |
| && path.elementAt(3).isLineTo() |
| && path.elementAt(4).isLineTo(); |
| |
| if (!mightBeRect) |
| return false; |
| |
| const qreal x1 = path.elementAt(0).x; |
| const qreal y1 = path.elementAt(0).y; |
| |
| const qreal x2 = path.elementAt(1).x; |
| const qreal y2 = path.elementAt(2).y; |
| |
| if (path.elementAt(1).y != y1) |
| return false; |
| |
| if (path.elementAt(2).x != x2) |
| return false; |
| |
| if (path.elementAt(3).x != x1 || path.elementAt(3).y != y2) |
| return false; |
| |
| if (path.elementAt(4).x != x1 || path.elementAt(4).y != y1) |
| return false; |
| |
| if (rect) |
| rect->setCoords(x1, y1, x2, y2); |
| |
| return true; |
| } |
| |
| |
| QPainterPath QPathClipper::clip(Operation operation) |
| { |
| op = operation; |
| |
| if (op != Simplify) { |
| if (subjectPath == clipPath) |
| return op == BoolSub ? QPainterPath() : subjectPath; |
| |
| bool subjectIsRect = pathToRect(subjectPath, nullptr); |
| bool clipIsRect = pathToRect(clipPath, nullptr); |
| |
| const QRectF clipBounds = clipPath.boundingRect(); |
| const QRectF subjectBounds = subjectPath.boundingRect(); |
| |
| if (!clipBounds.intersects(subjectBounds)) { |
| switch (op) { |
| case BoolSub: |
| return subjectPath; |
| case BoolAnd: |
| return QPainterPath(); |
| case BoolOr: { |
| QPainterPath result = subjectPath; |
| if (result.fillRule() == clipPath.fillRule()) { |
| result.addPath(clipPath); |
| } else if (result.fillRule() == Qt::WindingFill) { |
| result = result.simplified(); |
| result.addPath(clipPath); |
| } else { |
| result.addPath(clipPath.simplified()); |
| } |
| return result; |
| } |
| default: |
| break; |
| } |
| } |
| |
| if (clipBounds.contains(subjectBounds)) { |
| if (clipIsRect) { |
| switch (op) { |
| case BoolSub: |
| return QPainterPath(); |
| case BoolAnd: |
| return subjectPath; |
| case BoolOr: |
| return clipPath; |
| default: |
| break; |
| } |
| } |
| } else if (subjectBounds.contains(clipBounds)) { |
| if (subjectIsRect) { |
| switch (op) { |
| case BoolSub: |
| if (clipPath.fillRule() == Qt::OddEvenFill) { |
| QPainterPath result = clipPath; |
| result.addRect(subjectBounds); |
| return result; |
| } else { |
| QPainterPath result = clipPath.simplified(); |
| result.addRect(subjectBounds); |
| return result; |
| } |
| case BoolAnd: |
| return clipPath; |
| case BoolOr: |
| return subjectPath; |
| default: |
| break; |
| } |
| } |
| } |
| |
| if (op == BoolAnd) { |
| if (subjectIsRect) |
| return intersect(clipPath, subjectBounds); |
| else if (clipIsRect) |
| return intersect(subjectPath, clipBounds); |
| } |
| } |
| |
| QWingedEdge list(subjectPath, clipPath); |
| |
| doClip(list, ClipMode); |
| |
| QPainterPath path = list.toPath(); |
| return path; |
| } |
| |
| bool QPathClipper::doClip(QWingedEdge &list, ClipperMode mode) |
| { |
| QVector<qreal> y_coords; |
| y_coords.reserve(list.vertexCount()); |
| for (int i = 0; i < list.vertexCount(); ++i) |
| y_coords << list.vertex(i)->y; |
| |
| std::sort(y_coords.begin(), y_coords.end()); |
| y_coords.erase(std::unique(y_coords.begin(), y_coords.end(), fuzzyCompare), y_coords.end()); |
| |
| #ifdef QDEBUG_CLIPPER |
| printf("sorted y coords:\n"); |
| for (int i = 0; i < y_coords.size(); ++i) { |
| printf("%.9f\n", y_coords.at(i)); |
| } |
| #endif |
| |
| bool found; |
| do { |
| found = false; |
| int index = 0; |
| qreal maxHeight = 0; |
| for (int i = 0; i < list.edgeCount(); ++i) { |
| QPathEdge *edge = list.edge(i); |
| |
| // have both sides of this edge already been handled? |
| if ((edge->flag & 0x3) == 0x3) |
| continue; |
| |
| QPathVertex *a = list.vertex(edge->first); |
| QPathVertex *b = list.vertex(edge->second); |
| |
| if (qFuzzyCompare(a->y, b->y)) |
| continue; |
| |
| found = true; |
| |
| qreal height = qAbs(a->y - b->y); |
| if (height > maxHeight) { |
| index = i; |
| maxHeight = height; |
| } |
| } |
| |
| if (found) { |
| QPathEdge *edge = list.edge(index); |
| |
| QPathVertex *a = list.vertex(edge->first); |
| QPathVertex *b = list.vertex(edge->second); |
| |
| // FIXME: this can be optimized by using binary search |
| const int first = qFuzzyFind(y_coords.cbegin(), y_coords.cend(), qMin(a->y, b->y)) - y_coords.cbegin(); |
| const int last = qFuzzyFind(y_coords.cbegin() + first, y_coords.cend(), qMax(a->y, b->y)) - y_coords.cbegin(); |
| |
| Q_ASSERT(first < y_coords.size() - 1); |
| Q_ASSERT(last < y_coords.size()); |
| |
| qreal biggestGap = y_coords.at(first + 1) - y_coords.at(first); |
| int bestIdx = first; |
| for (int i = first + 1; i < last; ++i) { |
| qreal gap = y_coords.at(i + 1) - y_coords.at(i); |
| |
| if (gap > biggestGap) { |
| bestIdx = i; |
| biggestGap = gap; |
| } |
| } |
| const qreal bestY = 0.5 * (y_coords.at(bestIdx) + y_coords.at(bestIdx + 1)); |
| |
| #ifdef QDEBUG_CLIPPER |
| printf("y: %.9f, gap: %.9f\n", bestY, biggestGap); |
| #endif |
| |
| if (handleCrossingEdges(list, bestY, mode) && mode == CheckMode) |
| return true; |
| |
| edge->flag |= 0x3; |
| } |
| } while (found); |
| |
| if (mode == ClipMode) |
| list.simplify(); |
| |
| return false; |
| } |
| |
| static void traverse(QWingedEdge &list, int edge, QPathEdge::Traversal traversal) |
| { |
| QWingedEdge::TraversalStatus status; |
| status.edge = edge; |
| status.traversal = traversal; |
| status.direction = QPathEdge::Forward; |
| |
| do { |
| int flag = status.traversal == QPathEdge::LeftTraversal ? 1 : 2; |
| |
| QPathEdge *ep = list.edge(status.edge); |
| |
| ep->flag |= (flag | (flag << 4)); |
| |
| #ifdef QDEBUG_CLIPPER |
| qDebug() << "traverse: adding edge " << status.edge << ", mask:" << (flag << 4) <<ep->flag; |
| #endif |
| |
| status = list.next(status); |
| } while (status.edge != edge); |
| } |
| |
| struct QCrossingEdge |
| { |
| int edge; |
| qreal x; |
| |
| bool operator<(const QCrossingEdge &edge) const |
| { |
| return x < edge.x; |
| } |
| }; |
| Q_DECLARE_TYPEINFO(QCrossingEdge, Q_PRIMITIVE_TYPE); |
| |
| static bool bool_op(bool a, bool b, QPathClipper::Operation op) |
| { |
| switch (op) { |
| case QPathClipper::BoolAnd: |
| return a && b; |
| case QPathClipper::BoolOr: |
| case QPathClipper::Simplify: |
| return a || b; |
| case QPathClipper::BoolSub: |
| return a && !b; |
| default: |
| Q_ASSERT(false); |
| return false; |
| } |
| } |
| |
| bool QWingedEdge::isInside(qreal x, qreal y) const |
| { |
| int winding = 0; |
| for (int i = 0; i < edgeCount(); ++i) { |
| const QPathEdge *ep = edge(i); |
| |
| // left xor right |
| int w = ((ep->flag >> 4) ^ (ep->flag >> 5)) & 1; |
| |
| if (!w) |
| continue; |
| |
| QPointF a = *vertex(ep->first); |
| QPointF b = *vertex(ep->second); |
| |
| if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { |
| qreal intersectionX = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); |
| |
| if (intersectionX > x) |
| winding += w; |
| } |
| } |
| |
| return winding & 1; |
| } |
| |
| static QVector<QCrossingEdge> findCrossings(const QWingedEdge &list, qreal y) |
| { |
| QVector<QCrossingEdge> crossings; |
| for (int i = 0; i < list.edgeCount(); ++i) { |
| const QPathEdge *edge = list.edge(i); |
| QPointF a = *list.vertex(edge->first); |
| QPointF b = *list.vertex(edge->second); |
| |
| if ((a.y() < y && b.y() > y) || (a.y() > y && b.y() < y)) { |
| const qreal intersection = a.x() + (b.x() - a.x()) * (y - a.y()) / (b.y() - a.y()); |
| const QCrossingEdge edge = { i, intersection }; |
| crossings << edge; |
| } |
| } |
| return crossings; |
| } |
| |
| bool QPathClipper::handleCrossingEdges(QWingedEdge &list, qreal y, ClipperMode mode) |
| { |
| QVector<QCrossingEdge> crossings = findCrossings(list, y); |
| |
| Q_ASSERT(!crossings.isEmpty()); |
| std::sort(crossings.begin(), crossings.end()); |
| |
| int windingA = 0; |
| int windingB = 0; |
| |
| int windingD = 0; |
| |
| #ifdef QDEBUG_CLIPPER |
| qDebug() << "crossings:" << crossings.size(); |
| #endif |
| for (int i = 0; i < crossings.size() - 1; ++i) { |
| int ei = crossings.at(i).edge; |
| const QPathEdge *edge = list.edge(ei); |
| |
| windingA += edge->windingA; |
| windingB += edge->windingB; |
| |
| const bool hasLeft = (edge->flag >> 4) & 1; |
| const bool hasRight = (edge->flag >> 4) & 2; |
| |
| windingD += hasLeft ^ hasRight; |
| |
| const bool inA = (windingA & aMask) != 0; |
| const bool inB = (windingB & bMask) != 0; |
| const bool inD = (windingD & 0x1) != 0; |
| |
| const bool inside = bool_op(inA, inB, op); |
| const bool add = inD ^ inside; |
| |
| #ifdef QDEBUG_CLIPPER |
| 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); |
| #endif |
| |
| if (add) { |
| if (mode == CheckMode) |
| return true; |
| |
| qreal y0 = list.vertex(edge->first)->y; |
| qreal y1 = list.vertex(edge->second)->y; |
| |
| if (y0 < y1) { |
| if (!(edge->flag & 1)) |
| traverse(list, ei, QPathEdge::LeftTraversal); |
| |
| if (!(edge->flag & 2)) |
| clear(list, ei, QPathEdge::RightTraversal); |
| } else { |
| if (!(edge->flag & 1)) |
| clear(list, ei, QPathEdge::LeftTraversal); |
| |
| if (!(edge->flag & 2)) |
| traverse(list, ei, QPathEdge::RightTraversal); |
| } |
| |
| ++windingD; |
| } else { |
| if (!(edge->flag & 1)) |
| clear(list, ei, QPathEdge::LeftTraversal); |
| |
| if (!(edge->flag & 2)) |
| clear(list, ei, QPathEdge::RightTraversal); |
| } |
| } |
| |
| return false; |
| } |
| |
| namespace { |
| |
| QVector<QPainterPath> toSubpaths(const QPainterPath &path) |
| { |
| |
| QVector<QPainterPath> subpaths; |
| if (path.isEmpty()) |
| return subpaths; |
| |
| QPainterPath current; |
| for (int i = 0; i < path.elementCount(); ++i) { |
| const QPainterPath::Element &e = path.elementAt(i); |
| switch (e.type) { |
| case QPainterPath::MoveToElement: |
| if (current.elementCount() > 1) |
| subpaths += current; |
| current = QPainterPath(); |
| current.moveTo(e); |
| break; |
| case QPainterPath::LineToElement: |
| current.lineTo(e); |
| break; |
| case QPainterPath::CurveToElement: { |
| current.cubicTo(e, path.elementAt(i + 1), path.elementAt(i + 2)); |
| i+=2; |
| break; |
| } |
| case QPainterPath::CurveToDataElement: |
| Q_ASSERT(!"toSubpaths(), bad element type"); |
| break; |
| } |
| } |
| |
| if (current.elementCount() > 1) |
| subpaths << current; |
| |
| return subpaths; |
| } |
| |
| enum Edge |
| { |
| Left, Top, Right, Bottom |
| }; |
| |
| static bool isVertical(Edge edge) |
| { |
| return edge == Left || edge == Right; |
| } |
| |
| template <Edge edge> |
| bool compare(const QPointF &p, qreal t) |
| { |
| switch (edge) |
| { |
| case Left: |
| return p.x() < t; |
| case Right: |
| return p.x() > t; |
| case Top: |
| return p.y() < t; |
| default: |
| return p.y() > t; |
| } |
| } |
| |
| template <Edge edge> |
| QPointF intersectLine(const QPointF &a, const QPointF &b, qreal t) |
| { |
| QLineF line(a, b); |
| switch (edge) { |
| case Left: |
| case Right: |
| return line.pointAt((t - a.x()) / (b.x() - a.x())); |
| default: |
| return line.pointAt((t - a.y()) / (b.y() - a.y())); |
| } |
| } |
| |
| void addLine(QPainterPath &path, const QLineF &line) |
| { |
| if (path.elementCount() > 0) |
| path.lineTo(line.p1()); |
| else |
| path.moveTo(line.p1()); |
| |
| path.lineTo(line.p2()); |
| } |
| |
| template <Edge edge> |
| void clipLine(const QPointF &a, const QPointF &b, qreal t, QPainterPath &result) |
| { |
| bool outA = compare<edge>(a, t); |
| bool outB = compare<edge>(b, t); |
| if (outA && outB) |
| return; |
| |
| if (outA) |
| addLine(result, QLineF(intersectLine<edge>(a, b, t), b)); |
| else if(outB) |
| addLine(result, QLineF(a, intersectLine<edge>(a, b, t))); |
| else |
| addLine(result, QLineF(a, b)); |
| } |
| |
| void addBezier(QPainterPath &path, const QBezier &bezier) |
| { |
| if (path.elementCount() > 0) |
| path.lineTo(bezier.pt1()); |
| else |
| path.moveTo(bezier.pt1()); |
| |
| path.cubicTo(bezier.pt2(), bezier.pt3(), bezier.pt4()); |
| } |
| |
| template <Edge edge> |
| void clipBezier(const QPointF &a, const QPointF &b, const QPointF &c, const QPointF &d, qreal t, QPainterPath &result) |
| { |
| QBezier bezier = QBezier::fromPoints(a, b, c, d); |
| |
| bool outA = compare<edge>(a, t); |
| bool outB = compare<edge>(b, t); |
| bool outC = compare<edge>(c, t); |
| bool outD = compare<edge>(d, t); |
| |
| int outCount = int(outA) + int(outB) + int(outC) + int(outD); |
| |
| if (outCount == 4) |
| return; |
| |
| if (outCount == 0) { |
| addBezier(result, bezier); |
| return; |
| } |
| |
| QTransform flip = isVertical(edge) ? QTransform(0, 1, 1, 0, 0, 0) : QTransform(); |
| QBezier unflipped = bezier; |
| QBezier flipped = bezier.mapBy(flip); |
| |
| qreal t0 = 0, t1 = 1; |
| int stationary = flipped.stationaryYPoints(t0, t1); |
| |
| qreal segments[4]; |
| QPointF points[4]; |
| points[0] = unflipped.pt1(); |
| segments[0] = 0; |
| |
| int segmentCount = 0; |
| if (stationary > 0) { |
| ++segmentCount; |
| segments[segmentCount] = t0; |
| points[segmentCount] = unflipped.pointAt(t0); |
| } |
| if (stationary > 1) { |
| ++segmentCount; |
| segments[segmentCount] = t1; |
| points[segmentCount] = unflipped.pointAt(t1); |
| } |
| ++segmentCount; |
| segments[segmentCount] = 1; |
| points[segmentCount] = unflipped.pt4(); |
| |
| qreal lastIntersection = 0; |
| for (int i = 0; i < segmentCount; ++i) { |
| outA = compare<edge>(points[i], t); |
| outB = compare<edge>(points[i+1], t); |
| |
| if (outA != outB) { |
| qreal intersection = flipped.tForY(segments[i], segments[i+1], t); |
| |
| if (outB) |
| addBezier(result, unflipped.getSubRange(lastIntersection, intersection)); |
| |
| lastIntersection = intersection; |
| } |
| } |
| |
| if (!outB) |
| addBezier(result, unflipped.getSubRange(lastIntersection, 1)); |
| } |
| |
| // clips a single subpath against a single edge |
| template <Edge edge> |
| QPainterPath clip(const QPainterPath &path, qreal t) |
| { |
| QPainterPath result; |
| for (int i = 1; i < path.elementCount(); ++i) { |
| const QPainterPath::Element &element = path.elementAt(i); |
| Q_ASSERT(!element.isMoveTo()); |
| if (element.isLineTo()) { |
| clipLine<edge>(path.elementAt(i-1), path.elementAt(i), t, result); |
| } else { |
| clipBezier<edge>(path.elementAt(i-1), path.elementAt(i), path.elementAt(i+1), path.elementAt(i+2), t, result); |
| i += 2; |
| } |
| } |
| |
| int last = path.elementCount() - 1; |
| if (QPointF(path.elementAt(last)) != QPointF(path.elementAt(0))) |
| clipLine<edge>(path.elementAt(last), path.elementAt(0), t, result); |
| |
| return result; |
| } |
| |
| QPainterPath intersectPath(const QPainterPath &path, const QRectF &rect) |
| { |
| QVector<QPainterPath> subpaths = toSubpaths(path); |
| |
| QPainterPath result; |
| result.setFillRule(path.fillRule()); |
| for (int i = 0; i < subpaths.size(); ++i) { |
| QPainterPath subPath = subpaths.at(i); |
| QRectF bounds = subPath.boundingRect(); |
| if (bounds.intersects(rect)) { |
| if (bounds.left() < rect.left()) |
| subPath = clip<Left>(subPath, rect.left()); |
| if (bounds.right() > rect.right()) |
| subPath = clip<Right>(subPath, rect.right()); |
| |
| bounds = subPath.boundingRect(); |
| |
| if (bounds.top() < rect.top()) |
| subPath = clip<Top>(subPath, rect.top()); |
| if (bounds.bottom() > rect.bottom()) |
| subPath = clip<Bottom>(subPath, rect.bottom()); |
| |
| if (subPath.elementCount() > 1) |
| result.addPath(subPath); |
| } |
| } |
| // The algorithm above might return one side of \a rect if there was no intersection, |
| // so only return intersections that are not empty rectangles. |
| if (result.boundingRect().isEmpty()) |
| return QPainterPath(); |
| else |
| return result; |
| } |
| |
| } |
| |
| QPainterPath QPathClipper::intersect(const QPainterPath &path, const QRectF &rect) |
| { |
| return intersectPath(path, rect); |
| } |
| |
| QT_END_NAMESPACE |