Home | History | Annotate | Download | only in pathops 
      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, bool* unequal) 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     if (unequal) {
     90         *unequal = (float) largest != (float) (largest + dist);
     91     }
     92     t = SkPinT(t);  // a looser pin breaks skpwww_lptemp_com_3
     93     SkASSERT(between(0, t, 1));
     94     return t;
     95 }
     96 
     97 bool SkDLine::nearRay(const SkDPoint& xy) const {
     98     // project a perpendicular ray from the point to the line; find the T on the line
     99     SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
    100     double denom = len.fX * len.fX + len.fY * len.fY;  // see DLine intersectRay
    101     SkDVector ab0 = xy - fPts[0];
    102     double numer = len.fX * ab0.fX + ab0.fY * len.fY;
    103     double t = numer / denom;
    104     SkDPoint realPt = ptAtT(t);
    105     double dist = realPt.distance(xy);   // OPTIMIZATION: can we compare against distSq instead ?
    106     // find the ordinal in the original line with the largest unsigned exponent
    107     double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
    108     double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
    109     largest = SkTMax(largest, -tiniest);
    110     return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
    111 }
    112 
    113 // Returns true if a ray from (0,0) to (x1,y1) is coincident with a ray (0,0) to (x2,y2)
    114 // OPTIMIZE: a specialty routine could speed this up -- may not be called very often though
    115 bool SkDLine::NearRay(double x1, double y1, double x2, double y2) {
    116     double denom1 = x1 * x1 + y1 * y1;
    117     double denom2 = x2 * x2 + y2 * y2;
    118     SkDLine line = {{{0, 0}, {x1, y1}}};
    119     SkDPoint pt = {x2, y2};
    120     if (denom2 > denom1) {
    121         SkTSwap(line[1], pt);
    122     }
    123     return line.nearRay(pt);
    124 }
    125 
    126 double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
    127     if (xy.fY == y) {
    128         if (xy.fX == left) {
    129             return 0;
    130         }
    131         if (xy.fX == right) {
    132             return 1;
    133         }
    134     }
    135     return -1;
    136 }
    137 
    138 double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
    139     if (!AlmostBequalUlps(xy.fY, y)) {
    140         return -1;
    141     }
    142     if (!AlmostBetweenUlps(left, xy.fX, right)) {
    143         return -1;
    144     }
    145     double t = (xy.fX - left) / (right - left);
    146     t = SkPinT(t);
    147     SkASSERT(between(0, t, 1));
    148     double realPtX = (1 - t) * left + t * right;
    149     SkDVector distU = {xy.fY - y, xy.fX - realPtX};
    150     double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
    151     double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
    152     double tiniest = SkTMin(SkTMin(y, left), right);
    153     double largest = SkTMax(SkTMax(y, left), right);
    154     largest = SkTMax(largest, -tiniest);
    155     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
    156         return -1;
    157     }
    158     return t;
    159 }
    160 
    161 double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
    162     if (xy.fX == x) {
    163         if (xy.fY == top) {
    164             return 0;
    165         }
    166         if (xy.fY == bottom) {
    167             return 1;
    168         }
    169     }
    170     return -1;
    171 }
    172 
    173 double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
    174     if (!AlmostBequalUlps(xy.fX, x)) {
    175         return -1;
    176     }
    177     if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
    178         return -1;
    179     }
    180     double t = (xy.fY - top) / (bottom - top);
    181     t = SkPinT(t);
    182     SkASSERT(between(0, t, 1));
    183     double realPtY = (1 - t) * top + t * bottom;
    184     SkDVector distU = {xy.fX - x, xy.fY - realPtY};
    185     double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
    186     double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
    187     double tiniest = SkTMin(SkTMin(x, top), bottom);
    188     double largest = SkTMax(SkTMax(x, top), bottom);
    189     largest = SkTMax(largest, -tiniest);
    190     if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
    191         return -1;
    192     }
    193     return t;
    194 }
    195