cancel
Turn on suggestions
Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.
Showing results for 
Search instead for 
Did you mean: 

Archives Discussions

hunt_chang
Journeyman III
‎12-26-2013 01:56 AM

A Super Fast Solution of intersections for Bezier Curves

Merry Xmas and Happy New Year to everyone,

Last year I had presented my solution here about finding all of the intersection points in between two Cubic Bezier curves plus its self-X, and now I am going to show you my new X points solution for QuarticBez too. Besides that I have also enhanced the precision level of my solutions, all the deviation can be controlled in the level no higher than 1.0e-9, which means my solutions are ready to be used as a stable tool for various kind of application now.

4X4-AMD.png

DataZoom Picture

Blue Curve: degree 4, control points,
  P0(365.00, 234.00), P1(702.00, 6.00), P2(15.00, 270.00), P3(800.00, 411.00), P4(321.00, 159.00);

Self Intersection point at:
  S0(422.623866578220830, 219.100707365751530);  t[0] = 0.470568235168694, t[1] = 0.928965105280191;
  S1(403.771414449105410, 206.564631127658800);  t[2] = 0.033644311244951, t[3] = 0.946215379164179;
  S2(428.146585044641600, 187.490098585855800);  t[4] = 0.063282793880594, t[5] = 0.384577459709910;


Red Curve: degree 4, control points,
  P0(289.00, 219.00), P1(619.00, 281.00), P2(433.00, 42.00), P3(244.00, 99.00), P4(566.00, 340.00);


Self Intersection point at:
  S0(433.839624042999790, 220.171822083503030);  t[0] = 0.169622726530818, t[1] = 0.847996997510708;


The Intersection point(s) of these two curves:
  X00(373.132669769454200, 228.452384975740300), X01(422.976765319260100, 223.603384644635180), X02(427.328608685923310, 222.394565648216480);
  X03(453.238364069660750, 164.255182274873330), X04(447.975296939753890, 157.993040158902660), X05(423.163860704513580, 206.415509255545150);
  X06(416.528839850635050, 196.830100491660910), X07(454.443486880512640, 243.396391744401060), X08(472.693821439787600, 261.766619105502170);


Blue Curve's t value(s):
  t[00] = 0.006206970900832, t[01] = 0.482580691766434, t[02] = 0.924118404044710;
  t[03] = 0.115684858451726, t[04] = 0.278944240069076, t[05] = 0.436819858435325;
  t[06] = 0.047883985834167, t[07] = 0.888939387836823, t[08] = 0.847857157064769;


Red Curve's t value(s):
  t[00] = 0.076900012265960, t[01] = 0.147590072801383, t[02] = 0.155924661830965;
  t[03] = 0.398565884526332, t[04] = 0.426824837981717, t[05] = 0.824218211537170;
  t[06] = 0.806057750545920, t[07] = 0.883703196233528, t[08] = 0.909078781554686;

4X4z-AMD.png

Header 1
3X3-AMD.png

Blue Curve: degree 3, control points,
  P0(315.00, 52.00), P1(29.00, 321.00), P2(367.00, 281.00), P3(293.00, 45.00);

Self Intersection point at:
  S0(298.949925280094930, 67.407618892325132);  t[1] = 0.019529538620305, t[2] = 0.967466278888468;


Red Curve: degree 3, control points,
  P0(194.00, 95.00), P1(555.00, 261.00), P2(30.00, 88.00), P3(317.00, 114.00);


Self Intersection point at:
  S0(235.355982130217680, 114.368935343872980);  t[1] = 0.042499014859523, t[2] = 0.843266088117618;


The Intersection point(s) of these two curves:
  X00(249.020451741775960, 120.965581849421540), X01(300.199405205105680, 147.395573402130050), X02(296.397482594187810, 161.709774790957060);
  X03(238.046489588316890, 134.598419235671570), X04(257.136801594420720, 111.455978116500300), X05(303.881295989673330, 112.905702043116350);


Blue Curve's t value(s):
  t[00] = 0.095900097495871, t[01] = 0.830834081410266, t[02] = 0.801013743091780;
  t[03] = 0.118159081452121, t[04] = 0.081168420861567, t[05] = 0.894691324927957;


Red Curve's t value(s):
  t[00] = 0.059034581916642, t[01] = 0.144695830927720, t[02] = 0.455144046486331;
  t[03] = 0.665309525636102, t[04] = 0.908115561552037, t[05] = 0.984051799035192;

In the above two examples, I have presented the data of intersection points in between two curves, self-intersections within each single curve, the coordinates of those X points and their responsible t values and each of their control-points for your reference. Welcome for anyone to challenge the correctness and precision of these data!


From now on, I believe these solutions that I found would not only enhance our CAD design capability but it would also deeply changing the curve smoothness of those 3D models and their animation show in video and display. If you feel interested about my work and wish to know how fast my solutions can run? Welcome to visit my site at https://sites.google.com/site/curvesintersection/


Hunt Chang

0 Likes
0 Replies