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 
8 #include "tests/PathOpsCubicIntersectionTestData.h"
9 
10 #include <limits>
11 
12 static const double D = FLT_EPSILON / 2;
13 static const double G = FLT_EPSILON / 3;
14 static const double N = -FLT_EPSILON / 2;
15 static const double M = -FLT_EPSILON / 3;
16 
17 const CubicPts pointDegenerates[] = {
18     {{{0, 0}, {0, 0}, {0, 0}, {0, 0}}},
19     {{{1, 1}, {1, 1}, {1, 1}, {1, 1}}},
20     {{{1 + FLT_EPSILON_HALF, 1}, {1, 1 + FLT_EPSILON_HALF}, {1, 1}, {1, 1}}},
21     {{{1 + D, 1}, {1 - D, 1}, {1, 1}, {1, 1}}},
22     {{{0, 0}, {0, 0}, {1, 0}, {0, 0}}},
23     {{{0, 0}, {1, 0}, {0, 0}, {0, 0}}},
24     {{{0, 0}, {0, 0}, {0, 1}, {0, 0}}},
25     {{{0, 0}, {0, 1}, {0, 0}, {0, 0}}},
26     {{{0, 0}, {0, 0}, {1, 1}, {0, 0}}},
27     {{{0, 0}, {1, 1}, {0, 0}, {0, 0}}},
28     {{{0, 0}, {1, 1}, {2, 2}, {0, 0}}},
29     {{{1, 1}, {2, 2}, {2, 2}, {1, 1}}},
30     {{{0, 0}, {0, D}, {1, 0}, {0, 0}}},
31     {{{0, 0}, {1, 0}, {0, D}, {0, 0}}},
32     {{{0, 0}, {D, 0}, {0, 1}, {0, 0}}},
33     {{{0, 0}, {0, 1}, {D, 0}, {0, 0}}},
34     {{{1, 1}, {2, 2}, {2, 2+D}, {1, 1}}},
35     {{{0, 0}, {0, N}, {1, 0}, {0, 0}}},
36     {{{0, 0}, {1, 0}, {0, N}, {0, 0}}},
37     {{{0, 0}, {N, 0}, {0, 1}, {0, 0}}},
38     {{{0, 0}, {0, 1}, {N, 0}, {0, 0}}},
39     {{{0, 0}, {1, 1}, {N, 0}, {0, 0}}},
40     {{{0, 0}, {D, 0}, {1, 1}, {0, 0}}},
41     {{{0, 0}, {1, 1}, {D, 0}, {0, 0}}},
42     {{{0, 0}, {N, 0}, {1, 1}, {0, 0}}},
43     {{{1, 1}, {2, 2}, {2, 2+N}, {1, 1}}},
44 };
45 
46 const size_t pointDegenerates_count = SK_ARRAY_COUNT(pointDegenerates);
47 
48 const CubicPts notPointDegenerates[] = {
49     {{{1 + FLT_EPSILON * 8, 1}, {1, FLT_EPSILON * 8}, {1, 1}, {1, 1}}},
50     {{{1 + FLT_EPSILON * 8, 1}, {1 - FLT_EPSILON * 8, 1}, {1, 1}, {1, 1}}}
51 };
52 
53 const size_t notPointDegenerates_count =
54         SK_ARRAY_COUNT(notPointDegenerates);
55 
56 // from http://www.truetex.com/bezint.htm
57 const CubicPts tests[][2] = {
58     {  // intersects in one place (data gives bezier clip fits
59      {{{0, 45},
60       {6.0094158284751593, 51.610357411322688},
61       {12.741093228940867, 55.981703949474607},
62       {20.021417396476362, 58.652245509710262}}},
63      {{{2.2070737699246674, 52.703494107327209},
64       {31.591482272629477, 23.811002295222025},
65       {76.824588616426425, 44.049473790502674},
66       {119.25488947221436, 55.599248272955073}}}
67     }, {  // intersects in three places
68         {{{0, 45}, {50, 100}, {150,   0}, {200, 55}}},
69         {{{0, 55}, {50,   0}, {150, 100}, {200, 45}}}
70     }, {  // intersects in one place, cross over is nearly parallel
71         {{{0,   0}, {0, 100}, {200,   0}, {200, 100}}},
72         {{{0, 100}, {0,   0}, {200, 100}, {200,   0}}}
73     }, {  // intersects in two places
74         {{{0,   0}, {0, 100}, {200, 100}, {200,   0}}},
75         {{{0, 100}, {0,   0}, {200,   0}, {200, 100}}}
76     }, {
77         {{{150, 100}, {150 + 0.1, 150}, {150, 200}, {150, 250}}},
78         {{{250, 150}, {200, 150 + 0.1}, {150, 150}, {100, 150}}}
79     }, {  // single intersection around 168,185
80         {{{200, 100}, {150, 100}, {150, 150}, {200, 150}}},
81         {{{250, 150}, {250, 100}, {100, 100}, {100, 150}}}
82     }, {
83         {{{1.0, 1.5}, {15.5, 0.5}, {-8.0, 3.5}, {5.0, 1.5}}},
84         {{{4.0, 0.5}, {5.0, 15.0}, {2.0, -8.5}, {4.0, 4.5}}}
85     }, {
86         {{{664.00168, 0},       {726.11545, 124.22757}, {736.89069, 267.89743},
87                 {694.0017, 400.0002}}},
88         {{{850.66843, 115.55563}, {728.515, 115.55563}, {725.21347, 275.15309},
89                 {694.0017, 400.0002}}}
90     }, {
91         {{{1, 1},   {12.5, 6.5}, {-4, 6.5}, {7.5, 1}}},
92         {{{1, 6.5}, {12.5, 1},   {-4, 1},   {.5, 6}}}
93     }, {
94         {{{315.748, 312.84}, {312.644, 318.134}, {305.836, 319.909}, {300.542, 316.804}}},
95         {{{317.122, 309.05}, {316.112, 315.102}, {310.385, 319.19},  {304.332, 318.179}}}
96     }, {
97         {{{1046.604051, 172.937967},  {1046.604051, 178.9763059}, {1041.76745,  183.9279165}, {1035.703842, 184.0432409}}},
98         {{{1046.452235, 174.7640504}, {1045.544872, 180.1973817}, {1040.837966, 184.0469882}, {1035.505925, 184.0469882}}}
99     }, {
100         {{{125.79356, 199.57382}, {51.16556, 128.93575}, {87.494,  16.67848}, {167.29361, 16.67848}}},
101         {{{167.29361, 55.81876}, {100.36128, 55.81876}, {68.64099, 145.4755}, {125.7942, 199.57309}}}
102     }, {
103         {{{104.11546583642826, 370.21352558595504}, {122.96968232592344, 404.54489231839295},
104           {169.90881005384728, 425.00067000000007}, {221.33045999999999, 425.00067000000001}}},
105         {{{116.32365976159625, 381.71048540582598}, {103.86096590870899, 381.71048540581626},
106           {91.394188003200725, 377.17917781762833}, {82.622283093355179, 368.11683661930334}}}
107     }
108 };
109 
110 const size_t tests_count = SK_ARRAY_COUNT(tests);
111 
112 const CubicPts lines[] = {
113     {{{0, 0}, {0, 0}, {0, 0}, {1, 0}}},  // 0: horizontal
114     {{{1, 0}, {0, 0}, {0, 0}, {0, 0}}},
115     {{{1, 0}, {2, 0}, {3, 0}, {4, 0}}},
116     {{{0, 0}, {0, 0}, {0, 0}, {0, 1}}},  // 5: vertical
117     {{{0, 1}, {0, 0}, {0, 0}, {0, 0}}},
118     {{{0, 1}, {0, 2}, {0, 3}, {0, 4}}},
119     {{{0, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 10: 3 coincident
120     {{{1, 1}, {0, 0}, {0, 0}, {0, 0}}},
121     {{{0, 0}, {0, 0}, {1, 1}, {2, 2}}},  // 14: 2 coincident
122     {{{0, 0}, {1, 1}, {0, 0}, {2, 2}}},
123     {{{1, 1}, {0, 0}, {0, 0}, {2, 2}}},  // 17:
124     {{{1, 1}, {0, 0}, {2, 2}, {0, 0}}},
125     {{{1, 1}, {2, 2}, {0, 0}, {0, 0}}},
126     {{{1, 1}, {2, 2}, {3, 3}, {2, 2}}},  // middle-last coincident
127     {{{1, 1}, {2, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
128     {{{1, 1}, {1, 1}, {2, 2}, {2, 2}}},  // 2 pairs coincident
129     {{{1, 1}, {2, 2}, {1, 1}, {2, 2}}},
130     {{{1, 1}, {1, 1}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
131     {{{1, 1}, {2, 2}, {3, 3}, {4, 4}}},  // no coincident
132     {{{1, 1}, {3, 3}, {2, 2}, {4, 4}}},
133     {{{1, 1}, {2, 2}, {4, 4}, {3, 3}}},
134     {{{1, 1}, {3, 3}, {4, 4}, {2, 2}}},
135     {{{1, 1}, {4, 4}, {2, 2}, {3, 3}}},
136     {{{1, 1}, {4, 4}, {3, 3}, {2, 2}}},
137     {{{2, 2}, {1, 1}, {3, 3}, {4, 4}}},
138     {{{2, 2}, {1, 1}, {4, 4}, {3, 3}}},
139     {{{2, 2}, {3, 3}, {1, 1}, {4, 4}}},
140     {{{2, 2}, {3, 3}, {4, 4}, {1, 1}}},
141     {{{2, 2}, {4, 4}, {1, 1}, {3, 3}}},
142     {{{2, 2}, {4, 4}, {3, 3}, {1, 1}}},
143 };
144 
145 const size_t lines_count = SK_ARRAY_COUNT(lines);
146 
147 // 'not a line' tries to fool the line detection code
148 const CubicPts notLines[] = {
149     {{{0, 0}, {0, 0}, {0, 1}, {1, 0}}},
150     {{{0, 0}, {0, 1}, {0, 0}, {1, 0}}},
151     {{{0, 0}, {0, 1}, {1, 0}, {0, 0}}},
152     {{{0, 1}, {0, 0}, {0, 0}, {1, 0}}},
153     {{{0, 1}, {0, 0}, {1, 0}, {0, 0}}},
154     {{{0, 1}, {1, 0}, {0, 0}, {0, 0}}},
155 };
156 
157 const size_t notLines_count = SK_ARRAY_COUNT(notLines);
158 
159 static const double E = FLT_EPSILON * 8;
160 static const double F = FLT_EPSILON * 8;
161 
162 const CubicPts modEpsilonLines[] = {
163     {{{0, E}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal
164     {{{0, 0}, {0, E}, {1, 0}, {0, 0}}},
165     {{{0, 0}, {1, 0}, {0, E}, {0, 0}}},
166     {{{1, 0}, {0, 0}, {0, 0}, {0, E}}},
167     {{{1, E}, {2, 0}, {3, 0}, {4, 0}}},
168     {{{E, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical
169     {{{0, 0}, {E, 0}, {0, 1}, {0, 0}}},
170     {{{0, 0}, {0, 1}, {E, 0}, {0, 0}}},
171     {{{0, 1}, {0, 0}, {0, 0}, {E, 0}}},
172     {{{E, 1}, {0, 2}, {0, 3}, {0, 4}}},
173     {{{E, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident
174     {{{0, 0}, {E, 0}, {1, 1}, {0, 0}}},
175     {{{0, 0}, {1, 1}, {E, 0}, {0, 0}}},
176     {{{1, 1}, {0, 0}, {0, 0}, {E, 0}}},
177     {{{0, E}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident
178     {{{0, 0}, {1, 1}, {0, E}, {2, 2}}},
179     {{{0, 0}, {1, 1}, {2, 2}, {0, E}}},
180     {{{1, 1}, {0, E}, {0, 0}, {2, 2}}},
181     {{{1, 1}, {0, E}, {2, 2}, {0, 0}}},
182     {{{1, 1}, {2, 2}, {E, 0}, {0, 0}}},
183     {{{1, 1}, {2, 2+E}, {3, 3}, {2, 2}}},  // middle-last coincident
184     {{{1, 1}, {2+E, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
185     {{{1, 1}, {1, 1}, {2, 2}, {2+E, 2}}},  // 2 pairs coincident
186     {{{1, 1}, {2, 2}, {1, 1}, {2+E, 2}}},
187     {{{1, 1}, {2, 2}, {2, 2+E}, {1, 1}}},
188     {{{1, 1}, {1, 1+E}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
189     {{{1, 1}, {2+E, 2}, {3, 3}, {4, 4}}},  // no coincident
190     {{{1, 1}, {3, 3}, {2, 2}, {4, 4+F+F}}},  // INVESTIGATE: why the epsilon is bigger
191     {{{1, 1+F+F}, {2, 2}, {4, 4}, {3, 3}}},  // INVESTIGATE: why the epsilon is bigger
192     {{{1, 1}, {3, 3}, {4, 4+E}, {2, 2}}},
193     {{{1, 1}, {4, 4}, {2, 2}, {3, 3+E}}},
194     {{{1, 1}, {4, 4}, {3, 3}, {2+E, 2}}},
195     {{{2, 2}, {1, 1}, {3+E, 3}, {4, 4}}},
196     {{{2, 2}, {1+E, 1}, {4, 4}, {3, 3}}},
197     {{{2, 2+E}, {3, 3}, {1, 1}, {4, 4}}},
198     {{{2+E, 2}, {3, 3}, {4, 4}, {1, 1}}},
199     {{{2, 2}, {4+E, 4}, {1, 1}, {3, 3}}},
200     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+E}}},
201 };
202 
203 const size_t modEpsilonLines_count = SK_ARRAY_COUNT(modEpsilonLines);
204 
205 const CubicPts lessEpsilonLines[] = {
206     {{{0, D}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal
207     {{{1, 0}, {0, 0}, {0, 0}, {0, D}}},
208     {{{1, D}, {2, 0}, {3, 0}, {4, 0}}},
209     {{{D, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical
210     {{{0, 1}, {0, 0}, {0, 0}, {D, 0}}},
211     {{{D, 1}, {0, 2}, {0, 3}, {0, 4}}},
212     {{{D, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident
213     {{{1, 1}, {0, 0}, {0, 0}, {D, 0}}},
214     {{{0, D}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident
215     {{{0, 0}, {1, 1}, {0, D}, {2, 2}}},
216     {{{0, 0}, {1, 1}, {2, 2}, {1, 1+D}}},
217     {{{1, 1}, {0, D}, {0, 0}, {2, 2}}},
218     {{{1, 1}, {0, D}, {2, 2}, {0, 0}}},
219     {{{1, 1}, {2, 2}, {D, 0}, {0, 0}}},
220     {{{1, 1}, {2, 2+D}, {3, 3}, {2, 2}}},  // middle-last coincident
221     {{{1, 1}, {2+D, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
222     {{{1, 1}, {1, 1}, {2, 2}, {2+D, 2}}},  // 2 pairs coincident
223     {{{1, 1}, {2, 2}, {1, 1}, {2+D, 2}}},
224     {{{1, 1}, {1, 1+D}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
225     {{{1, 1}, {2+D/2, 2}, {3, 3}, {4, 4}}},  // no coincident (FIXME: N as opposed to N/2 failed)
226     {{{1, 1}, {3, 3}, {2, 2}, {4, 4+D}}},
227     {{{1, 1+D}, {2, 2}, {4, 4}, {3, 3}}},
228     {{{1, 1}, {3, 3}, {4, 4+D}, {2, 2}}},
229     {{{1, 1}, {4, 4}, {2, 2}, {3, 3+D}}},
230     {{{1, 1}, {4, 4}, {3, 3}, {2+G, 2}}},  // INVESTIGATE: why the epsilon is smaller
231     {{{2, 2}, {1, 1}, {3+D, 3}, {4, 4}}},
232     {{{2, 2}, {1+D, 1}, {4, 4}, {3, 3}}},
233     {{{2, 2+D}, {3, 3}, {1, 1}, {4, 4}}},
234     {{{2+G, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is smaller
235     {{{2, 2}, {4+D, 4}, {1, 1}, {3, 3}}},
236     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+D}}},
237 };
238 
239 const size_t lessEpsilonLines_count = SK_ARRAY_COUNT(lessEpsilonLines);
240 
241 const CubicPts negEpsilonLines[] = {
242     {{{0, N}, {0, 0}, {0, 0}, {1, 0}}},  // horizontal
243     {{{1, 0}, {0, 0}, {0, 0}, {0, N}}},
244     {{{1, N}, {2, 0}, {3, 0}, {4, 0}}},
245     {{{N, 0}, {0, 0}, {0, 0}, {0, 1}}},  // vertical
246     {{{0, 1}, {0, 0}, {0, 0}, {N, 0}}},
247     {{{N, 1}, {0, 2}, {0, 3}, {0, 4}}},
248     {{{N, 0}, {0, 0}, {0, 0}, {1, 1}}},  // 3 coincident
249     {{{1, 1}, {0, 0}, {0, 0}, {N, 0}}},
250     {{{0, N}, {0, 0}, {1, 1}, {2, 2}}},  // 2 coincident
251     {{{0, 0}, {1, 1}, {0, N}, {2, 2}}},
252     {{{0, 0}, {1, 1}, {2, 2}, {1, 1+N}}},
253     {{{1, 1}, {0, N}, {0, 0}, {2, 2}}},
254     {{{1, 1}, {0, N}, {2, 2}, {0, 0}}},
255     {{{1, 1}, {2, 2}, {N, 0}, {0, 0}}},
256     {{{1, 1}, {2, 2+N}, {3, 3}, {2, 2}}},  // middle-last coincident
257     {{{1, 1}, {2+N, 2}, {3, 3}, {3, 3}}},  // middle-last coincident
258     {{{1, 1}, {1, 1}, {2, 2}, {2+N, 2}}},  // 2 pairs coincident
259     {{{1, 1}, {2, 2}, {1, 1}, {2+N, 2}}},
260     {{{1, 1}, {1, 1+N}, {3, 3}, {3, 3}}},  // first-middle middle-last coincident
261     {{{1, 1}, {2+N/2, 2}, {3, 3}, {4, 4}}},  // no coincident (FIXME: N as opposed to N/2 failed)
262     {{{1, 1}, {3, 3}, {2, 2}, {4, 4+N}}},
263     {{{1, 1+N}, {2, 2}, {4, 4}, {3, 3}}},
264     {{{1, 1}, {3, 3}, {4, 4+N}, {2, 2}}},
265     {{{1, 1}, {4, 4}, {2, 2}, {3, 3+N}}},
266     {{{1, 1}, {4, 4}, {3, 3}, {2+M, 2}}},  // INVESTIGATE: why the epsilon is smaller
267     {{{2, 2}, {1, 1}, {3+N, 3}, {4, 4}}},
268     {{{2, 2}, {1+N, 1}, {4, 4}, {3, 3}}},
269     {{{2, 2+N}, {3, 3}, {1, 1}, {4, 4}}},
270     {{{2+M, 2}, {3, 3}, {4, 4}, {1, 1}}},  // INVESTIGATE: why the epsilon is smaller
271     {{{2, 2}, {4+N, 4}, {1, 1}, {3, 3}}},
272     {{{2, 2}, {4, 4}, {3, 3}, {1, 1+N}}},
273 };
274 
275 const size_t negEpsilonLines_count = SK_ARRAY_COUNT(negEpsilonLines);
276