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
subDivide(double t1,double t2) const9 SkDLine SkDLine::subDivide(double t1, double t2) const {
10 SkDVector delta = tangent();
11 SkDLine dst = {{{
12 fPts[0].fX - t1 * delta.fX, fPts[0].fY - t1 * delta.fY}, {
13 fPts[0].fX - t2 * delta.fX, fPts[0].fY - t2 * delta.fY}}};
14 return dst;
15 }
16
17 // may have this below somewhere else already:
18 // copying here because I thought it was clever
19
20 // Copyright 2001, softSurfer (www.softsurfer.com)
21 // This code may be freely used and modified for any purpose
22 // providing that this copyright notice is included with it.
23 // SoftSurfer makes no warranty for this code, and cannot be held
24 // liable for any real or imagined damage resulting from its use.
25 // Users of this code must verify correctness for their application.
26
27 // Assume that a class is already given for the object:
28 // Point with coordinates {float x, y;}
29 //===================================================================
30
31 // isLeft(): tests if a point is Left|On|Right of an infinite line.
32 // Input: three points P0, P1, and P2
33 // Return: >0 for P2 left of the line through P0 and P1
34 // =0 for P2 on the line
35 // <0 for P2 right of the line
36 // See: the January 2001 Algorithm on Area of Triangles
37 // return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y));
isLeft(const SkDPoint & pt) const38 double SkDLine::isLeft(const SkDPoint& pt) const {
39 SkDVector p0 = fPts[1] - fPts[0];
40 SkDVector p2 = pt - fPts[0];
41 return p0.cross(p2);
42 }
43
ptAtT(double t) const44 SkDPoint SkDLine::ptAtT(double t) const {
45 if (0 == t) {
46 return fPts[0];
47 }
48 if (1 == t) {
49 return fPts[1];
50 }
51 double one_t = 1 - t;
52 SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
53 return result;
54 }
55
exactPoint(const SkDPoint & xy) const56 double SkDLine::exactPoint(const SkDPoint& xy) const {
57 if (xy == fPts[0]) { // do cheapest test first
58 return 0;
59 }
60 if (xy == fPts[1]) {
61 return 1;
62 }
63 return -1;
64 }
65
nearPoint(const SkDPoint & xy) const66 double SkDLine::nearPoint(const SkDPoint& xy) const {
67 if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
68 || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
69 return -1;
70 }
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 if (!between(0, numer, denom)) {
77 return -1;
78 }
79 double t = numer / denom;
80 SkDPoint realPt = ptAtT(t);
81 double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
82 // find the ordinal in the original line with the largest unsigned exponent
83 double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
84 double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
85 largest = SkTMax(largest, -tiniest);
86 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
87 return -1;
88 }
89 t = SkPinT(t);
90 SkASSERT(between(0, t, 1));
91 return t;
92 }
93
nearRay(const SkDPoint & xy) const94 bool SkDLine::nearRay(const SkDPoint& xy) const {
95 // project a perpendicular ray from the point to the line; find the T on the line
96 SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
97 double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
98 SkDVector ab0 = xy - fPts[0];
99 double numer = len.fX * ab0.fX + ab0.fY * len.fY;
100 double t = numer / denom;
101 SkDPoint realPt = ptAtT(t);
102 double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
103 // find the ordinal in the original line with the largest unsigned exponent
104 double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
105 double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
106 largest = SkTMax(largest, -tiniest);
107 return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
108 }
109
110 // Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2)
111 // OPTIMIZE: a specialty routine could speed this up -- may not be called very often though
NearRay(double x1,double y1,double x2,double y2)112 bool SkDLine::NearRay(double x1, double y1, double x2, double y2) {
113 double denom1 = x1 * x1 + y1 * y1;
114 double denom2 = x2 * x2 + y2 * y2;
115 SkDLine line = {{{0, 0}, {x1, y1}}};
116 SkDPoint pt = {x2, y2};
117 if (denom2 > denom1) {
118 SkTSwap(line[1], pt);
119 }
120 return line.nearRay(pt);
121 }
122
ExactPointH(const SkDPoint & xy,double left,double right,double y)123 double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
124 if (xy.fY == y) {
125 if (xy.fX == left) {
126 return 0;
127 }
128 if (xy.fX == right) {
129 return 1;
130 }
131 }
132 return -1;
133 }
134
NearPointH(const SkDPoint & xy,double left,double right,double y)135 double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
136 if (!AlmostBequalUlps(xy.fY, y)) {
137 return -1;
138 }
139 if (!AlmostBetweenUlps(left, xy.fX, right)) {
140 return -1;
141 }
142 double t = (xy.fX - left) / (right - left);
143 t = SkPinT(t);
144 SkASSERT(between(0, t, 1));
145 double realPtX = (1 - t) * left + t * right;
146 SkDVector distU = {xy.fY - y, xy.fX - realPtX};
147 double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
148 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
149 double tiniest = SkTMin(SkTMin(y, left), right);
150 double largest = SkTMax(SkTMax(y, left), right);
151 largest = SkTMax(largest, -tiniest);
152 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
153 return -1;
154 }
155 return t;
156 }
157
ExactPointV(const SkDPoint & xy,double top,double bottom,double x)158 double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
159 if (xy.fX == x) {
160 if (xy.fY == top) {
161 return 0;
162 }
163 if (xy.fY == bottom) {
164 return 1;
165 }
166 }
167 return -1;
168 }
169
NearPointV(const SkDPoint & xy,double top,double bottom,double x)170 double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
171 if (!AlmostBequalUlps(xy.fX, x)) {
172 return -1;
173 }
174 if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
175 return -1;
176 }
177 double t = (xy.fY - top) / (bottom - top);
178 t = SkPinT(t);
179 SkASSERT(between(0, t, 1));
180 double realPtY = (1 - t) * top + t * bottom;
181 SkDVector distU = {xy.fX - x, xy.fY - realPtY};
182 double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
183 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
184 double tiniest = SkTMin(SkTMin(x, top), bottom);
185 double largest = SkTMax(SkTMax(x, top), bottom);
186 largest = SkTMax(largest, -tiniest);
187 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
188 return -1;
189 }
190 return t;
191 }
192
193 #ifdef SK_DEBUG
dump()194 void SkDLine::dump() {
195 SkDebugf("{{");
196 fPts[0].dump();
197 SkDebugf(", ");
198 fPts[1].dump();
199 SkDebugf("}}\n");
200 }
201 #endif
202