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 
9 // may have this below somewhere else already:
10 // copying here because I thought it was clever
11 
12 // Copyright 2001, softSurfer (www.softsurfer.com)
13 // This code may be freely used and modified for any purpose
14 // providing that this copyright notice is included with it.
15 // SoftSurfer makes no warranty for this code, and cannot be held
16 // liable for any real or imagined damage resulting from its use.
17 // Users of this code must verify correctness for their application.
18 
19 // Assume that a class is already given for the object:
20 //    Point with coordinates {float x, y;}
21 //===================================================================
22 
23 // (only used by testing)
24 // isLeft(): tests if a point is Left|On|Right of an infinite line.
25 //    Input:  three points P0, P1, and P2
26 //    Return: >0 for P2 left of the line through P0 and P1
27 //            =0 for P2 on the line
28 //            <0 for P2 right of the line
29 //    See: the January 2001 Algorithm on Area of Triangles
30 //    return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y));
isLeft(const SkDPoint & pt) const31 double SkDLine::isLeft(const SkDPoint& pt) const {
32     SkDVector p0 = fPts[1] - fPts[0];
33     SkDVector p2 = pt - fPts[0];
34     return p0.cross(p2);
35 }
36 
ptAtT(double t) const37 SkDPoint SkDLine::ptAtT(double t) const {
38     if (0 == t) {
39         return fPts[0];
40     }
41     if (1 == t) {
42         return fPts[1];
43     }
44     double one_t = 1 - t;
45     SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
46     return result;
47 }
48 
exactPoint(const SkDPoint & xy) const49 double SkDLine::exactPoint(const SkDPoint& xy) const {
50     if (xy == fPts[0]) {  // do cheapest test first
51         return 0;
52     }
53     if (xy == fPts[1]) {
54         return 1;
55     }
56     return -1;
57 }
58 
nearPoint(const SkDPoint & xy,bool * unequal) const59 double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const {
60     if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
61             || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
62         return -1;
63     }
64     // project a perpendicular ray from the point to the line; find the T on the line
65     SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
66     double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
67     SkDVector ab0 = xy - fPts[0];
68     double numer = len.fX * ab0.fX + ab0.fY * len.fY;
69     if (!between(0, numer, denom)) {
70         return -1;
71     }
72     double t = numer / denom;
73     SkDPoint realPt = ptAtT(t);
74     double dist = realPt.distance(xy);   // OPTIMIZATION: can we compare against distSq instead ?
75     // find the ordinal in the original line with the largest unsigned exponent
76     double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
77     double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
78     largest = SkTMax(largest, -tiniest);
79     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
80         return -1;
81     }
82     if (unequal) {
83         *unequal = (float) largest != (float) (largest + dist);
84     }
85     t = SkPinT(t);  // a looser pin breaks skpwww_lptemp_com_3
86     SkASSERT(between(0, t, 1));
87     return t;
88 }
89 
nearRay(const SkDPoint & xy) const90 bool SkDLine::nearRay(const SkDPoint& xy) const {
91     // project a perpendicular ray from the point to the line; find the T on the line
92     SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
93     double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
94     SkDVector ab0 = xy - fPts[0];
95     double numer = len.fX * ab0.fX + ab0.fY * len.fY;
96     double t = numer / denom;
97     SkDPoint realPt = ptAtT(t);
98     double dist = realPt.distance(xy);   // OPTIMIZATION: can we compare against distSq instead ?
99     // find the ordinal in the original line with the largest unsigned exponent
100     double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
101     double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
102     largest = SkTMax(largest, -tiniest);
103     return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
104 }
105 
ExactPointH(const SkDPoint & xy,double left,double right,double y)106 double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
107     if (xy.fY == y) {
108         if (xy.fX == left) {
109             return 0;
110         }
111         if (xy.fX == right) {
112             return 1;
113         }
114     }
115     return -1;
116 }
117 
NearPointH(const SkDPoint & xy,double left,double right,double y)118 double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
119     if (!AlmostBequalUlps(xy.fY, y)) {
120         return -1;
121     }
122     if (!AlmostBetweenUlps(left, xy.fX, right)) {
123         return -1;
124     }
125     double t = (xy.fX - left) / (right - left);
126     t = SkPinT(t);
127     SkASSERT(between(0, t, 1));
128     double realPtX = (1 - t) * left + t * right;
129     SkDVector distU = {xy.fY - y, xy.fX - realPtX};
130     double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
131     double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
132     double tiniest = SkTMin(SkTMin(y, left), right);
133     double largest = SkTMax(SkTMax(y, left), right);
134     largest = SkTMax(largest, -tiniest);
135     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
136         return -1;
137     }
138     return t;
139 }
140 
ExactPointV(const SkDPoint & xy,double top,double bottom,double x)141 double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
142     if (xy.fX == x) {
143         if (xy.fY == top) {
144             return 0;
145         }
146         if (xy.fY == bottom) {
147             return 1;
148         }
149     }
150     return -1;
151 }
152 
NearPointV(const SkDPoint & xy,double top,double bottom,double x)153 double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
154     if (!AlmostBequalUlps(xy.fX, x)) {
155         return -1;
156     }
157     if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
158         return -1;
159     }
160     double t = (xy.fY - top) / (bottom - top);
161     t = SkPinT(t);
162     SkASSERT(between(0, t, 1));
163     double realPtY = (1 - t) * top + t * bottom;
164     SkDVector distU = {xy.fX - x, xy.fY - realPtY};
165     double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
166     double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
167     double tiniest = SkTMin(SkTMin(x, top), bottom);
168     double largest = SkTMax(SkTMax(x, top), bottom);
169     largest = SkTMax(largest, -tiniest);
170     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
171         return -1;
172     }
173     return t;
174 }
175