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 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)); 38 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 44 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 56 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 66 double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) 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 if (unequal) { 90 *unequal = (float) largest != (float) (largest + dist); 91 } 92 t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3 93 SkASSERT(between(0, t, 1)); 94 return t; 95 } 96 97 bool SkDLine::nearRay(const SkDPoint& xy) const { 98 // project a perpendicular ray from the point to the line; find the T on the line 99 SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line 100 double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay 101 SkDVector ab0 = xy - fPts[0]; 102 double numer = len.fX * ab0.fX + ab0.fY * len.fY; 103 double t = numer / denom; 104 SkDPoint realPt = ptAtT(t); 105 double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? 106 // find the ordinal in the original line with the largest unsigned exponent 107 double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 108 double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY); 109 largest = SkTMax(largest, -tiniest); 110 return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? 111 } 112 113 // Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2) 114 // OPTIMIZE: a specialty routine could speed this up -- may not be called very often though 115 bool SkDLine::NearRay(double x1, double y1, double x2, double y2) { 116 double denom1 = x1 * x1 + y1 * y1; 117 double denom2 = x2 * x2 + y2 * y2; 118 SkDLine line = {{{0, 0}, {x1, y1}}}; 119 SkDPoint pt = {x2, y2}; 120 if (denom2 > denom1) { 121 SkTSwap(line[1], pt); 122 } 123 return line.nearRay(pt); 124 } 125 126 double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) { 127 if (xy.fY == y) { 128 if (xy.fX == left) { 129 return 0; 130 } 131 if (xy.fX == right) { 132 return 1; 133 } 134 } 135 return -1; 136 } 137 138 double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) { 139 if (!AlmostBequalUlps(xy.fY, y)) { 140 return -1; 141 } 142 if (!AlmostBetweenUlps(left, xy.fX, right)) { 143 return -1; 144 } 145 double t = (xy.fX - left) / (right - left); 146 t = SkPinT(t); 147 SkASSERT(between(0, t, 1)); 148 double realPtX = (1 - t) * left + t * right; 149 SkDVector distU = {xy.fY - y, xy.fX - realPtX}; 150 double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 151 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 152 double tiniest = SkTMin(SkTMin(y, left), right); 153 double largest = SkTMax(SkTMax(y, left), right); 154 largest = SkTMax(largest, -tiniest); 155 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 156 return -1; 157 } 158 return t; 159 } 160 161 double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) { 162 if (xy.fX == x) { 163 if (xy.fY == top) { 164 return 0; 165 } 166 if (xy.fY == bottom) { 167 return 1; 168 } 169 } 170 return -1; 171 } 172 173 double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) { 174 if (!AlmostBequalUlps(xy.fX, x)) { 175 return -1; 176 } 177 if (!AlmostBetweenUlps(top, xy.fY, bottom)) { 178 return -1; 179 } 180 double t = (xy.fY - top) / (bottom - top); 181 t = SkPinT(t); 182 SkASSERT(between(0, t, 1)); 183 double realPtY = (1 - t) * top + t * bottom; 184 SkDVector distU = {xy.fX - x, xy.fY - realPtY}; 185 double distSq = distU.fX * distU.fX + distU.fY * distU.fY; 186 double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ? 187 double tiniest = SkTMin(SkTMin(x, top), bottom); 188 double largest = SkTMax(SkTMax(x, top), bottom); 189 largest = SkTMax(largest, -tiniest); 190 if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance? 191 return -1; 192 } 193 return t; 194 } 195