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 "SkPathOpsLine.h"
8
9SkDPoint SkDLine::ptAtT(double t) const {
10    if (0 == t) {
11        return fPts[0];
12    }
13    if (1 == t) {
14        return fPts[1];
15    }
16    double one_t = 1 - t;
17    SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
18    return result;
19}
20
21double SkDLine::exactPoint(const SkDPoint& xy) const {
22    if (xy == fPts[0]) {  // do cheapest test first
23        return 0;
24    }
25    if (xy == fPts[1]) {
26        return 1;
27    }
28    return -1;
29}
30
31double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const {
32    if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
33            || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
34        return -1;
35    }
36    // project a perpendicular ray from the point to the line; find the T on the line
37    SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
38    double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
39    SkDVector ab0 = xy - fPts[0];
40    double numer = len.fX * ab0.fX + ab0.fY * len.fY;
41    if (!between(0, numer, denom)) {
42        return -1;
43    }
44    if (!denom) {
45        return 0;
46    }
47    double t = numer / denom;
48    SkDPoint realPt = ptAtT(t);
49    double dist = realPt.distance(xy);   // OPTIMIZATION: can we compare against distSq instead ?
50    // find the ordinal in the original line with the largest unsigned exponent
51    double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
52    double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
53    largest = SkTMax(largest, -tiniest);
54    if (!AlmostEqualUlps_Pin(largest, largest + dist)) { // is the dist within ULPS tolerance?
55        return -1;
56    }
57    if (unequal) {
58        *unequal = (float) largest != (float) (largest + dist);
59    }
60    t = SkPinT(t);  // a looser pin breaks skpwww_lptemp_com_3
61    SkASSERT(between(0, t, 1));
62    return t;
63}
64
65bool SkDLine::nearRay(const SkDPoint& xy) const {
66    // project a perpendicular ray from the point to the line; find the T on the line
67    SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
68    double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
69    SkDVector ab0 = xy - fPts[0];
70    double numer = len.fX * ab0.fX + ab0.fY * len.fY;
71    double t = numer / denom;
72    SkDPoint realPt = ptAtT(t);
73    double dist = realPt.distance(xy);   // OPTIMIZATION: can we compare against distSq instead ?
74    // find the ordinal in the original line with the largest unsigned exponent
75    double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
76    double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
77    largest = SkTMax(largest, -tiniest);
78    return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
79}
80
81double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
82    if (xy.fY == y) {
83        if (xy.fX == left) {
84            return 0;
85        }
86        if (xy.fX == right) {
87            return 1;
88        }
89    }
90    return -1;
91}
92
93double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
94    if (!AlmostBequalUlps(xy.fY, y)) {
95        return -1;
96    }
97    if (!AlmostBetweenUlps(left, xy.fX, right)) {
98        return -1;
99    }
100    double t = (xy.fX - left) / (right - left);
101    t = SkPinT(t);
102    SkASSERT(between(0, t, 1));
103    double realPtX = (1 - t) * left + t * right;
104    SkDVector distU = {xy.fY - y, xy.fX - realPtX};
105    double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
106    double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
107    double tiniest = SkTMin(SkTMin(y, left), right);
108    double largest = SkTMax(SkTMax(y, left), right);
109    largest = SkTMax(largest, -tiniest);
110    if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
111        return -1;
112    }
113    return t;
114}
115
116double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
117    if (xy.fX == x) {
118        if (xy.fY == top) {
119            return 0;
120        }
121        if (xy.fY == bottom) {
122            return 1;
123        }
124    }
125    return -1;
126}
127
128double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
129    if (!AlmostBequalUlps(xy.fX, x)) {
130        return -1;
131    }
132    if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
133        return -1;
134    }
135    double t = (xy.fY - top) / (bottom - top);
136    t = SkPinT(t);
137    SkASSERT(between(0, t, 1));
138    double realPtY = (1 - t) * top + t * bottom;
139    SkDVector distU = {xy.fX - x, xy.fY - realPtY};
140    double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
141    double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
142    double tiniest = SkTMin(SkTMin(x, top), bottom);
143    double largest = SkTMax(SkTMax(x, top), bottom);
144    largest = SkTMax(largest, -tiniest);
145    if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
146        return -1;
147    }
148    return t;
149}
150