OLD | NEW |
| (Empty) |
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 "CurveIntersection.h" | |
8 | |
9 /* This rejects coincidence with two muls, two adds, and one cmp. | |
10 Coincident candidates will take another four muls and two adds, but may still | |
11 fail if they don't overlap. (The overlap test isn't performed here.) | |
12 */ | |
13 bool implicit_matches(const _Line& one, const _Line& two) { | |
14 _Point oneD, twoD; | |
15 tangent(one, oneD); | |
16 tangent(two, twoD); | |
17 /* See if the slopes match, i.e. | |
18 dx1 / dy1 == dx2 / dy2 | |
19 (dy1 * dy2) * dx1 / dy1 == (dy1 * dy2) * dx2 / dy2 | |
20 dy2 * dx1 == dy1 * dx2 | |
21 */ | |
22 if (!AlmostEqualUlps(oneD.x * twoD.y, twoD.x * oneD.y)) { | |
23 return false; | |
24 } | |
25 /* See if the axis intercepts match, i.e. | |
26 y0 - x0 * dy / dx == y1 - x1 * dy / dx | |
27 dx * (y0 - x0 * dy / dx) == dx * (y1 - x1 * dy / dx) | |
28 dx * y0 - x0 * dy == dx * y1 - x1 * dy | |
29 */ | |
30 if (!AlmostEqualUlps(oneD.x * one[0].y - oneD.y * one[0].x, | |
31 oneD.x * two[0].y - oneD.y * two[0].x)) { | |
32 return false; | |
33 } | |
34 return true; | |
35 } | |
36 | |
37 bool implicit_matches_ulps(const _Line& one, const _Line& two, int ulps) { | |
38 _Point oneD, twoD; | |
39 tangent(one, oneD); | |
40 tangent(two, twoD); | |
41 /* See if the slopes match, i.e. | |
42 dx1 / dy1 == dx2 / dy2 | |
43 (dy1 * dy2) * dx1 / dy1 == (dy1 * dy2) * dx2 / dy2 | |
44 dy2 * dx1 == dy1 * dx2 | |
45 */ | |
46 int diff = UlpsDiff((float) (oneD.x * twoD.y), (float) (twoD.x * oneD.y)); | |
47 if (diff < 0 || diff > ulps) { | |
48 return false; | |
49 } | |
50 /* See if the axis intercepts match, i.e. | |
51 y0 - x0 * dy / dx == y1 - x1 * dy / dx | |
52 dx * (y0 - x0 * dy / dx) == dx * (y1 - x1 * dy / dx) | |
53 dx * y0 - x0 * dy == dx * y1 - x1 * dy | |
54 */ | |
55 diff = UlpsDiff((float) (oneD.x * one[0].y - oneD.y * one[0].x), | |
56 (float) (oneD.x * two[0].y - oneD.y * two[0].x)); | |
57 return diff >= 0 && diff <= ulps; | |
58 } | |
59 | |
60 void tangent(const _Line& line, _Point& result) { | |
61 result.x = line[0].x - line[1].x; | |
62 result.y = line[0].y - line[1].y; | |
63 } | |
OLD | NEW |