src/third_party/skia/src/pathops/SkPathOpsLine.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 "SkPathOpsLine.h"
   8
   9 SkDLine SkDLine::subDivide(double t1, double t2) const {
  10     SkDVector delta = tangent();
  11     SkDLine dst = {{{
  12             fPts[0].fX - t1 * delta.fX, fPts[0].fY - t1 * delta.fY}, {
  13             fPts[0].fX - t2 * delta.fX, fPts[0].fY - t2 * delta.fY}}};
  14     return dst;
  15 }
  16
  17 // may have this below somewhere else already:
  18 // copying here because I thought it was clever
  19
  20 // Copyright 2001, softSurfer (www.softsurfer.com)
  21 // This code may be freely used and modified for any purpose
  22 // providing that this copyright notice is included with it.
  23 // SoftSurfer makes no warranty for this code, and cannot be held
  24 // liable for any real or imagined damage resulting from its use.
  25 // Users of this code must verify correctness for their application.
  26
  27 // Assume that a class is already given for the object:
  28 //    Point with coordinates {float x, y;}
  29 //===================================================================
  30
  31 // isLeft(): tests if a point is Left|On|Right of an infinite line.
  32 //    Input:  three points P0, P1, and P2
  33 //    Return: >0 for P2 left of the line through P0 and P1
  34 //            =0 for P2 on the line
  35 //            <0 for P2 right of the line
  36 //    See: the January 2001 Algorithm on Area of Triangles
  37 //    return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y));
  38 double SkDLine::isLeft(const SkDPoint& pt) const {
  39     SkDVector p0 = fPts[1] - fPts[0];
  40     SkDVector p2 = pt - fPts[0];
  41     return p0.cross(p2);
  42 }
  43
  44 SkDPoint SkDLine::ptAtT(double t) const {
  45     if (0 == t) {
  46         return fPts[0];
  47     }
  48     if (1 == t) {
  49         return fPts[1];
  50     }
  51     double one_t = 1 - t;
  52     SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
  53     return result;
  54 }
  55
  56 double SkDLine::exactPoint(const SkDPoint& xy) const {
  57     if (xy == fPts[0]) {  // do cheapest test first
  58         return 0;
  59     }
  60     if (xy == fPts[1]) {
  61         return 1;
  62     }
  63     return -1;
  64 }
  65
  66 double SkDLine::nearPoint(const SkDPoint& xy) const {
  67     if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
  68             || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
  69         return -1;
  70     }
  71     // project a perpendicular ray from the point to the line; find the T on the line
  72     SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
  73     double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
  74     SkDVector ab0 = xy - fPts[0];
  75     double numer = len.fX * ab0.fX + ab0.fY * len.fY;
  76     if (!between(0, numer, denom)) {
  77         return -1;
  78     }
  79     double t = numer / denom;
  80     SkDPoint realPt = ptAtT(t);
  81     double dist = realPt.distance(xy);   // OPTIMIZATION: can we compare against distSq instead ?
  82     // find the ordinal in the original line with the largest unsigned exponent
  83     double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
  84     double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
  85     largest = SkTMax(largest, -tiniest);
  86     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
  87         return -1;
  88     }
  89     t = SkPinT(t);
  90     SkASSERT(between(0, t, 1));
  91     return t;
  92 }
  93
  94 bool SkDLine::nearRay(const SkDPoint& xy) const {
  95     // project a perpendicular ray from the point to the line; find the T on the line
  96     SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
  97     double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
  98     SkDVector ab0 = xy - fPts[0];
  99     double numer = len.fX * ab0.fX + ab0.fY * len.fY;
 100     double t = numer / denom;
 101     SkDPoint realPt = ptAtT(t);
 102     double dist = realPt.distance(xy);   // OPTIMIZATION: can we compare against distSq instead ?
 103     // find the ordinal in the original line with the largest unsigned exponent
 104     double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
 105     double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
 106     largest = SkTMax(largest, -tiniest);
 107     return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
 108 }
 109
 110 // Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2)
 111 // OPTIMIZE: a specialty routine could speed this up -- may not be called very often though
 112 bool SkDLine::NearRay(double x1, double y1, double x2, double y2) {
 113     double denom1 = x1 * x1 + y1 * y1;
 114     double denom2 = x2 * x2 + y2 * y2;
 115     SkDLine line = {{{0, 0}, {x1, y1}}};
 116     SkDPoint pt = {x2, y2};
 117     if (denom2 > denom1) {
 118         SkTSwap(line[1], pt);
 119     }
 120     return line.nearRay(pt);
 121 }
 122
 123 double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
 124     if (xy.fY == y) {
 125         if (xy.fX == left) {
 126             return 0;
 127         }
 128         if (xy.fX == right) {
 129             return 1;
 130         }
 131     }
 132     return -1;
 133 }
 134
 135 double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
 136     if (!AlmostBequalUlps(xy.fY, y)) {
 137         return -1;
 138     }
 139     if (!AlmostBetweenUlps(left, xy.fX, right)) {
 140         return -1;
 141     }
 142     double t = (xy.fX - left) / (right - left);
 143     t = SkPinT(t);
 144     SkASSERT(between(0, t, 1));
 145     double realPtX = (1 - t) * left + t * right;
 146     SkDVector distU = {xy.fY - y, xy.fX - realPtX};
 147     double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
 148     double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
 149     double tiniest = SkTMin(SkTMin(y, left), right);
 150     double largest = SkTMax(SkTMax(y, left), right);
 151     largest = SkTMax(largest, -tiniest);
 152     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
 153         return -1;
 154     }
 155     return t;
 156 }
 157
 158 double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
 159     if (xy.fX == x) {
 160         if (xy.fY == top) {
 161             return 0;
 162         }
 163         if (xy.fY == bottom) {
 164             return 1;
 165         }
 166     }
 167     return -1;
 168 }
 169
 170 double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
 171     if (!AlmostBequalUlps(xy.fX, x)) {
 172         return -1;
 173     }
 174     if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
 175         return -1;
 176     }
 177     double t = (xy.fY - top) / (bottom - top);
 178     t = SkPinT(t);
 179     SkASSERT(between(0, t, 1));
 180     double realPtY = (1 - t) * top + t * bottom;
 181     SkDVector distU = {xy.fX - x, xy.fY - realPtY};
 182     double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
 183     double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
 184     double tiniest = SkTMin(SkTMin(x, top), bottom);
 185     double largest = SkTMax(SkTMax(x, top), bottom);
 186     largest = SkTMax(largest, -tiniest);
 187     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
 188         return -1;
 189     }
 190     return t;
 191 }