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