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