PathOpsCubicIntersectionTestData.cpp 12 KB

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