Line data Source code
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 0 : SkDPoint SkDLine::ptAtT(double t) const {
10 0 : if (0 == t) {
11 0 : return fPts[0];
12 : }
13 0 : if (1 == t) {
14 0 : return fPts[1];
15 : }
16 0 : double one_t = 1 - t;
17 0 : SkDPoint result = { one_t * fPts[0].fX + t * fPts[1].fX, one_t * fPts[0].fY + t * fPts[1].fY };
18 0 : return result;
19 : }
20 :
21 0 : double SkDLine::exactPoint(const SkDPoint& xy) const {
22 0 : if (xy == fPts[0]) { // do cheapest test first
23 0 : return 0;
24 : }
25 0 : if (xy == fPts[1]) {
26 0 : return 1;
27 : }
28 0 : return -1;
29 : }
30 :
31 0 : double SkDLine::nearPoint(const SkDPoint& xy, bool* unequal) const {
32 0 : if (!AlmostBetweenUlps(fPts[0].fX, xy.fX, fPts[1].fX)
33 0 : || !AlmostBetweenUlps(fPts[0].fY, xy.fY, fPts[1].fY)) {
34 0 : return -1;
35 : }
36 : // project a perpendicular ray from the point to the line; find the T on the line
37 0 : SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
38 0 : double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
39 0 : SkDVector ab0 = xy - fPts[0];
40 0 : double numer = len.fX * ab0.fX + ab0.fY * len.fY;
41 0 : if (!between(0, numer, denom)) {
42 0 : return -1;
43 : }
44 0 : if (!denom) {
45 0 : return 0;
46 : }
47 0 : double t = numer / denom;
48 0 : SkDPoint realPt = ptAtT(t);
49 0 : double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
50 : // find the ordinal in the original line with the largest unsigned exponent
51 0 : double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
52 0 : double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
53 0 : largest = SkTMax(largest, -tiniest);
54 0 : if (!AlmostEqualUlps_Pin(largest, largest + dist)) { // is the dist within ULPS tolerance?
55 0 : return -1;
56 : }
57 0 : if (unequal) {
58 0 : *unequal = (float) largest != (float) (largest + dist);
59 : }
60 0 : t = SkPinT(t); // a looser pin breaks skpwww_lptemp_com_3
61 0 : SkASSERT(between(0, t, 1));
62 0 : return t;
63 : }
64 :
65 0 : bool SkDLine::nearRay(const SkDPoint& xy) const {
66 : // project a perpendicular ray from the point to the line; find the T on the line
67 0 : SkDVector len = fPts[1] - fPts[0]; // the x/y magnitudes of the line
68 0 : double denom = len.fX * len.fX + len.fY * len.fY; // see DLine intersectRay
69 0 : SkDVector ab0 = xy - fPts[0];
70 0 : double numer = len.fX * ab0.fX + ab0.fY * len.fY;
71 0 : double t = numer / denom;
72 0 : SkDPoint realPt = ptAtT(t);
73 0 : double dist = realPt.distance(xy); // OPTIMIZATION: can we compare against distSq instead ?
74 : // find the ordinal in the original line with the largest unsigned exponent
75 0 : double tiniest = SkTMin(SkTMin(SkTMin(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
76 0 : double largest = SkTMax(SkTMax(SkTMax(fPts[0].fX, fPts[0].fY), fPts[1].fX), fPts[1].fY);
77 0 : largest = SkTMax(largest, -tiniest);
78 0 : return RoughlyEqualUlps(largest, largest + dist); // is the dist within ULPS tolerance?
79 : }
80 :
81 0 : double SkDLine::ExactPointH(const SkDPoint& xy, double left, double right, double y) {
82 0 : if (xy.fY == y) {
83 0 : if (xy.fX == left) {
84 0 : return 0;
85 : }
86 0 : if (xy.fX == right) {
87 0 : return 1;
88 : }
89 : }
90 0 : return -1;
91 : }
92 :
93 0 : double SkDLine::NearPointH(const SkDPoint& xy, double left, double right, double y) {
94 0 : if (!AlmostBequalUlps(xy.fY, y)) {
95 0 : return -1;
96 : }
97 0 : if (!AlmostBetweenUlps(left, xy.fX, right)) {
98 0 : return -1;
99 : }
100 0 : double t = (xy.fX - left) / (right - left);
101 0 : t = SkPinT(t);
102 0 : SkASSERT(between(0, t, 1));
103 0 : double realPtX = (1 - t) * left + t * right;
104 0 : SkDVector distU = {xy.fY - y, xy.fX - realPtX};
105 0 : double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
106 0 : double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
107 0 : double tiniest = SkTMin(SkTMin(y, left), right);
108 0 : double largest = SkTMax(SkTMax(y, left), right);
109 0 : largest = SkTMax(largest, -tiniest);
110 0 : if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
111 0 : return -1;
112 : }
113 0 : return t;
114 : }
115 :
116 0 : double SkDLine::ExactPointV(const SkDPoint& xy, double top, double bottom, double x) {
117 0 : if (xy.fX == x) {
118 0 : if (xy.fY == top) {
119 0 : return 0;
120 : }
121 0 : if (xy.fY == bottom) {
122 0 : return 1;
123 : }
124 : }
125 0 : return -1;
126 : }
127 :
128 0 : double SkDLine::NearPointV(const SkDPoint& xy, double top, double bottom, double x) {
129 0 : if (!AlmostBequalUlps(xy.fX, x)) {
130 0 : return -1;
131 : }
132 0 : if (!AlmostBetweenUlps(top, xy.fY, bottom)) {
133 0 : return -1;
134 : }
135 0 : double t = (xy.fY - top) / (bottom - top);
136 0 : t = SkPinT(t);
137 0 : SkASSERT(between(0, t, 1));
138 0 : double realPtY = (1 - t) * top + t * bottom;
139 0 : SkDVector distU = {xy.fX - x, xy.fY - realPtY};
140 0 : double distSq = distU.fX * distU.fX + distU.fY * distU.fY;
141 0 : double dist = sqrt(distSq); // OPTIMIZATION: can we compare against distSq instead ?
142 0 : double tiniest = SkTMin(SkTMin(x, top), bottom);
143 0 : double largest = SkTMax(SkTMax(x, top), bottom);
144 0 : largest = SkTMax(largest, -tiniest);
145 0 : if (!AlmostEqualUlps(largest, largest + dist)) { // is the dist within ULPS tolerance?
146 0 : return -1;
147 : }
148 0 : return t;
149 : }
|
