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 #include "LineUtilities.h" | |
9 | |
10 bool implicitLine(const _Line& line, double& slope, double& axisIntercept) { | |
11 _Point delta; | |
12 tangent(line, delta); | |
13 bool moreHorizontal = fabs(delta.x) > fabs(delta.y); | |
14 if (moreHorizontal) { | |
15 slope = delta.y / delta.x; | |
16 axisIntercept = line[0].y - slope * line[0].x; | |
17 } else { | |
18 slope = delta.x / delta.y; | |
19 axisIntercept = line[0].x - slope * line[0].y; | |
20 } | |
21 return moreHorizontal; | |
22 } | |
23 | |
24 int reduceOrder(const _Line& line, _Line& reduced) { | |
25 reduced[0] = line[0]; | |
26 int different = line[0] != line[1]; | |
27 reduced[1] = line[different]; | |
28 return 1 + different; | |
29 } | |
30 | |
31 void sub_divide(const _Line& line, double t1, double t2, _Line& dst) { | |
32 _Point delta; | |
33 tangent(line, delta); | |
34 dst[0].x = line[0].x - t1 * delta.x; | |
35 dst[0].y = line[0].y - t1 * delta.y; | |
36 dst[1].x = line[0].x - t2 * delta.x; | |
37 dst[1].y = line[0].y - t2 * delta.y; | |
38 } | |
39 | |
40 // may have this below somewhere else already: | |
41 // copying here because I thought it was clever | |
42 | |
43 // Copyright 2001, softSurfer (www.softsurfer.com) | |
44 // This code may be freely used and modified for any purpose | |
45 // providing that this copyright notice is included with it. | |
46 // SoftSurfer makes no warranty for this code, and cannot be held | |
47 // liable for any real or imagined damage resulting from its use. | |
48 // Users of this code must verify correctness for their application. | |
49 | |
50 // Assume that a class is already given for the object: | |
51 // Point with coordinates {float x, y;} | |
52 //=================================================================== | |
53 | |
54 // isLeft(): tests if a point is Left|On|Right of an infinite line. | |
55 // Input: three points P0, P1, and P2 | |
56 // Return: >0 for P2 left of the line through P0 and P1 | |
57 // =0 for P2 on the line | |
58 // <0 for P2 right of the line | |
59 // See: the January 2001 Algorithm on Area of Triangles | |
60 // return (float) ((P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y))
; | |
61 double is_left(const _Line& line, const _Point& pt) { | |
62 _Vector P0 = line[1] - line[0]; | |
63 _Vector P2 = pt - line[0]; | |
64 return P0.cross(P2); | |
65 } | |
66 | |
67 double t_at(const _Line& line, const _Point& pt) { | |
68 double dx = line[1].x - line[0].x; | |
69 double dy = line[1].y - line[0].y; | |
70 if (fabs(dx) > fabs(dy)) { | |
71 if (approximately_zero(dx)) { | |
72 return 0; | |
73 } | |
74 return (pt.x - line[0].x) / dx; | |
75 } | |
76 if (approximately_zero(dy)) { | |
77 return 0; | |
78 } | |
79 return (pt.y - line[0].y) / dy; | |
80 } | |
81 | |
82 static void setMinMax(double x, int flags, double& minX, double& maxX) { | |
83 if (minX > x && (flags & (kFindTopMin | kFindBottomMin))) { | |
84 minX = x; | |
85 } | |
86 if (maxX < x && (flags & (kFindTopMax | kFindBottomMax))) { | |
87 maxX = x; | |
88 } | |
89 } | |
90 | |
91 void x_at(const _Point& p1, const _Point& p2, double top, double bottom, | |
92 int flags, double& minX, double& maxX) { | |
93 if (AlmostEqualUlps(p1.y, p2.y)) { | |
94 // It should be OK to bail early in this case. There's another edge | |
95 // which shares this end point which can intersect without failing to | |
96 // have a slope ... maybe | |
97 return; | |
98 } | |
99 | |
100 // p2.x is always greater than p1.x -- the part of points (p1, p2) are | |
101 // moving from the start of the cubic towards its end. | |
102 // if p1.y < p2.y, minX can be affected | |
103 // if p1.y > p2.y, maxX can be affected | |
104 double slope = (p2.x - p1.x) / (p2.y - p1.y); | |
105 int topFlags = flags & (kFindTopMin | kFindTopMax); | |
106 if (topFlags && ((top <= p1.y && top >= p2.y) | |
107 || (top >= p1.y && top <= p2.y))) { | |
108 double x = p1.x + (top - p1.y) * slope; | |
109 setMinMax(x, topFlags, minX, maxX); | |
110 } | |
111 int bottomFlags = flags & (kFindBottomMin | kFindBottomMax); | |
112 if (bottomFlags && ((bottom <= p1.y && bottom >= p2.y) | |
113 || (bottom >= p1.y && bottom <= p2.y))) { | |
114 double x = p1.x + (bottom - p1.y) * slope; | |
115 setMinMax(x, bottomFlags, minX, maxX); | |
116 } | |
117 } | |
118 | |
119 void xy_at_t(const _Line& line, double t, double& x, double& y) { | |
120 double one_t = 1 - t; | |
121 if (&x) { | |
122 x = one_t * line[0].x + t * line[1].x; | |
123 } | |
124 if (&y) { | |
125 y = one_t * line[0].y + t * line[1].y; | |
126 } | |
127 } | |
128 | |
129 _Point xy_at_t(const _Line& line, double t) { | |
130 double one_t = 1 - t; | |
131 _Point result = { one_t * line[0].x + t * line[1].x, one_t * line[0].y + t *
line[1].y }; | |
132 return result; | |
133 } | |
OLD | NEW |