Reply

A super fast solution to solve the intersection problem of Bezier curves

[ Edited ]

Merry Xmas to everyone,

 

I like to share a solution of mine and draw some attention of SolidEdge users and the R&D team of Siemens PLM. If this is impolite or anyone feel offended, please take my apology.

 

In the past, we were told to believe there are no solutions for the intersection problems of the parametric equations of Bezier curves and there is no solution to the self-X problems either. Actually they are not true.

 

Please watch my data and pictures below then you can make the judgment by yourself.

 

Blue Curve: degree 4, control points,
  P0(387.00, 349.00), P1(787.00, 198.00), P2(120.00, 486.00), P3(242.00, 50.00), P4(509.00, 359.00);

 

 Self Intersection point at:
  S0(469.838139298499410, 318.197362331964430);  t[0] = 0.069656683817288, t[1] = 0.962029982603426;
  S1(449.519944288017710, 300.465001940038350);  t[2] = 0.339638443927282, t[3] = 0.941005009454029;

 

Red Curve: degree 4, control points,
  P0(487.00, 269.00), P1(44.00, 253.00), P2(756.00, 456.00), P3(120.00, 20.00), P4(471.00, 397.00);

 

 Self Intersection point at:
  S0(379.725471047950800, 287.594036124411330);  t[0] = 0.455308366144889, t[1] = 0.897373880023737;
  S1(370.095509196072160, 272.457160713972770);  t[2] = 0.099218702961429, t[3] = 0.872228488160042;
  S2(385.572004267908480, 270.536876787925510);  t[4] = 0.078932490709650, t[5] = 0.555738164708322;

 

The Intersection point(s) of these two curves:
  X00(404.141752009129390, 269.144944705308720), X01(339.918916256242880, 281.888471531754020), X02(372.545980971463790, 292.187836114352420);
  X03(380.948846869200000, 257.741807538406480), X04(360.415652007513930, 250.627065331980820), X05(418.031591683276700, 337.365520480243840);
  X06(384.607565551905170, 294.602829084497390);


 Blue Curve's t value(s):
  t[00] = 0.888781813900420, t[01] = 0.541770681640841, t[02] = 0.471948852012151;
  t[03] = 0.857571153043595, t[04] = 0.825362918302459, t[05] = 0.021139256485913;
  t[06] = 0.449971241682696;


 Red Curve's t value(s):
  t[00] = 0.059414136949627, t[01] = 0.175569460869795, t[02] = 0.412368453428635;
  t[03] = 0.620375750334192, t[04] = 0.813850347895966, t[05] = 0.953969551725473;
  t[06] = 0.907209372066025;

 

The second one,

 

 

 

Blue Curve: degree 3, control points,
  P0(437.00, 181.00), P1(20.00, 42.00), P2(602.00, 329.00), P3(293.00, 118.00);

 

 Self Intersection point at:
  S0(339.830925357344600, 151.116211859683460);  t[1] = 0.100210620389809, t[2] = 0.939319294140106;

 

Red Curve: degree 3, control points,

  P0(277.00, 170.00), P1(523.00, 39.00), P2(134.00, 350.00), P3(378.00, 65.00);

 

 Self Intersection point at:
  S0(308.251357036046270, 154.039418129719680);  t[1] = 0.048135272215991, t[2] = 0.856256968901223;

 

The Intersection point(s) of these two curves:
  X00(296.004377113955340, 160.111030927053780), X01(323.467019812335590, 146.968865486704690), X02(330.206066338590290, 144.072802570196250);
  X03(349.054069545143250, 158.045684903848010), X04(352.495116958770320, 154.597721074622370), X05(325.641530457184790, 177.081501127609270);
  X06(314.422614508732120, 144.919479259039860), X07(302.082598545107660, 163.998106283902270), X08(320.160656974380170, 136.878335723582380);


 Blue Curve's t value(s):
  t[00] = 0.403490295239099, t[01] = 0.125500168162259, t[02] = 0.953947804322356;
  t[03] = 0.923616983984895, t[04] = 0.083299997909514, t[05] = 0.503469283275420;
  t[06] = 0.141913057497819, t[07] = 0.426870914125008, t[08] = 0.967774193543151;


 Red Curve's t value(s):
  t[00] = 0.027694514527966, t[01] = 0.077765921292720, t[02] = 0.093068401146250;
  t[03] = 0.397151501249560, t[04] = 0.376478721824760, t[05] = 0.512084579599908;
  t[06] = 0.877273315232328, t[07] = 0.829340921232635, t[08] = 0.893800194291865;

 

In the above two examples, I have presented the data of intersection points between two curves, self-intersections within each single curve, the coordinates of those X points and their responsive t values and each of their control-points for your reference. The Bezier equation of Cubic & Quartic should be easy to find via Google or Wikipedia, welcome for anyone to challenge the correctness and precision of these data!

 

I believe my solution would influence CAD and other tools development to a more advanced level and if you feel interested about my work and wish to know how fast my solutions can run? Welcome to visit my site .

 

Hunt Chang