src/third_party/skia/src/pathops/SkDLineIntersection.cpp

   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 }