blob: f291e7491e1f439b4d7ab4e42c69663394e17a28 [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.
rmistry@google.comd6176b02012-08-23 18:14:13 +00008
caryclark@google.com639df892012-01-10 21:46:10 +00009 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.
rmistry@google.comd6176b02012-08-23 18:14:13 +000013
caryclark@google.com639df892012-01-10 21:46:10 +000014 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;
rmistry@google.comd6176b02012-08-23 18:14:13 +000074
caryclark@google.com639df892012-01-10 21:46:10 +000075 // 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);
rmistry@google.comd6176b02012-08-23 18:14:13 +000083 if (midSides != 2) { // if mid point is not between
caryclark@google.com639df892012-01-10 21:46:10 +000084 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.
rmistry@google.comd6176b02012-08-23 18:14:13 +000094
caryclark@google.com639df892012-01-10 21:46:10 +000095 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.
rmistry@google.comd6176b02012-08-23 18:14:13 +000097
caryclark@google.com639df892012-01-10 21:46:10 +000098 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