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));
31double 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
37SkDPoint 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
49double 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
59double 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
90bool 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
106double 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
118double 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
141double 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
153double 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