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)); 31 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 37 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 49 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 59 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 90 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 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 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 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 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