1/*
2 * Copyright (C) 2006 Zack Rusin   <zack@kde.org>
3 *               2006 Rob Buis     <buis@kde.org>
4 *               2009, 2010 Dirk Schulze <krit@webkit.org>
5 *
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 *    notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
20 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
25 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#include "config.h"
31#include "Path.h"
32
33#include "AffineTransform.h"
34#include "FloatRect.h"
35#include "GraphicsContext.h"
36#include "ImageBuffer.h"
37#include "PlatformString.h"
38#include "StrokeStyleApplier.h"
39#include <QPainterPath>
40#include <QTransform>
41#include <QString>
42#include <wtf/MathExtras.h>
43#include <wtf/OwnPtr.h>
44
45namespace WebCore {
46
47Path::Path()
48{
49}
50
51Path::~Path()
52{
53}
54
55Path::Path(const Path& other)
56    : m_path(other.m_path)
57{
58}
59
60Path& Path::operator=(const Path& other)
61{
62    m_path = other.m_path;
63    return *this;
64}
65
66static inline bool areCollinear(const QPointF& a, const QPointF& b, const QPointF& c)
67{
68    // Solved from comparing the slopes of a to b and b to c: (ay-by)/(ax-bx) == (cy-by)/(cx-bx)
69    return qFuzzyCompare((c.y() - b.y()) * (a.x() - b.x()), (a.y() - b.y()) * (c.x() - b.x()));
70}
71
72static inline bool withinRange(qreal p, qreal a, qreal b)
73{
74    return (p >= a && p <= b) || (p >= b && p <= a);
75}
76
77// Check whether a point is on the border
78static bool isPointOnPathBorder(const QPolygonF& border, const QPointF& p)
79{
80    // null border doesn't contain points
81    if (border.isEmpty())
82        return false;
83
84    QPointF p1 = border.at(0);
85    QPointF p2;
86
87    for (int i = 1; i < border.size(); ++i) {
88        p2 = border.at(i);
89        if (areCollinear(p, p1, p2)
90                // Once we know that the points are collinear we
91                // only need to check one of the coordinates
92                && (qAbs(p2.x() - p1.x()) > qAbs(p2.y() - p1.y()) ?
93                        withinRange(p.x(), p1.x(), p2.x()) :
94                        withinRange(p.y(), p1.y(), p2.y()))) {
95            return true;
96        }
97        p1 = p2;
98    }
99    return false;
100}
101
102bool Path::contains(const FloatPoint& point, WindRule rule) const
103{
104    Qt::FillRule savedRule = m_path.fillRule();
105    const_cast<QPainterPath*>(&m_path)->setFillRule(rule == RULE_EVENODD ? Qt::OddEvenFill : Qt::WindingFill);
106
107    bool contains = m_path.contains(point);
108
109    if (!contains) {
110        // check whether the point is on the border
111        contains = isPointOnPathBorder(m_path.toFillPolygon(), point);
112    }
113
114    const_cast<QPainterPath*>(&m_path)->setFillRule(savedRule);
115    return contains;
116}
117
118static GraphicsContext* scratchContext()
119{
120    static QImage image(1, 1, QImage::Format_ARGB32_Premultiplied);
121    static QPainter painter(&image);
122    static GraphicsContext* context = new GraphicsContext(&painter);
123    return context;
124}
125
126bool Path::strokeContains(StrokeStyleApplier* applier, const FloatPoint& point) const
127{
128    ASSERT(applier);
129
130    QPainterPathStroker stroke;
131    GraphicsContext* context = scratchContext();
132    applier->strokeStyle(context);
133
134    QPen pen = context->platformContext()->pen();
135    stroke.setWidth(pen.widthF());
136    stroke.setCapStyle(pen.capStyle());
137    stroke.setJoinStyle(pen.joinStyle());
138    stroke.setMiterLimit(pen.miterLimit());
139    stroke.setDashPattern(pen.dashPattern());
140    stroke.setDashOffset(pen.dashOffset());
141
142    return stroke.createStroke(m_path).contains(point);
143}
144
145void Path::translate(const FloatSize& size)
146{
147    QTransform matrix;
148    matrix.translate(size.width(), size.height());
149    m_path = m_path * matrix;
150}
151
152FloatRect Path::boundingRect() const
153{
154    return m_path.boundingRect();
155}
156
157FloatRect Path::strokeBoundingRect(StrokeStyleApplier* applier) const
158{
159    GraphicsContext* context = scratchContext();
160    QPainterPathStroker stroke;
161    if (applier) {
162        applier->strokeStyle(context);
163
164        QPen pen = context->platformContext()->pen();
165        stroke.setWidth(pen.widthF());
166        stroke.setCapStyle(pen.capStyle());
167        stroke.setJoinStyle(pen.joinStyle());
168        stroke.setMiterLimit(pen.miterLimit());
169        stroke.setDashPattern(pen.dashPattern());
170        stroke.setDashOffset(pen.dashOffset());
171    }
172    return stroke.createStroke(m_path).boundingRect();
173}
174
175void Path::moveTo(const FloatPoint& point)
176{
177    m_path.moveTo(point);
178}
179
180void Path::addLineTo(const FloatPoint& p)
181{
182    m_path.lineTo(p);
183}
184
185void Path::addQuadCurveTo(const FloatPoint& cp, const FloatPoint& p)
186{
187    m_path.quadTo(cp, p);
188}
189
190void Path::addBezierCurveTo(const FloatPoint& cp1, const FloatPoint& cp2, const FloatPoint& p)
191{
192    m_path.cubicTo(cp1, cp2, p);
193}
194
195void Path::addArcTo(const FloatPoint& p1, const FloatPoint& p2, float radius)
196{
197    FloatPoint p0(m_path.currentPosition());
198
199    FloatPoint p1p0((p0.x() - p1.x()), (p0.y() - p1.y()));
200    FloatPoint p1p2((p2.x() - p1.x()), (p2.y() - p1.y()));
201    float p1p0_length = sqrtf(p1p0.x() * p1p0.x() + p1p0.y() * p1p0.y());
202    float p1p2_length = sqrtf(p1p2.x() * p1p2.x() + p1p2.y() * p1p2.y());
203
204    double cos_phi = (p1p0.x() * p1p2.x() + p1p0.y() * p1p2.y()) / (p1p0_length * p1p2_length);
205
206    // The points p0, p1, and p2 are on the same straight line (HTML5, 4.8.11.1.8)
207    // We could have used areCollinear() here, but since we're reusing
208    // the variables computed above later on we keep this logic.
209    if (qFuzzyCompare(qAbs(cos_phi), 1.0)) {
210        m_path.lineTo(p1);
211        return;
212    }
213
214    float tangent = radius / tan(acos(cos_phi) / 2);
215    float factor_p1p0 = tangent / p1p0_length;
216    FloatPoint t_p1p0((p1.x() + factor_p1p0 * p1p0.x()), (p1.y() + factor_p1p0 * p1p0.y()));
217
218    FloatPoint orth_p1p0(p1p0.y(), -p1p0.x());
219    float orth_p1p0_length = sqrt(orth_p1p0.x() * orth_p1p0.x() + orth_p1p0.y() * orth_p1p0.y());
220    float factor_ra = radius / orth_p1p0_length;
221
222    // angle between orth_p1p0 and p1p2 to get the right vector orthographic to p1p0
223    double cos_alpha = (orth_p1p0.x() * p1p2.x() + orth_p1p0.y() * p1p2.y()) / (orth_p1p0_length * p1p2_length);
224    if (cos_alpha < 0.f)
225        orth_p1p0 = FloatPoint(-orth_p1p0.x(), -orth_p1p0.y());
226
227    FloatPoint p((t_p1p0.x() + factor_ra * orth_p1p0.x()), (t_p1p0.y() + factor_ra * orth_p1p0.y()));
228
229    // calculate angles for addArc
230    orth_p1p0 = FloatPoint(-orth_p1p0.x(), -orth_p1p0.y());
231    float sa = acos(orth_p1p0.x() / orth_p1p0_length);
232    if (orth_p1p0.y() < 0.f)
233        sa = 2 * piDouble - sa;
234
235    // anticlockwise logic
236    bool anticlockwise = false;
237
238    float factor_p1p2 = tangent / p1p2_length;
239    FloatPoint t_p1p2((p1.x() + factor_p1p2 * p1p2.x()), (p1.y() + factor_p1p2 * p1p2.y()));
240    FloatPoint orth_p1p2((t_p1p2.x() - p.x()), (t_p1p2.y() - p.y()));
241    float orth_p1p2_length = sqrtf(orth_p1p2.x() * orth_p1p2.x() + orth_p1p2.y() * orth_p1p2.y());
242    float ea = acos(orth_p1p2.x() / orth_p1p2_length);
243    if (orth_p1p2.y() < 0)
244        ea = 2 * piDouble - ea;
245    if ((sa > ea) && ((sa - ea) < piDouble))
246        anticlockwise = true;
247    if ((sa < ea) && ((ea - sa) > piDouble))
248        anticlockwise = true;
249
250    m_path.lineTo(t_p1p0);
251
252    addArc(p, radius, sa, ea, anticlockwise);
253}
254
255void Path::closeSubpath()
256{
257    m_path.closeSubpath();
258}
259
260void Path::addArc(const FloatPoint& p, float r, float sar, float ear, bool anticlockwise)
261{
262    qreal xc = p.x();
263    qreal yc = p.y();
264    qreal radius = r;
265
266
267    //### HACK
268    // In Qt we don't switch the coordinate system for degrees
269    // and still use the 0,0 as bottom left for degrees so we need
270    // to switch
271    sar = -sar;
272    ear = -ear;
273    anticlockwise = !anticlockwise;
274    //end hack
275
276    float sa = rad2deg(sar);
277    float ea = rad2deg(ear);
278
279    double span = 0;
280
281    double xs = xc - radius;
282    double ys = yc - radius;
283    double width  = radius*2;
284    double height = radius*2;
285
286    if ((!anticlockwise && (ea - sa >= 360)) || (anticlockwise && (sa - ea >= 360))) {
287        // If the anticlockwise argument is false and endAngle-startAngle is equal to or greater than 2*PI, or, if the
288        // anticlockwise argument is true and startAngle-endAngle is equal to or greater than 2*PI, then the arc is the whole
289        // circumference of this circle.
290        span = 360;
291
292        if (anticlockwise)
293            span = -span;
294    } else {
295        if (!anticlockwise && (ea < sa))
296            span += 360;
297        else if (anticlockwise && (sa < ea))
298            span -= 360;
299
300        // this is also due to switched coordinate system
301        // we would end up with a 0 span instead of 360
302        if (!(qFuzzyCompare(span + (ea - sa) + 1, 1.0)
303            && qFuzzyCompare(qAbs(span), 360.0))) {
304            // mod 360
305            span += (ea - sa) - (static_cast<int>((ea - sa) / 360)) * 360;
306        }
307    }
308
309    // If the path is empty, move to where the arc will start to avoid painting a line from (0,0)
310    // NOTE: QPainterPath::isEmpty() won't work here since it ignores a lone MoveToElement
311    if (!m_path.elementCount())
312        m_path.arcMoveTo(xs, ys, width, height, sa);
313    else if (!radius) {
314        m_path.lineTo(xc, yc);
315        return;
316    }
317
318    m_path.arcTo(xs, ys, width, height, sa, span);
319
320}
321
322void Path::addRect(const FloatRect& r)
323{
324    m_path.addRect(r.x(), r.y(), r.width(), r.height());
325}
326
327void Path::addEllipse(const FloatRect& r)
328{
329    m_path.addEllipse(r.x(), r.y(), r.width(), r.height());
330}
331
332void Path::clear()
333{
334    if (!m_path.elementCount())
335        return;
336    m_path = QPainterPath();
337}
338
339bool Path::isEmpty() const
340{
341    // Don't use QPainterPath::isEmpty(), as that also returns true if there's only
342    // one initial MoveTo element in the path.
343    return !m_path.elementCount();
344}
345
346bool Path::hasCurrentPoint() const
347{
348    return !isEmpty();
349}
350
351FloatPoint Path::currentPoint() const
352{
353    return m_path.currentPosition();
354}
355
356void Path::apply(void* info, PathApplierFunction function) const
357{
358    PathElement pelement;
359    FloatPoint points[3];
360    pelement.points = points;
361    for (int i = 0; i < m_path.elementCount(); ++i) {
362        const QPainterPath::Element& cur = m_path.elementAt(i);
363
364        switch (cur.type) {
365            case QPainterPath::MoveToElement:
366                pelement.type = PathElementMoveToPoint;
367                pelement.points[0] = QPointF(cur);
368                function(info, &pelement);
369                break;
370            case QPainterPath::LineToElement:
371                pelement.type = PathElementAddLineToPoint;
372                pelement.points[0] = QPointF(cur);
373                function(info, &pelement);
374                break;
375            case QPainterPath::CurveToElement:
376            {
377                const QPainterPath::Element& c1 = m_path.elementAt(i + 1);
378                const QPainterPath::Element& c2 = m_path.elementAt(i + 2);
379
380                Q_ASSERT(c1.type == QPainterPath::CurveToDataElement);
381                Q_ASSERT(c2.type == QPainterPath::CurveToDataElement);
382
383                pelement.type = PathElementAddCurveToPoint;
384                pelement.points[0] = QPointF(cur);
385                pelement.points[1] = QPointF(c1);
386                pelement.points[2] = QPointF(c2);
387                function(info, &pelement);
388
389                i += 2;
390                break;
391            }
392            case QPainterPath::CurveToDataElement:
393                Q_ASSERT(false);
394        }
395    }
396}
397
398void Path::transform(const AffineTransform& transform)
399{
400    QTransform qTransform(transform);
401    m_path = qTransform.map(m_path);
402}
403
404float Path::length() const
405{
406    return m_path.length();
407}
408
409FloatPoint Path::pointAtLength(float length, bool& ok) const
410{
411    ok = (length >= 0 && length <= m_path.length());
412
413    qreal percent = m_path.percentAtLength(length);
414    QPointF point = m_path.pointAtPercent(percent);
415
416    return point;
417}
418
419float Path::normalAngleAtLength(float length, bool& ok) const
420{
421    ok = (length >= 0 && length <= m_path.length());
422
423    qreal percent = m_path.percentAtLength(length);
424    qreal angle = m_path.angleAtPercent(percent);
425
426    // Normalize angle value.
427    // QPainterPath returns angle values with the origo being at the top left corner.
428    // In case of moveTo(0, 0) and addLineTo(0, 10) the angle is 270,
429    // while the caller expects it to be 90.
430    // Normalize the value by mirroring it to the x-axis.
431    // For more info look at pathLengthApplierFunction().
432    if (angle > 0)
433        angle = 360 - angle;
434    return angle;
435}
436
437}
438
439// vim: ts=4 sw=4 et
440