2 * Copyright 2012 Google Inc.
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
7 #include "SkPathOpsLine.h"
9 SkDLine SkDLine::subDivide(double t1, double t2) const {
10 SkDVector delta = tangent();
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}}};
17 // may have this below somewhere else already:
18 // copying here because I thought it was clever
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.
27 // Assume that a class is already given for the object:
28 // Point with coordinates {float x, y;}
29 //===================================================================
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];
44 SkDPoint SkDLine::ptAtT(double t) const {
52 SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
56 double SkDLine::exactPoint(const SkDPoint& xy) const {
57 if (xy == fPts[0]) { // do cheapest test first
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)) {
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)) {
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?
90 *unequal = (float) largest != (float) (largest + dist);
92 t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3
93 SkASSERT(between(0, t, 1));
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?
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);
123 return line.nearRay(pt);
126 double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
131 if (xy.fX == right) {
138 double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
139 if (!AlmostBequalUlps(xy.fY, y)) {
142 if (!AlmostBetweenUlps(left, xy.fX, right)) {
145 double t = (xy.fX - left) / (right - left);
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?
161 double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
166 if (xy.fY == bottom) {
173 double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
174 if (!AlmostBequalUlps(xy.fX, x)) {
177 if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
180 double t = (xy.fY - top) / (bottom - top);
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?