caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame^] | 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 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | |
caryclark@google.com | 4fdbb22 | 2013-07-23 15:27:41 +0000 | [diff] [blame] | 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 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 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 | } |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 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 | |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 66 | double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const { |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 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; |
caryclark@google.com | 4fdbb22 | 2013-07-23 15:27:41 +0000 | [diff] [blame] | 80 | SkDPoint realPt = ptAtT(t); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 81 | double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ? |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 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 | } |
caryclark | dac1d17 | 2014-06-17 05:15:38 -0700 | [diff] [blame] | 89 | if (unequal) { |
| 90 | *unequal = (float) largest != (float) (largest + dist); |
| 91 | } |
caryclark | 65b427c | 2014-09-18 10:32:57 -0700 | [diff] [blame] | 92 | t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3 |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 93 | SkASSERT(between(0, t, 1)); |
| 94 | return t; |
| 95 | } |
| 96 | |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 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 | |
reed | 0dc4dd6 | 2015-03-24 13:55:33 -0700 | [diff] [blame^] | 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 | |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 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) { |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 139 | if (!AlmostBequalUlps(xy.fY, y)) { |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 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)); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 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 | } |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 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) { |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 174 | if (!AlmostBequalUlps(xy.fX, x)) { |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 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)); |
caryclark@google.com | 570863f | 2013-09-16 15:55:01 +0000 | [diff] [blame] | 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 | } |
caryclark@google.com | fa2aeee | 2013-07-15 13:29:13 +0000 | [diff] [blame] | 193 | return t; |
| 194 | } |