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 numerA /= denom; 80 numerB /= denom; 81 int used; 82 if (!approximately_zero(denom)) { 83 fT[0][0] = numerA; 84 fT[1][0] = numerB; 85 used = 1; 86 } else { 87 /* See if the axis intercepts match: 88 ay - ax * ayLen / axLen == by - bx * ayLen / axLen 89 axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen) 90 axLen * ay - ax * ayLen == axLen * by - bx * ayLen 91 */ 92 if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX, 93 aLen.fX * b[0].fY - aLen.fY * b[0].fX)) { 94 return fUsed = 0; 95 } 96 // there's no great answer for intersection points for coincident rays, but return something 97 fT[0][0] = fT[1][0] = 0; 98 fT[1][0] = fT[1][1] = 1; 99 used = 2; 100 } 101 computePoints(a, used); 102 return fUsed; 103 } 104 105 // note that this only works if both lines are neither horizontal nor vertical 106 int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) { 107 fMax = 3; // note that we clean up so that there is no more than two in the end 108 // see if end points intersect the opposite line 109 double t; 110 for (int iA = 0; iA < 2; ++iA) { 111 if ((t = b.exactPoint(a[iA])) >= 0) { 112 insert(iA, t, a[iA]); 113 } 114 } 115 for (int iB = 0; iB < 2; ++iB) { 116 if ((t = a.exactPoint(b[iB])) >= 0) { 117 insert(t, iB, b[iB]); 118 } 119 } 120 /* Determine the intersection point of two line segments 121 Return FALSE if the lines don't intersect 122 from: http://paulbourke.net/geometry/lineline2d/ */ 123 double axLen = a[1].fX - a[0].fX; 124 double ayLen = a[1].fY - a[0].fY; 125 double bxLen = b[1].fX - b[0].fX; 126 double byLen = b[1].fY - b[0].fY; 127 /* Slopes match when denom goes to zero: 128 axLen / ayLen == bxLen / byLen 129 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen 130 byLen * axLen == ayLen * bxLen 131 byLen * axLen - ayLen * bxLen == 0 ( == denom ) 132 */ 133 double axByLen = axLen * byLen; 134 double ayBxLen = ayLen * bxLen; 135 // detect parallel lines the same way here and in SkOpAngle operator < 136 // so that non-parallel means they are also sortable 137 bool unparallel = fAllowNear ? NotAlmostEqualUlps(axByLen, ayBxLen) 138 : NotAlmostDequalUlps(axByLen, ayBxLen); 139 if (unparallel && fUsed == 0) { 140 double ab0y = a[0].fY - b[0].fY; 141 double ab0x = a[0].fX - b[0].fX; 142 double numerA = ab0y * bxLen - byLen * ab0x; 143 double numerB = ab0y * axLen - ayLen * ab0x; 144 double denom = axByLen - ayBxLen; 145 if (between(0, numerA, denom) && between(0, numerB, denom)) { 146 fT[0][0] = numerA / denom; 147 fT[1][0] = numerB / denom; 148 computePoints(a, 1); 149 } 150 } 151 if (fAllowNear || !unparallel) { 152 for (int iA = 0; iA < 2; ++iA) { 153 if ((t = b.nearPoint(a[iA])) >= 0) { 154 insert(iA, t, a[iA]); 155 } 156 } 157 for (int iB = 0; iB < 2; ++iB) { 158 if ((t = a.nearPoint(b[iB])) >= 0) { 159 insert(t, iB, b[iB]); 160 } 161 } 162 } 163 cleanUpParallelLines(!unparallel); 164 SkASSERT(fUsed <= 2); 165 return fUsed; 166 } 167 168 static int horizontal_coincident(const SkDLine& line, double y) { 169 double min = line[0].fY; 170 double max = line[1].fY; 171 if (min > max) { 172 SkTSwap(min, max); 173 } 174 if (min > y || max < y) { 175 return 0; 176 } 177 if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) { 178 return 2; 179 } 180 return 1; 181 } 182 183 static double horizontal_intercept(const SkDLine& line, double y) { 184 return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY)); 185 } 186 187 int SkIntersections::horizontal(const SkDLine& line, double y) { 188 fMax = 2; 189 int horizontalType = horizontal_coincident(line, y); 190 if (horizontalType == 1) { 191 fT[0][0] = horizontal_intercept(line, y); 192 } else if (horizontalType == 2) { 193 fT[0][0] = 0; 194 fT[0][1] = 1; 195 } 196 return fUsed = horizontalType; 197 } 198 199 int SkIntersections::horizontal(const SkDLine& line, double left, double right, 200 double y, bool flipped) { 201 fMax = 2; 202 // see if end points intersect the opposite line 203 double t; 204 const SkDPoint leftPt = { left, y }; 205 if ((t = line.exactPoint(leftPt)) >= 0) { 206 insert(t, (double) flipped, leftPt); 207 } 208 if (left != right) { 209 const SkDPoint rightPt = { right, y }; 210 if ((t = line.exactPoint(rightPt)) >= 0) { 211 insert(t, (double) !flipped, rightPt); 212 } 213 for (int index = 0; index < 2; ++index) { 214 if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) { 215 insert((double) index, flipped ? 1 - t : t, line[index]); 216 } 217 } 218 } 219 int result = horizontal_coincident(line, y); 220 if (result == 1 && fUsed == 0) { 221 fT[0][0] = horizontal_intercept(line, y); 222 double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX); 223 if (between(left, xIntercept, right)) { 224 fT[1][0] = (xIntercept - left) / (right - left); 225 if (flipped) { 226 // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX 227 for (int index = 0; index < result; ++index) { 228 fT[1][index] = 1 - fT[1][index]; 229 } 230 } 231 fPt[0].fX = xIntercept; 232 fPt[0].fY = y; 233 fUsed = 1; 234 } 235 } 236 if (fAllowNear || result == 2) { 237 if ((t = line.nearPoint(leftPt)) >= 0) { 238 insert(t, (double) flipped, leftPt); 239 } 240 if (left != right) { 241 const SkDPoint rightPt = { right, y }; 242 if ((t = line.nearPoint(rightPt)) >= 0) { 243 insert(t, (double) !flipped, rightPt); 244 } 245 for (int index = 0; index < 2; ++index) { 246 if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) { 247 insert((double) index, flipped ? 1 - t : t, line[index]); 248 } 249 } 250 } 251 } 252 cleanUpParallelLines(result == 2); 253 return fUsed; 254 } 255 256 static int vertical_coincident(const SkDLine& line, double x) { 257 double min = line[0].fX; 258 double max = line[1].fX; 259 if (min > max) { 260 SkTSwap(min, max); 261 } 262 if (!precisely_between(min, x, max)) { 263 return 0; 264 } 265 if (AlmostEqualUlps(min, max)) { 266 return 2; 267 } 268 return 1; 269 } 270 271 static double vertical_intercept(const SkDLine& line, double x) { 272 return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX)); 273 } 274 275 int SkIntersections::vertical(const SkDLine& line, double x) { 276 fMax = 2; 277 int verticalType = vertical_coincident(line, x); 278 if (verticalType == 1) { 279 fT[0][0] = vertical_intercept(line, x); 280 } else if (verticalType == 2) { 281 fT[0][0] = 0; 282 fT[0][1] = 1; 283 } 284 return fUsed = verticalType; 285 } 286 287 int SkIntersections::vertical(const SkDLine& line, double top, double bottom, 288 double x, bool flipped) { 289 fMax = 2; 290 // see if end points intersect the opposite line 291 double t; 292 SkDPoint topPt = { x, top }; 293 if ((t = line.exactPoint(topPt)) >= 0) { 294 insert(t, (double) flipped, topPt); 295 } 296 if (top != bottom) { 297 SkDPoint bottomPt = { x, bottom }; 298 if ((t = line.exactPoint(bottomPt)) >= 0) { 299 insert(t, (double) !flipped, bottomPt); 300 } 301 for (int index = 0; index < 2; ++index) { 302 if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) { 303 insert((double) index, flipped ? 1 - t : t, line[index]); 304 } 305 } 306 } 307 int result = vertical_coincident(line, x); 308 if (result == 1 && fUsed == 0) { 309 fT[0][0] = vertical_intercept(line, x); 310 double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY); 311 if (between(top, yIntercept, bottom)) { 312 fT[1][0] = (yIntercept - top) / (bottom - top); 313 if (flipped) { 314 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY 315 for (int index = 0; index < result; ++index) { 316 fT[1][index] = 1 - fT[1][index]; 317 } 318 } 319 fPt[0].fX = x; 320 fPt[0].fY = yIntercept; 321 fUsed = 1; 322 } 323 } 324 if (fAllowNear || result == 2) { 325 if ((t = line.nearPoint(topPt)) >= 0) { 326 insert(t, (double) flipped, topPt); 327 } 328 if (top != bottom) { 329 SkDPoint bottomPt = { x, bottom }; 330 if ((t = line.nearPoint(bottomPt)) >= 0) { 331 insert(t, (double) !flipped, bottomPt); 332 } 333 for (int index = 0; index < 2; ++index) { 334 if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) { 335 insert((double) index, flipped ? 1 - t : t, line[index]); 336 } 337 } 338 } 339 } 340 cleanUpParallelLines(result == 2); 341 return fUsed; 342 } 343 344 // from http://www.bryceboe.com/wordpress/wp-content/uploads/2006/10/intersect.py 345 // 4 subs, 2 muls, 1 cmp 346 static bool ccw(const SkDPoint& A, const SkDPoint& B, const SkDPoint& C) { 347 return (C.fY - A.fY) * (B.fX - A.fX) > (B.fY - A.fY) * (C.fX - A.fX); 348 } 349 350 // 16 subs, 8 muls, 6 cmps 351 bool SkIntersections::Test(const SkDLine& a, const SkDLine& b) { 352 return ccw(a[0], b[0], b[1]) != ccw(a[1], b[0], b[1]) 353 && ccw(a[0], a[1], b[0]) != ccw(a[0], a[1], b[1]); 354 } 355
