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 "SkIntersections.h" 8#include "SkPathOpsLine.h" 9 10/* Determine the intersection point of two lines. This assumes the lines are not parallel, 11 and that that the lines are infinite. 12 From http://en.wikipedia.org/wiki/Line-line_intersection 13 */ 14SkDPoint SkIntersections::Line(const SkDLine& a, const SkDLine& b) { 15 double axLen = a[1].fX - a[0].fX; 16 double ayLen = a[1].fY - a[0].fY; 17 double bxLen = b[1].fX - b[0].fX; 18 double byLen = b[1].fY - b[0].fY; 19 double denom = byLen * axLen - ayLen * bxLen; 20 SkASSERT(denom); 21 double term1 = a[1].fX * a[0].fY - a[1].fY * a[0].fX; 22 double term2 = b[1].fX * b[0].fY - b[1].fY * b[0].fX; 23 SkDPoint p; 24 p.fX = (term1 * bxLen - axLen * term2) / denom; 25 p.fY = (term1 * byLen - ayLen * term2) / denom; 26 return p; 27} 28 29void SkIntersections::cleanUpCoincidence() { 30 SkASSERT(fUsed == 2); 31 // both t values are good 32 bool startMatch = fT[0][0] == 0 && (fT[1][0] == 0 || fT[1][0] == 1); 33 bool endMatch = fT[0][1] == 1 && (fT[1][1] == 0 || fT[1][1] == 1); 34 if (startMatch || endMatch) { 35 removeOne(startMatch); 36 return; 37 } 38 // either t value is good 39 bool pStartMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; 40 bool pEndMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; 41 removeOne(pStartMatch || !pEndMatch); 42} 43 44void SkIntersections::cleanUpParallelLines(bool parallel) { 45 while (fUsed > 2) { 46 removeOne(1); 47 } 48 if (fUsed == 2 && !parallel) { 49 bool startMatch = fT[0][0] == 0 || fT[1][0] == 0 || fT[1][0] == 1; 50 bool endMatch = fT[0][1] == 1 || fT[1][1] == 0 || fT[1][1] == 1; 51 if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) { 52 SkASSERT(startMatch || endMatch); 53 removeOne(endMatch); 54 } 55 } 56} 57 58void SkIntersections::computePoints(const SkDLine& line, int used) { 59 fPt[0] = line.ptAtT(fT[0][0]); 60 if ((fUsed = used) == 2) { 61 fPt[1] = line.ptAtT(fT[0][1]); 62 } 63} 64 65int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) { 66 fMax = 2; 67 SkDVector aLen = a[1] - a[0]; 68 SkDVector bLen = b[1] - b[0]; 69 /* Slopes match when denom goes to zero: 70 axLen / ayLen == bxLen / byLen 71 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen 72 byLen * axLen == ayLen * bxLen 73 byLen * axLen - ayLen * bxLen == 0 ( == denom ) 74 */ 75 double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX; 76 SkDVector ab0 = a[0] - b[0]; 77 double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX; 78 double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX; 79#if 0 80 if (!between(0, numerA, denom) || !between(0, numerB, denom)) { 81 fUsed = 0; 82 return 0; 83 } 84#endif 85 numerA /= denom; 86 numerB /= denom; 87 int used; 88 if (!approximately_zero(denom)) { 89 fT[0][0] = numerA; 90 fT[1][0] = numerB; 91 used = 1; 92 } else { 93 /* See if the axis intercepts match: 94 ay - ax * ayLen / axLen == by - bx * ayLen / axLen 95 axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) 96 axLen * ay - ax * ayLen == axLen * by - bx * ayLen 97 */ 98 if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX, 99 aLen.fX * b[0].fY - aLen.fY * b[0].fX)) { 100 return fUsed = 0; 101 } 102 // there's no great answer for intersection points for coincident rays, but return something 103 fT[0][0] = fT[1][0] = 0; 104 fT[1][0] = fT[1][1] = 1; 105 used = 2; 106 } 107 computePoints(a, used); 108 return fUsed; 109} 110 111// note that this only works if both lines are neither horizontal nor vertical 112int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { 113 fMax = 3; // note that we clean up so that there is no more than two in the end 114 // see if end points intersect the opposite line 115 double t; 116 for (int iA = 0; iA < 2; ++iA) { 117 if ((t = b.exactPoint(a[iA])) >= 0) { 118 insert(iA, t, a[iA]); 119 } 120 } 121 for (int iB = 0; iB < 2; ++iB) { 122 if ((t = a.exactPoint(b[iB])) >= 0) { 123 insert(t, iB, b[iB]); 124 } 125 } 126 /* Determine the intersection point of two line segments 127 Return FALSE if the lines don't intersect 128 from: http://paulbourke.net/geometry/lineline2d/ */ 129 double axLen = a[1].fX - a[0].fX; 130 double ayLen = a[1].fY - a[0].fY; 131 double bxLen = b[1].fX - b[0].fX; 132 double byLen = b[1].fY - b[0].fY; 133 /* Slopes match when denom goes to zero: 134 axLen / ayLen == bxLen / byLen 135 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen 136 byLen * axLen == ayLen * bxLen 137 byLen * axLen - ayLen * bxLen == 0 ( == denom ) 138 */ 139 double axByLen = axLen * byLen; 140 double ayBxLen = ayLen * bxLen; 141 // detect parallel lines the same way here and in SkOpAngle operator < 142 // so that non-parallel means they are also sortable 143 bool unparallel = fAllowNear ? NotAlmostEqualUlps(axByLen, ayBxLen) 144 : NotAlmostDequalUlps(axByLen, ayBxLen); 145 if (unparallel && fUsed == 0) { 146 double ab0y = a[0].fY - b[0].fY; 147 double ab0x = a[0].fX - b[0].fX; 148 double numerA = ab0y * bxLen - byLen * ab0x; 149 double numerB = ab0y * axLen - ayLen * ab0x; 150 double denom = axByLen - ayBxLen; 151 if (between(0, numerA, denom) && between(0, numerB, denom)) { 152 fT[0][0] = numerA / denom; 153 fT[1][0] = numerB / denom; 154 computePoints(a, 1); 155 } 156 } 157/* Allow tracking that both sets of end points are near each other -- the lines are entirely 158 coincident -- even when the end points are not exactly the same. 159 Mark this as a 'wild card' for the end points, so that either point is considered totally 160 coincident. Then, avoid folding the lines over each other, but allow either end to mate 161 to the next set of lines. 162 */ 163 if (fAllowNear || !unparallel) { 164 double aNearB[2]; 165 double bNearA[2]; 166 bool aNotB[2] = {false, false}; 167 bool bNotA[2] = {false, false}; 168 int nearCount = 0; 169 for (int index = 0; index < 2; ++index) { 170 aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]); 171 nearCount += t >= 0; 172 bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]); 173 nearCount += t >= 0; 174 } 175 if (nearCount > 0) { 176 for (int iA = 0; iA < 2; ++iA) { 177 if (!aNotB[iA]) { 178 continue; 179 } 180 int nearer = aNearB[iA] > 0.5; 181 if (!bNotA[nearer]) { 182 continue; 183 } 184 SkASSERT(a[iA] != b[nearer]); 185 SkASSERT(iA == (bNearA[nearer] > 0.5)); 186 fNearlySame[iA] = true; 187 insertNear(iA, nearer, a[iA], b[nearer]); 188 aNearB[iA] = -1; 189 bNearA[nearer] = -1; 190 nearCount -= 2; 191 } 192 if (nearCount > 0) { 193 for (int iA = 0; iA < 2; ++iA) { 194 if (aNearB[iA] >= 0) { 195 insert(iA, aNearB[iA], a[iA]); 196 } 197 } 198 for (int iB = 0; iB < 2; ++iB) { 199 if (bNearA[iB] >= 0) { 200 insert(bNearA[iB], iB, b[iB]); 201 } 202 } 203 } 204 } 205 } 206 cleanUpParallelLines(!unparallel); 207 SkASSERT(fUsed <= 2); 208 return fUsed; 209} 210 211static int horizontal_coincident(const SkDLine& line, double y) { 212 double min = line[0].fY; 213 double max = line[1].fY; 214 if (min > max) { 215 SkTSwap(min, max); 216 } 217 if (min > y || max < y) { 218 return 0; 219 } 220 if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) { 221 return 2; 222 } 223 return 1; 224} 225 226static double horizontal_intercept(const SkDLine& line, double y) { 227 return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY)); 228} 229 230int SkIntersections::horizontal(const SkDLine& line, double y) { 231 fMax = 2; 232 int horizontalType = horizontal_coincident(line, y); 233 if (horizontalType == 1) { 234 fT[0][0] = horizontal_intercept(line, y); 235 } else if (horizontalType == 2) { 236 fT[0][0] = 0; 237 fT[0][1] = 1; 238 } 239 return fUsed = horizontalType; 240} 241 242int SkIntersections::horizontal(const SkDLine& line, double left, double right, 243 double y, bool flipped) { 244 fMax = 3; // clean up parallel at the end will limit the result to 2 at the most 245 // see if end points intersect the opposite line 246 double t; 247 const SkDPoint leftPt = { left, y }; 248 if ((t = line.exactPoint(leftPt)) >= 0) { 249 insert(t, (double) flipped, leftPt); 250 } 251 if (left != right) { 252 const SkDPoint rightPt = { right, y }; 253 if ((t = line.exactPoint(rightPt)) >= 0) { 254 insert(t, (double) !flipped, rightPt); 255 } 256 for (int index = 0; index < 2; ++index) { 257 if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) { 258 insert((double) index, flipped ? 1 - t : t, line[index]); 259 } 260 } 261 } 262 int result = horizontal_coincident(line, y); 263 if (result == 1 && fUsed == 0) { 264 fT[0][0] = horizontal_intercept(line, y); 265 double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); 266 if (between(left, xIntercept, right)) { 267 fT[1][0] = (xIntercept - left) / (right - left); 268 if (flipped) { 269 // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX 270 for (int index = 0; index < result; ++index) { 271 fT[1][index] = 1 - fT[1][index]; 272 } 273 } 274 fPt[0].fX = xIntercept; 275 fPt[0].fY = y; 276 fUsed = 1; 277 } 278 } 279 if (fAllowNear || result == 2) { 280 if ((t = line.nearPoint(leftPt, NULL)) >= 0) { 281 insert(t, (double) flipped, leftPt); 282 } 283 if (left != right) { 284 const SkDPoint rightPt = { right, y }; 285 if ((t = line.nearPoint(rightPt, NULL)) >= 0) { 286 insert(t, (double) !flipped, rightPt); 287 } 288 for (int index = 0; index < 2; ++index) { 289 if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) { 290 insert((double) index, flipped ? 1 - t : t, line[index]); 291 } 292 } 293 } 294 } 295 cleanUpParallelLines(result == 2); 296 return fUsed; 297} 298 299static int vertical_coincident(const SkDLine& line, double x) { 300 double min = line[0].fX; 301 double max = line[1].fX; 302 if (min > max) { 303 SkTSwap(min, max); 304 } 305 if (!precisely_between(min, x, max)) { 306 return 0; 307 } 308 if (AlmostEqualUlps(min, max)) { 309 return 2; 310 } 311 return 1; 312} 313 314static double vertical_intercept(const SkDLine& line, double x) { 315 return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX)); 316} 317 318int SkIntersections::vertical(const SkDLine& line, double x) { 319 fMax = 2; 320 int verticalType = vertical_coincident(line, x); 321 if (verticalType == 1) { 322 fT[0][0] = vertical_intercept(line, x); 323 } else if (verticalType == 2) { 324 fT[0][0] = 0; 325 fT[0][1] = 1; 326 } 327 return fUsed = verticalType; 328} 329 330int SkIntersections::vertical(const SkDLine& line, double top, double bottom, 331 double x, bool flipped) { 332 fMax = 3; // cleanup parallel lines will bring this back line 333 // see if end points intersect the opposite line 334 double t; 335 SkDPoint topPt = { x, top }; 336 if ((t = line.exactPoint(topPt)) >= 0) { 337 insert(t, (double) flipped, topPt); 338 } 339 if (top != bottom) { 340 SkDPoint bottomPt = { x, bottom }; 341 if ((t = line.exactPoint(bottomPt)) >= 0) { 342 insert(t, (double) !flipped, bottomPt); 343 } 344 for (int index = 0; index < 2; ++index) { 345 if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) { 346 insert((double) index, flipped ? 1 - t : t, line[index]); 347 } 348 } 349 } 350 int result = vertical_coincident(line, x); 351 if (result == 1 && fUsed == 0) { 352 fT[0][0] = vertical_intercept(line, x); 353 double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); 354 if (between(top, yIntercept, bottom)) { 355 fT[1][0] = (yIntercept - top) / (bottom - top); 356 if (flipped) { 357 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY 358 for (int index = 0; index < result; ++index) { 359 fT[1][index] = 1 - fT[1][index]; 360 } 361 } 362 fPt[0].fX = x; 363 fPt[0].fY = yIntercept; 364 fUsed = 1; 365 } 366 } 367 if (fAllowNear || result == 2) { 368 if ((t = line.nearPoint(topPt, NULL)) >= 0) { 369 insert(t, (double) flipped, topPt); 370 } 371 if (top != bottom) { 372 SkDPoint bottomPt = { x, bottom }; 373 if ((t = line.nearPoint(bottomPt, NULL)) >= 0) { 374 insert(t, (double) !flipped, bottomPt); 375 } 376 for (int index = 0; index < 2; ++index) { 377 if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) { 378 insert((double) index, flipped ? 1 - t : t, line[index]); 379 } 380 } 381 } 382 } 383 cleanUpParallelLines(result == 2); 384 SkASSERT(fUsed <= 2); 385 return fUsed; 386} 387 388// from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py 389// 4 subs, 2 muls, 1 cmp 390static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { 391 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); 392} 393 394// 16 subs, 8 muls, 6 cmps 395bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { 396 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) 397 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); 398} 399