1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "SkPathOpsCubic.h"
8#include "SkPathOpsLine.h"
9#include "SkPathOpsQuad.h"
10
11// Sources
12// computer-aided design - volume 22 number 9 november 1990 pp 538 - 549
13// online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
14
15// This turns a line segment into a parameterized line, of the form
16// ax + by + c = 0
17// When a^2 + b^2 == 1, the line is normalized.
18// The distance to the line for (x, y) is d(x,y) = ax + by + c
19//
20// Note that the distances below are not necessarily normalized. To get the true
21// distance, it's necessary to either call normalize() after xxxEndPoints(), or
22// divide the result of xxxDistance() by sqrt(normalSquared())
23
24class SkLineParameters {
25public:
26    void cubicEndPoints(const SkDCubic& pts) {
27        cubicEndPoints(pts, 0, 1);
28        if (dx() == 0 && dy() == 0) {
29            cubicEndPoints(pts, 0, 2);
30            if (dx() == 0 && dy() == 0) {
31                cubicEndPoints(pts, 0, 3);
32            }
33        }
34    }
35
36    void cubicEndPoints(const SkDCubic& pts, int s, int e) {
37        a = pts[s].fY - pts[e].fY;
38        b = pts[e].fX - pts[s].fX;
39        c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
40    }
41
42    void lineEndPoints(const SkDLine& pts) {
43        a = pts[0].fY - pts[1].fY;
44        b = pts[1].fX - pts[0].fX;
45        c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
46    }
47
48    void quadEndPoints(const SkDQuad& pts) {
49        quadEndPoints(pts, 0, 1);
50        if (dx() == 0 && dy() == 0) {
51            quadEndPoints(pts, 0, 2);
52        }
53    }
54
55    void quadEndPoints(const SkDQuad& pts, int s, int e) {
56        a = pts[s].fY - pts[e].fY;
57        b = pts[e].fX - pts[s].fX;
58        c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
59    }
60
61    double normalSquared() const {
62        return a * a + b * b;
63    }
64
65    bool normalize() {
66        double normal = sqrt(normalSquared());
67        if (approximately_zero(normal)) {
68            a = b = c = 0;
69            return false;
70        }
71        double reciprocal = 1 / normal;
72        a *= reciprocal;
73        b *= reciprocal;
74        c *= reciprocal;
75        return true;
76    }
77
78    void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
79        double oneThird = 1 / 3.0;
80        for (int index = 0; index < 4; ++index) {
81            distance[index].fX = index * oneThird;
82            distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
83        }
84    }
85
86    void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
87        double oneHalf = 1 / 2.0;
88        for (int index = 0; index < 3; ++index) {
89            distance[index].fX = index * oneHalf;
90            distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
91        }
92    }
93
94    double controlPtDistance(const SkDCubic& pts, int index) const {
95        SkASSERT(index == 1 || index == 2);
96        return a * pts[index].fX + b * pts[index].fY + c;
97    }
98
99    double controlPtDistance(const SkDQuad& pts) const {
100        return a * pts[1].fX + b * pts[1].fY + c;
101    }
102
103    double pointDistance(const SkDPoint& pt) const {
104        return a * pt.fX + b * pt.fY + c;
105    }
106
107    double dx() const {
108        return b;
109    }
110
111    double dy() const {
112        return -a;
113    }
114
115private:
116    double a;
117    double b;
118    double c;
119};
120