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 | #ifndef SkPathOpsPoint_DEFINED |
| 8 | #define SkPathOpsPoint_DEFINED |
| 9 | |
| 10 | #include "SkPathOpsTypes.h" |
| 11 | #include "SkPoint.h" |
| 12 | |
caryclark@google.com | a5e5592 | 2013-05-07 18:51:31 +0000 | [diff] [blame] | 13 | inline bool AlmostEqualUlps(const SkPoint& pt1, const SkPoint& pt2) { |
| 14 | return AlmostEqualUlps(pt1.fX, pt2.fX) && AlmostEqualUlps(pt1.fY, pt2.fY); |
| 15 | } |
| 16 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 17 | struct SkDVector { |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 18 | double fX; |
| 19 | double fY; |
| 20 | |
| 21 | void set(const SkVector& pt) { |
| 22 | fX = pt.fX; |
| 23 | fY = pt.fY; |
| 24 | } |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 25 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 26 | // only used by testing |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 27 | void operator+=(const SkDVector& v) { |
| 28 | fX += v.fX; |
| 29 | fY += v.fY; |
| 30 | } |
| 31 | |
Cary Clark | d2eb581 | 2017-01-18 11:00:57 -0500 | [diff] [blame^] | 32 | SkDVector operator+(const SkDVector& v) const { |
| 33 | SkDVector result = *this; |
| 34 | result += v; |
| 35 | return result; |
| 36 | } |
| 37 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 38 | // only called by nearestT, which is currently only used by testing |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 39 | void operator-=(const SkDVector& v) { |
| 40 | fX -= v.fX; |
| 41 | fY -= v.fY; |
| 42 | } |
| 43 | |
Cary Clark | d2eb581 | 2017-01-18 11:00:57 -0500 | [diff] [blame^] | 44 | SkDVector operator-(const SkDVector& v) const { |
| 45 | SkDVector result = *this; |
| 46 | result -= v; |
| 47 | return result; |
| 48 | } |
| 49 | |
| 50 | SkDVector operator-() const { |
| 51 | SkDVector result = { -fX, -fY }; |
| 52 | return result; |
| 53 | } |
| 54 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 55 | void operator/=(const double s) { |
| 56 | fX /= s; |
| 57 | fY /= s; |
| 58 | } |
| 59 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 60 | // only used by testing |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 61 | void operator*=(const double s) { |
| 62 | fX *= s; |
| 63 | fY *= s; |
| 64 | } |
| 65 | |
| 66 | SkVector asSkVector() const { |
| 67 | SkVector v = {SkDoubleToScalar(fX), SkDoubleToScalar(fY)}; |
| 68 | return v; |
| 69 | } |
| 70 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 71 | // only used by testing |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 72 | double cross(const SkDVector& a) const { |
| 73 | return fX * a.fY - fY * a.fX; |
| 74 | } |
| 75 | |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 76 | // similar to cross, this bastardization considers nearly coincident to be zero |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 77 | // uses ulps epsilon == 16 |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 78 | double crossCheck(const SkDVector& a) const { |
| 79 | double xy = fX * a.fY; |
| 80 | double yx = fY * a.fX; |
| 81 | return AlmostEqualUlps(xy, yx) ? 0 : xy - yx; |
| 82 | } |
| 83 | |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 84 | // allow tinier numbers |
| 85 | double crossNoNormalCheck(const SkDVector& a) const { |
| 86 | double xy = fX * a.fY; |
| 87 | double yx = fY * a.fX; |
| 88 | return AlmostEqualUlpsNoNormalCheck(xy, yx) ? 0 : xy - yx; |
| 89 | } |
| 90 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 91 | double dot(const SkDVector& a) const { |
| 92 | return fX * a.fX + fY * a.fY; |
| 93 | } |
| 94 | |
| 95 | double length() const { |
| 96 | return sqrt(lengthSquared()); |
| 97 | } |
| 98 | |
| 99 | double lengthSquared() const { |
| 100 | return fX * fX + fY * fY; |
| 101 | } |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 102 | |
| 103 | void normalize() { |
| 104 | double inverseLength = 1 / this->length(); |
| 105 | fX *= inverseLength; |
| 106 | fY *= inverseLength; |
| 107 | } |
Cary Clark | d2eb581 | 2017-01-18 11:00:57 -0500 | [diff] [blame^] | 108 | |
| 109 | void setLengthSquared(double lenSquared) { |
| 110 | double inverseLength = lenSquared / this->lengthSquared(); |
| 111 | fX *= inverseLength; |
| 112 | fY *= inverseLength; |
| 113 | } |
| 114 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 115 | }; |
| 116 | |
| 117 | struct SkDPoint { |
| 118 | double fX; |
| 119 | double fY; |
| 120 | |
| 121 | void set(const SkPoint& pt) { |
| 122 | fX = pt.fX; |
| 123 | fY = pt.fY; |
| 124 | } |
| 125 | |
| 126 | friend SkDVector operator-(const SkDPoint& a, const SkDPoint& b); |
| 127 | |
| 128 | friend bool operator==(const SkDPoint& a, const SkDPoint& b) { |
| 129 | return a.fX == b.fX && a.fY == b.fY; |
| 130 | } |
| 131 | |
| 132 | friend bool operator!=(const SkDPoint& a, const SkDPoint& b) { |
| 133 | return a.fX != b.fX || a.fY != b.fY; |
| 134 | } |
| 135 | |
| 136 | void operator=(const SkPoint& pt) { |
| 137 | fX = pt.fX; |
| 138 | fY = pt.fY; |
| 139 | } |
| 140 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 141 | // only used by testing |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 142 | void operator+=(const SkDVector& v) { |
| 143 | fX += v.fX; |
| 144 | fY += v.fY; |
| 145 | } |
| 146 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 147 | // only used by testing |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 148 | void operator-=(const SkDVector& v) { |
| 149 | fX -= v.fX; |
| 150 | fY -= v.fY; |
| 151 | } |
| 152 | |
Cary Clark | d2eb581 | 2017-01-18 11:00:57 -0500 | [diff] [blame^] | 153 | SkDPoint operator+(const SkDVector& v) const { |
caryclark | 03b03ca | 2015-04-23 09:13:37 -0700 | [diff] [blame] | 154 | SkDPoint result = *this; |
| 155 | result += v; |
| 156 | return result; |
| 157 | } |
| 158 | |
| 159 | // only used by testing |
Cary Clark | d2eb581 | 2017-01-18 11:00:57 -0500 | [diff] [blame^] | 160 | SkDPoint operator-(const SkDVector& v) const { |
caryclark | 03b03ca | 2015-04-23 09:13:37 -0700 | [diff] [blame] | 161 | SkDPoint result = *this; |
| 162 | result -= v; |
| 163 | return result; |
| 164 | } |
| 165 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 166 | // note: this can not be implemented with |
| 167 | // return approximately_equal(a.fY, fY) && approximately_equal(a.fX, fX); |
caryclark@google.com | a2bbc6e | 2013-11-01 17:36:03 +0000 | [diff] [blame] | 168 | // because that will not take the magnitude of the values into account |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 169 | bool approximatelyDEqual(const SkDPoint& a) const { |
| 170 | if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { |
| 171 | return true; |
| 172 | } |
| 173 | if (!RoughlyEqualUlps(fX, a.fX) || !RoughlyEqualUlps(fY, a.fY)) { |
| 174 | return false; |
| 175 | } |
| 176 | double dist = distance(a); // OPTIMIZATION: can we compare against distSq instead ? |
| 177 | double tiniest = SkTMin(SkTMin(SkTMin(fX, a.fX), fY), a.fY); |
| 178 | double largest = SkTMax(SkTMax(SkTMax(fX, a.fX), fY), a.fY); |
| 179 | largest = SkTMax(largest, -tiniest); |
| 180 | return AlmostDequalUlps(largest, largest + dist); // is the dist within ULPS tolerance? |
| 181 | } |
| 182 | |
| 183 | bool approximatelyDEqual(const SkPoint& a) const { |
| 184 | SkDPoint dA; |
| 185 | dA.set(a); |
| 186 | return approximatelyDEqual(dA); |
| 187 | } |
| 188 | |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 189 | bool approximatelyEqual(const SkDPoint& a) const { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 190 | if (approximately_equal(fX, a.fX) && approximately_equal(fY, a.fY)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 191 | return true; |
| 192 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 193 | if (!RoughlyEqualUlps(fX, a.fX) || !RoughlyEqualUlps(fY, a.fY)) { |
| 194 | return false; |
| 195 | } |
| 196 | double dist = distance(a); // OPTIMIZATION: can we compare against distSq instead ? |
| 197 | double tiniest = SkTMin(SkTMin(SkTMin(fX, a.fX), fY), a.fY); |
| 198 | double largest = SkTMax(SkTMax(SkTMax(fX, a.fX), fY), a.fY); |
| 199 | largest = SkTMax(largest, -tiniest); |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 200 | return AlmostPequalUlps(largest, largest + dist); // is the dist within ULPS tolerance? |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 201 | } |
| 202 | |
| 203 | bool approximatelyEqual(const SkPoint& a) const { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 204 | SkDPoint dA; |
| 205 | dA.set(a); |
| 206 | return approximatelyEqual(dA); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 207 | } |
| 208 | |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 209 | static bool ApproximatelyEqual(const SkPoint& a, const SkPoint& b) { |
| 210 | if (approximately_equal(a.fX, b.fX) && approximately_equal(a.fY, b.fY)) { |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 211 | return true; |
| 212 | } |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 213 | if (!RoughlyEqualUlps(a.fX, b.fX) || !RoughlyEqualUlps(a.fY, b.fY)) { |
| 214 | return false; |
| 215 | } |
| 216 | SkDPoint dA, dB; |
| 217 | dA.set(a); |
| 218 | dB.set(b); |
| 219 | double dist = dA.distance(dB); // OPTIMIZATION: can we compare against distSq instead ? |
| 220 | float tiniest = SkTMin(SkTMin(SkTMin(a.fX, b.fX), a.fY), b.fY); |
| 221 | float largest = SkTMax(SkTMax(SkTMax(a.fX, b.fX), a.fY), b.fY); |
| 222 | largest = SkTMax(largest, -tiniest); |
caryclark | 55888e4 | 2016-07-18 10:01:36 -0700 | [diff] [blame] | 223 | return AlmostDequalUlps((double) largest, largest + dist); // is dist within ULPS tolerance? |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 224 | } |
| 225 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 226 | // only used by testing |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 227 | bool approximatelyZero() const { |
| 228 | return approximately_zero(fX) && approximately_zero(fY); |
| 229 | } |
| 230 | |
| 231 | SkPoint asSkPoint() const { |
| 232 | SkPoint pt = {SkDoubleToScalar(fX), SkDoubleToScalar(fY)}; |
| 233 | return pt; |
| 234 | } |
| 235 | |
| 236 | double distance(const SkDPoint& a) const { |
| 237 | SkDVector temp = *this - a; |
| 238 | return temp.length(); |
| 239 | } |
| 240 | |
| 241 | double distanceSquared(const SkDPoint& a) const { |
| 242 | SkDVector temp = *this - a; |
| 243 | return temp.lengthSquared(); |
| 244 | } |
| 245 | |
caryclark@google.com | cffbcc3 | 2013-06-04 17:59:42 +0000 | [diff] [blame] | 246 | static SkDPoint Mid(const SkDPoint& a, const SkDPoint& b) { |
| 247 | SkDPoint result; |
| 248 | result.fX = (a.fX + b.fX) / 2; |
| 249 | result.fY = (a.fY + b.fY) / 2; |
| 250 | return result; |
| 251 | } |
| 252 | |
caryclark | 5435929 | 2015-03-26 07:52:43 -0700 | [diff] [blame] | 253 | bool roughlyEqual(const SkDPoint& a) const { |
caryclark@google.com | 7eaa53d | 2013-10-02 14:49:34 +0000 | [diff] [blame] | 254 | if (roughly_equal(fX, a.fX) && roughly_equal(fY, a.fY)) { |
| 255 | return true; |
| 256 | } |
| 257 | double dist = distance(a); // OPTIMIZATION: can we compare against distSq instead ? |
| 258 | double tiniest = SkTMin(SkTMin(SkTMin(fX, a.fX), fY), a.fY); |
| 259 | double largest = SkTMax(SkTMax(SkTMax(fX, a.fX), fY), a.fY); |
| 260 | largest = SkTMax(largest, -tiniest); |
| 261 | return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance? |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 262 | } |
| 263 | |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 264 | static bool RoughlyEqual(const SkPoint& a, const SkPoint& b) { |
caryclark | 624637c | 2015-05-11 07:21:27 -0700 | [diff] [blame] | 265 | if (!RoughlyEqualUlps(a.fX, b.fX) && !RoughlyEqualUlps(a.fY, b.fY)) { |
caryclark | 1049f12 | 2015-04-20 08:31:59 -0700 | [diff] [blame] | 266 | return false; |
| 267 | } |
| 268 | SkDPoint dA, dB; |
| 269 | dA.set(a); |
| 270 | dB.set(b); |
| 271 | double dist = dA.distance(dB); // OPTIMIZATION: can we compare against distSq instead ? |
| 272 | float tiniest = SkTMin(SkTMin(SkTMin(a.fX, b.fX), a.fY), b.fY); |
| 273 | float largest = SkTMax(SkTMax(SkTMax(a.fX, b.fX), a.fY), b.fY); |
| 274 | largest = SkTMax(largest, -tiniest); |
| 275 | return RoughlyEqualUlps((double) largest, largest + dist); // is dist within ULPS tolerance? |
| 276 | } |
| 277 | |
caryclark | 30b9fdd | 2016-08-31 14:36:29 -0700 | [diff] [blame] | 278 | // very light weight check, should only be used for inequality check |
| 279 | static bool WayRoughlyEqual(const SkPoint& a, const SkPoint& b) { |
| 280 | float largestNumber = SkTMax(SkTAbs(a.fX), SkTMax(SkTAbs(a.fY), |
| 281 | SkTMax(SkTAbs(b.fX), SkTAbs(b.fY)))); |
| 282 | SkVector diffs = a - b; |
| 283 | float largestDiff = SkTMax(diffs.fX, diffs.fY); |
| 284 | return roughly_zero_when_compared_to(largestDiff, largestNumber); |
| 285 | } |
| 286 | |
commit-bot@chromium.org | 4431e77 | 2014-04-14 17:08:59 +0000 | [diff] [blame] | 287 | // utilities callable by the user from the debugger when the implementation code is linked in |
| 288 | void dump() const; |
| 289 | static void Dump(const SkPoint& pt); |
caryclark | 65f5531 | 2014-11-13 06:58:52 -0800 | [diff] [blame] | 290 | static void DumpHex(const SkPoint& pt); |
caryclark@google.com | 07393ca | 2013-04-08 11:47:37 +0000 | [diff] [blame] | 291 | }; |
| 292 | |
| 293 | #endif |