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 */
implicit_matches(const _Line & one,const _Line & two)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
implicit_matches_ulps(const _Line & one,const _Line & two,int ulps)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
tangent(const _Line & line,_Point & result)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 }
64