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