blob: 1551720eef3000a24288df42cdc63cd1609c4754 [file] [log] [blame]
caryclark@google.comc6825902012-02-03 22:07:47 +00001#include "CurveIntersection.h"
caryclark@google.com8dcf1142012-07-02 20:27:02 +00002#include "CurveUtilities.h"
caryclark@google.com639df892012-01-10 21:46:10 +00003#include "IntersectionUtilities.h"
4
5/* Given a cubic, find the convex hull described by the end and control points.
6 The hull may have 3 or 4 points. Cubics that degenerate into a point or line
7 are not considered.
8
9 The hull is computed by assuming that three points, if unique and non-linear,
10 form a triangle. The fourth point may replace one of the first three, may be
11 discarded if in the triangle or on an edge, or may be inserted between any of
12 the three to form a convex quadralateral.
13
14 The indices returned in order describe the convex hull.
15*/
16int convex_hull(const Cubic& cubic, char order[4]) {
17 size_t index;
18 // find top point
19 size_t yMin = 0;
20 for (index = 1; index < 4; ++index) {
21 if (cubic[yMin].y > cubic[index].y || (cubic[yMin].y == cubic[index].y
22 && cubic[yMin].x > cubic[index].x)) {
23 yMin = index;
24 }
25 }
26 order[0] = yMin;
27 int midX = -1;
28 int backupYMin = -1;
29 for (int pass = 0; pass < 2; ++pass) {
30 for (index = 0; index < 4; ++index) {
31 if (index == yMin) {
32 continue;
33 }
34 // rotate line from (yMin, index) to axis
35 // see if remaining two points are both above or below
36 // use this to find mid
37 int mask = other_two(yMin, index);
38 int side1 = yMin ^ mask;
39 int side2 = index ^ mask;
40 Cubic rotPath;
41 if (!rotate(cubic, yMin, index, rotPath)) { // ! if cbc[yMin]==cbc[idx]
42 order[1] = side1;
43 order[2] = side2;
44 return 3;
45 }
46 int sides = side(rotPath[side1].y - rotPath[yMin].y);
47 sides ^= side(rotPath[side2].y - rotPath[yMin].y);
48 if (sides == 2) { // '2' means one remaining point <0, one >0
49 if (midX >= 0) {
50 printf("%s unexpected mid\n", __FUNCTION__); // there can be only one mid
51 }
52 midX = index;
53 } else if (sides == 0) { // '0' means both to one side or the other
54 backupYMin = index;
55 }
56 }
57 if (midX >= 0) {
58 break;
59 }
60 if (backupYMin < 0) {
61 break;
62 }
63 yMin = backupYMin;
64 backupYMin = -1;
65 }
66 if (midX < 0) {
67 midX = yMin ^ 3; // choose any other point
68 }
69 int mask = other_two(yMin, midX);
70 int least = yMin ^ mask;
71 int most = midX ^ mask;
72 order[0] = yMin;
73 order[1] = least;
74
75 // see if mid value is on same side of line (least, most) as yMin
76 Cubic midPath;
77 if (!rotate(cubic, least, most, midPath)) { // ! if cbc[least]==cbc[most]
78 order[2] = midX;
79 return 3;
80 }
81 int midSides = side(midPath[yMin].y - midPath[least].y);
82 midSides ^= side(midPath[midX].y - midPath[least].y);
83 if (midSides != 2) { // if mid point is not between
84 order[2] = most;
85 return 3; // result is a triangle
86 }
87 order[2] = midX;
88 order[3] = most;
89 return 4; // result is a quadralateral
90}
91
92/* Find the convex hull for cubics with the x-axis interval regularly spaced.
93 Cubics computed as distance functions are formed this way.
94
95 connectTo0[0], connectTo0[1] are the point indices that cubic[0] connects to.
96 connectTo3[0], connectTo3[1] are the point indices that cubic[3] connects to.
97
98 Returns true if cubic[1] to cubic[2] also forms part of the hull.
99*/
100bool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]) {
101 double projectedY[4];
102 projectedY[0] = 0;
103 int index;
104 for (index = 1; index < 4; ++index) {
105 projectedY[index] = (cubic[index].y - cubic[0].y) * (3.0 / index);
106 }
107 int lower0Index = 1;
108 int upper0Index = 1;
109 for (index = 2; index < 4; ++index) {
110 if (approximately_greater(projectedY[lower0Index], projectedY[index])) {
111 lower0Index = index;
112 }
113 if (approximately_lesser(projectedY[upper0Index], projectedY[index])) {
114 upper0Index = index;
115 }
116 }
117 connectTo0[0] = lower0Index;
118 connectTo0[1] = upper0Index;
119 for (index = 0; index < 3; ++index) {
120 projectedY[index] = (cubic[3].y - cubic[index].y) * (3.0 / (3 - index));
121 }
122 projectedY[3] = 0;
123 int lower3Index = 2;
124 int upper3Index = 2;
125 for (index = 1; index > -1; --index) {
126 if (approximately_greater(projectedY[lower3Index], projectedY[index])) {
127 lower3Index = index;
128 }
129 if (approximately_lesser(projectedY[upper3Index], projectedY[index])) {
130 upper3Index = index;
131 }
132 }
133 connectTo3[0] = lower3Index;
134 connectTo3[1] = upper3Index;
135 return (1 << lower0Index | 1 << upper0Index
136 | 1 << lower3Index | 1 << upper3Index) == 0x0F;
137}
138