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 "src/pathops/SkIntersections.h"
8#include "src/pathops/SkPathOpsLine.h"
9
10#include <utility>
11
12void SkIntersections::cleanUpParallelLines(bool parallel) {
13 while (fUsed > 2) {
14 removeOne(1);
15 }
16 if (fUsed == 2 && !parallel) {
17 bool startMatch = fT[0][0] == 0 || zero_or_one(fT[1][0]);
18 bool endMatch = fT[0][1] == 1 || zero_or_one(fT[1][1]);
19 if ((!startMatch && !endMatch) || approximately_equal(fT[0][0], fT[0][1])) {
20 SkASSERT(startMatch || endMatch);
21 if (startMatch && endMatch && (fT[0][0] != 0 || !zero_or_one(fT[1][0]))
22 && fT[0][1] == 1 && zero_or_one(fT[1][1])) {
23 removeOne(0);
24 } else {
25 removeOne(endMatch);
26 }
27 }
28 }
29 if (fUsed == 2) {
30 fIsCoincident[0] = fIsCoincident[1] = 0x03;
31 }
32}
33
34void SkIntersections::computePoints(const SkDLine& line, int used) {
35 fPt[0] = line.ptAtT(fT[0][0]);
36 if ((fUsed = used) == 2) {
37 fPt[1] = line.ptAtT(fT[0][1]);
38 }
39}
40
41int SkIntersections::intersectRay(const SkDLine& a, const SkDLine& b) {
42 fMax = 2;
43 SkDVector aLen = a[1] - a[0];
44 SkDVector bLen = b[1] - b[0];
45 /* Slopes match when denom goes to zero:
46 axLen / ayLen == bxLen / byLen
47 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
48 byLen * axLen == ayLen * bxLen
49 byLen * axLen - ayLen * bxLen == 0 ( == denom )
50 */
51 double denom = bLen.fY * aLen.fX - aLen.fY * bLen.fX;
52 int used;
53 if (!approximately_zero(denom)) {
54 SkDVector ab0 = a[0] - b[0];
55 double numerA = ab0.fY * bLen.fX - bLen.fY * ab0.fX;
56 double numerB = ab0.fY * aLen.fX - aLen.fY * ab0.fX;
57 numerA /= denom;
58 numerB /= denom;
59 fT[0][0] = numerA;
60 fT[1][0] = numerB;
61 used = 1;
62 } else {
63 /* See if the axis intercepts match:
64 ay - ax * ayLen / axLen == by - bx * ayLen / axLen
65 axLen * (ay - ax * ayLen / axLen) == axLen * (by - bx * ayLen / axLen)
66 axLen * ay - ax * ayLen == axLen * by - bx * ayLen
67 */
68 if (!AlmostEqualUlps(aLen.fX * a[0].fY - aLen.fY * a[0].fX,
69 aLen.fX * b[0].fY - aLen.fY * b[0].fX)) {
70 return fUsed = 0;
71 }
72 // there's no great answer for intersection points for coincident rays, but return something
73 fT[0][0] = fT[1][0] = 0;
74 fT[1][0] = fT[1][1] = 1;
75 used = 2;
76 }
77 computePoints(a, used);
78 return fUsed;
79}
80
81// note that this only works if both lines are neither horizontal nor vertical
82int SkIntersections::intersect(const SkDLine& a, const SkDLine& b) {
83 fMax = 3; // note that we clean up so that there is no more than two in the end
84 // see if end points intersect the opposite line
85 double t;
86 for (int iA = 0; iA < 2; ++iA) {
87 if ((t = b.exactPoint(a[iA])) >= 0) {
88 insert(iA, t, a[iA]);
89 }
90 }
91 for (int iB = 0; iB < 2; ++iB) {
92 if ((t = a.exactPoint(b[iB])) >= 0) {
93 insert(t, iB, b[iB]);
94 }
95 }
96 /* Determine the intersection point of two line segments
97 Return FALSE if the lines don't intersect
98 from: http://paulbourke.net/geometry/lineline2d/ */
99 double axLen = a[1].fX - a[0].fX;
100 double ayLen = a[1].fY - a[0].fY;
101 double bxLen = b[1].fX - b[0].fX;
102 double byLen = b[1].fY - b[0].fY;
103 /* Slopes match when denom goes to zero:
104 axLen / ayLen == bxLen / byLen
105 (ayLen * byLen) * axLen / ayLen == (ayLen * byLen) * bxLen / byLen
106 byLen * axLen == ayLen * bxLen
107 byLen * axLen - ayLen * bxLen == 0 ( == denom )
108 */
109 double axByLen = axLen * byLen;
110 double ayBxLen = ayLen * bxLen;
111 // detect parallel lines the same way here and in SkOpAngle operator <
112 // so that non-parallel means they are also sortable
113 bool unparallel = fAllowNear ? NotAlmostEqualUlps_Pin(axByLen, ayBxLen)
114 : NotAlmostDequalUlps(axByLen, ayBxLen);
115 if (unparallel && fUsed == 0) {
116 double ab0y = a[0].fY - b[0].fY;
117 double ab0x = a[0].fX - b[0].fX;
118 double numerA = ab0y * bxLen - byLen * ab0x;
119 double numerB = ab0y * axLen - ayLen * ab0x;
120 double denom = axByLen - ayBxLen;
121 if (between(0, numerA, denom) && between(0, numerB, denom)) {
122 fT[0][0] = numerA / denom;
123 fT[1][0] = numerB / denom;
124 computePoints(a, 1);
125 }
126 }
127/* Allow tracking that both sets of end points are near each other -- the lines are entirely
128 coincident -- even when the end points are not exactly the same.
129 Mark this as a 'wild card' for the end points, so that either point is considered totally
130 coincident. Then, avoid folding the lines over each other, but allow either end to mate
131 to the next set of lines.
132 */
133 if (fAllowNear || !unparallel) {
134 double aNearB[2];
135 double bNearA[2];
136 bool aNotB[2] = {false, false};
137 bool bNotA[2] = {false, false};
138 int nearCount = 0;
139 for (int index = 0; index < 2; ++index) {
140 aNearB[index] = t = b.nearPoint(a[index], &aNotB[index]);
141 nearCount += t >= 0;
142 bNearA[index] = t = a.nearPoint(b[index], &bNotA[index]);
143 nearCount += t >= 0;
144 }
145 if (nearCount > 0) {
146 // Skip if each segment contributes to one end point.
147 if (nearCount != 2 || aNotB[0] == aNotB[1]) {
148 for (int iA = 0; iA < 2; ++iA) {
149 if (!aNotB[iA]) {
150 continue;
151 }
152 int nearer = aNearB[iA] > 0.5;
153 if (!bNotA[nearer]) {
154 continue;
155 }
156 SkASSERT(a[iA] != b[nearer]);
157 SkOPASSERT(iA == (bNearA[nearer] > 0.5));
158 insertNear(iA, nearer, a[iA], b[nearer]);
159 aNearB[iA] = -1;
160 bNearA[nearer] = -1;
161 nearCount -= 2;
162 }
163 }
164 if (nearCount > 0) {
165 for (int iA = 0; iA < 2; ++iA) {
166 if (aNearB[iA] >= 0) {
167 insert(iA, aNearB[iA], a[iA]);
168 }
169 }
170 for (int iB = 0; iB < 2; ++iB) {
171 if (bNearA[iB] >= 0) {
172 insert(bNearA[iB], iB, b[iB]);
173 }
174 }
175 }
176 }
177 }
178 cleanUpParallelLines(!unparallel);
179 SkASSERT(fUsed <= 2);
180 return fUsed;
181}
182
183static int horizontal_coincident(const SkDLine& line, double y) {
184 double min = line[0].fY;
185 double max = line[1].fY;
186 if (min > max) {
187 using std::swap;
188 swap(min, max);
189 }
190 if (min > y || max < y) {
191 return 0;
192 }
193 if (AlmostEqualUlps(min, max) && max - min < fabs(line[0].fX - line[1].fX)) {
194 return 2;
195 }
196 return 1;
197}
198
199double SkIntersections::HorizontalIntercept(const SkDLine& line, double y) {
200 SkASSERT(line[1].fY != line[0].fY);
201 return SkPinT((y - line[0].fY) / (line[1].fY - line[0].fY));
202}
203
204int SkIntersections::horizontal(const SkDLine& line, double left, double right,
205 double y, bool flipped) {
206 fMax = 3; // clean up parallel at the end will limit the result to 2 at the most
207 // see if end points intersect the opposite line
208 double t;
209 const SkDPoint leftPt = { left, y };
210 if ((t = line.exactPoint(leftPt)) >= 0) {
211 insert(t, (double) flipped, leftPt);
212 }
213 if (left != right) {
214 const SkDPoint rightPt = { right, y };
215 if ((t = line.exactPoint(rightPt)) >= 0) {
216 insert(t, (double) !flipped, rightPt);
217 }
218 for (int index = 0; index < 2; ++index) {
219 if ((t = SkDLine::ExactPointH(line[index], left, right, y)) >= 0) {
220 insert((double) index, flipped ? 1 - t : t, line[index]);
221 }
222 }
223 }
224 int result = horizontal_coincident(line, y);
225 if (result == 1 && fUsed == 0) {
226 fT[0][0] = HorizontalIntercept(line, y);
227 double xIntercept = line[0].fX + fT[0][0] * (line[1].fX - line[0].fX);
228 if (between(left, xIntercept, right)) {
229 fT[1][0] = (xIntercept - left) / (right - left);
230 if (flipped) {
231 // OPTIMIZATION: ? instead of swapping, pass original line, use [1].fX - [0].fX
232 for (int index = 0; index < result; ++index) {
233 fT[1][index] = 1 - fT[1][index];
234 }
235 }
236 fPt[0].fX = xIntercept;
237 fPt[0].fY = y;
238 fUsed = 1;
239 }
240 }
241 if (fAllowNear || result == 2) {
242 if ((t = line.nearPoint(leftPt, nullptr)) >= 0) {
243 insert(t, (double) flipped, leftPt);
244 }
245 if (left != right) {
246 const SkDPoint rightPt = { right, y };
247 if ((t = line.nearPoint(rightPt, nullptr)) >= 0) {
248 insert(t, (double) !flipped, rightPt);
249 }
250 for (int index = 0; index < 2; ++index) {
251 if ((t = SkDLine::NearPointH(line[index], left, right, y)) >= 0) {
252 insert((double) index, flipped ? 1 - t : t, line[index]);
253 }
254 }
255 }
256 }
257 cleanUpParallelLines(result == 2);
258 return fUsed;
259}
260
261static int vertical_coincident(const SkDLine& line, double x) {
262 double min = line[0].fX;
263 double max = line[1].fX;
264 if (min > max) {
265 using std::swap;
266 swap(min, max);
267 }
268 if (!precisely_between(min, x, max)) {
269 return 0;
270 }
271 if (AlmostEqualUlps(min, max)) {
272 return 2;
273 }
274 return 1;
275}
276
277double SkIntersections::VerticalIntercept(const SkDLine& line, double x) {
278 SkASSERT(line[1].fX != line[0].fX);
279 return SkPinT((x - line[0].fX) / (line[1].fX - line[0].fX));
280}
281
282int SkIntersections::vertical(const SkDLine& line, double top, double bottom,
283 double x, bool flipped) {
284 fMax = 3; // cleanup parallel lines will bring this back line
285 // see if end points intersect the opposite line
286 double t;
287 SkDPoint topPt = { x, top };
288 if ((t = line.exactPoint(topPt)) >= 0) {
289 insert(t, (double) flipped, topPt);
290 }
291 if (top != bottom) {
292 SkDPoint bottomPt = { x, bottom };
293 if ((t = line.exactPoint(bottomPt)) >= 0) {
294 insert(t, (double) !flipped, bottomPt);
295 }
296 for (int index = 0; index < 2; ++index) {
297 if ((t = SkDLine::ExactPointV(line[index], top, bottom, x)) >= 0) {
298 insert((double) index, flipped ? 1 - t : t, line[index]);
299 }
300 }
301 }
302 int result = vertical_coincident(line, x);
303 if (result == 1 && fUsed == 0) {
304 fT[0][0] = VerticalIntercept(line, x);
305 double yIntercept = line[0].fY + fT[0][0] * (line[1].fY - line[0].fY);
306 if (between(top, yIntercept, bottom)) {
307 fT[1][0] = (yIntercept - top) / (bottom - top);
308 if (flipped) {
309 // OPTIMIZATION: instead of swapping, pass original line, use [1].fY - [0].fY
310 for (int index = 0; index < result; ++index) {
311 fT[1][index] = 1 - fT[1][index];
312 }
313 }
314 fPt[0].fX = x;
315 fPt[0].fY = yIntercept;
316 fUsed = 1;
317 }
318 }
319 if (fAllowNear || result == 2) {
320 if ((t = line.nearPoint(topPt, nullptr)) >= 0) {
321 insert(t, (double) flipped, topPt);
322 }
323 if (top != bottom) {
324 SkDPoint bottomPt = { x, bottom };
325 if ((t = line.nearPoint(bottomPt, nullptr)) >= 0) {
326 insert(t, (double) !flipped, bottomPt);
327 }
328 for (int index = 0; index < 2; ++index) {
329 if ((t = SkDLine::NearPointV(line[index], top, bottom, x)) >= 0) {
330 insert((double) index, flipped ? 1 - t : t, line[index]);
331 }
332 }
333 }
334 }
335 cleanUpParallelLines(result == 2);
336 SkASSERT(fUsed <= 2);
337 return fUsed;
338}
339
340