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 */ 14 SkDPoint 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 29 void 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 44 void 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 58 void 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 65 int 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 112 int 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 // Skip if each segment contributes to one end point. 177 if (nearCount != 2 || aNotB[0] == aNotB[1]) { 178 for (int iA = 0; iA < 2; ++iA) { 179 if (!aNotB[iA]) { 180 continue; 181 } 182 int nearer = aNearB[iA] > 0.5; 183 if (!bNotA[nearer]) { 184 continue; 185 } 186 SkASSERT(a[iA] != b[nearer]); 187 SkASSERT(iA == (bNearA[nearer] > 0.5)); 188 fNearlySame[iA] = true; 189 insertNear(iA, nearer, a[iA], b[nearer]); 190 aNearB[iA] = -1; 191 bNearA[nearer] = -1; 192 nearCount -= 2; 193 } 194 } 195 if (nearCount > 0) { 196 for (int iA = 0; iA < 2; ++iA) { 197 if (aNearB[iA] >= 0) { 198 insert(iA, aNearB[iA], a[iA]); 199 } 200 } 201 for (int iB = 0; iB < 2; ++iB) { 202 if (bNearA[iB] >= 0) { 203 insert(bNearA[iB], iB, b[iB]); 204 } 205 } 206 } 207 } 208 } 209 cleanUpParallelLines(!unparallel); 210 SkASSERT(fUsed <= 2); 211 return fUsed; 212 } 213 214 static int horizontal_coincident(const SkDLine& line, double y) { 215 double min = line[0].fY; 216 double max = line[1].fY; 217 if (min > max) { 218 SkTSwap(min, max); 219 } 220 if (min > y || max < y) { 221 return 0; 222 } 223 if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) { 224 return 2; 225 } 226 return 1; 227 } 228 229 static double horizontal_intercept(const SkDLine& line, double y) { 230 return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY)); 231 } 232 233 int SkIntersections::horizontal(const SkDLine& line, double y) { 234 fMax = 2; 235 int horizontalType = horizontal_coincident(line, y); 236 if (horizontalType == 1) { 237 fT[0][0] = horizontal_intercept(line, y); 238 } else if (horizontalType == 2) { 239 fT[0][0] = 0; 240 fT[0][1] = 1; 241 } 242 return fUsed = horizontalType; 243 } 244 245 int SkIntersections::horizontal(const SkDLine& line, double left, double right, 246 double y, bool flipped) { 247 fMax = 3; // clean up parallel at the end will limit the result to 2 at the most 248 // see if end points intersect the opposite line 249 double t; 250 const SkDPoint leftPt = { left, y }; 251 if ((t = line.exactPoint(leftPt)) >= 0) { 252 insert(t, (double) flipped, leftPt); 253 } 254 if (left != right) { 255 const SkDPoint rightPt = { right, y }; 256 if ((t = line.exactPoint(rightPt)) >= 0) { 257 insert(t, (double) !flipped, rightPt); 258 } 259 for (int index = 0; index < 2; ++index) { 260 if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) { 261 insert((double) index, flipped ? 1 - t : t, line[index]); 262 } 263 } 264 } 265 int result = horizontal_coincident(line, y); 266 if (result == 1 && fUsed == 0) { 267 fT[0][0] = horizontal_intercept(line, y); 268 double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); 269 if (between(left, xIntercept, right)) { 270 fT[1][0] = (xIntercept - left) / (right - left); 271 if (flipped) { 272 // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX 273 for (int index = 0; index < result; ++index) { 274 fT[1][index] = 1 - fT[1][index]; 275 } 276 } 277 fPt[0].fX = xIntercept; 278 fPt[0].fY = y; 279 fUsed = 1; 280 } 281 } 282 if (fAllowNear || result == 2) { 283 if ((t = line.nearPoint(leftPt, NULL)) >= 0) { 284 insert(t, (double) flipped, leftPt); 285 } 286 if (left != right) { 287 const SkDPoint rightPt = { right, y }; 288 if ((t = line.nearPoint(rightPt, NULL)) >= 0) { 289 insert(t, (double) !flipped, rightPt); 290 } 291 for (int index = 0; index < 2; ++index) { 292 if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) { 293 insert((double) index, flipped ? 1 - t : t, line[index]); 294 } 295 } 296 } 297 } 298 cleanUpParallelLines(result == 2); 299 return fUsed; 300 } 301 302 static int vertical_coincident(const SkDLine& line, double x) { 303 double min = line[0].fX; 304 double max = line[1].fX; 305 if (min > max) { 306 SkTSwap(min, max); 307 } 308 if (!precisely_between(min, x, max)) { 309 return 0; 310 } 311 if (AlmostEqualUlps(min, max)) { 312 return 2; 313 } 314 return 1; 315 } 316 317 static double vertical_intercept(const SkDLine& line, double x) { 318 return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX)); 319 } 320 321 int SkIntersections::vertical(const SkDLine& line, double x) { 322 fMax = 2; 323 int verticalType = vertical_coincident(line, x); 324 if (verticalType == 1) { 325 fT[0][0] = vertical_intercept(line, x); 326 } else if (verticalType == 2) { 327 fT[0][0] = 0; 328 fT[0][1] = 1; 329 } 330 return fUsed = verticalType; 331 } 332 333 int SkIntersections::vertical(const SkDLine& line, double top, double bottom, 334 double x, bool flipped) { 335 fMax = 3; // cleanup parallel lines will bring this back line 336 // see if end points intersect the opposite line 337 double t; 338 SkDPoint topPt = { x, top }; 339 if ((t = line.exactPoint(topPt)) >= 0) { 340 insert(t, (double) flipped, topPt); 341 } 342 if (top != bottom) { 343 SkDPoint bottomPt = { x, bottom }; 344 if ((t = line.exactPoint(bottomPt)) >= 0) { 345 insert(t, (double) !flipped, bottomPt); 346 } 347 for (int index = 0; index < 2; ++index) { 348 if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) { 349 insert((double) index, flipped ? 1 - t : t, line[index]); 350 } 351 } 352 } 353 int result = vertical_coincident(line, x); 354 if (result == 1 && fUsed == 0) { 355 fT[0][0] = vertical_intercept(line, x); 356 double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); 357 if (between(top, yIntercept, bottom)) { 358 fT[1][0] = (yIntercept - top) / (bottom - top); 359 if (flipped) { 360 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY 361 for (int index = 0; index < result; ++index) { 362 fT[1][index] = 1 - fT[1][index]; 363 } 364 } 365 fPt[0].fX = x; 366 fPt[0].fY = yIntercept; 367 fUsed = 1; 368 } 369 } 370 if (fAllowNear || result == 2) { 371 if ((t = line.nearPoint(topPt, NULL)) >= 0) { 372 insert(t, (double) flipped, topPt); 373 } 374 if (top != bottom) { 375 SkDPoint bottomPt = { x, bottom }; 376 if ((t = line.nearPoint(bottomPt, NULL)) >= 0) { 377 insert(t, (double) !flipped, bottomPt); 378 } 379 for (int index = 0; index < 2; ++index) { 380 if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) { 381 insert((double) index, flipped ? 1 - t : t, line[index]); 382 } 383 } 384 } 385 } 386 cleanUpParallelLines(result == 2); 387 SkASSERT(fUsed <= 2); 388 return fUsed; 389 } 390 391 // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py 392 // 4 subs, 2 muls, 1 cmp 393 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { 394 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); 395 } 396 397 // 16 subs, 8 muls, 6 cmps 398 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { 399 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) 400 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); 401 } 402
