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
9SkDLine 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));
38double 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
44SkDPoint 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
56double 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
66double 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
97bool 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
115bool 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
126double 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
138double 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
161double 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
173double 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