0 Replies Latest reply on Dec 24, 2013 12:59 PM by Hunt Chang

    A super fast solution for intersection points of QuarticBez

    Hunt Chang

      Merry Xmas and Happy New Year to everyone,

       

      Last year I had presented my solution to find all of the intersection points in between two CubicBez plus its self-X at this forum, and now I am going to show you my X points solution for QuarticBez too. Besides that I have also enhanced the precision level of my solutions, all of 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 of application now.

       

      Welcome to challenge the correctness of my data!

       

      4X4-SW.png

       

      DataPicture

      Blue Curve: degree 4, control points,
        P0(641.00, 317.00), P1(56.00, 499.00), P2(941.00, 407.00), P3(466.00, 90.00), P4(536.00, 459.00);

       

      Self Intersection point at:
        S0(530.401776918847530, 369.210868992716200);  t[0] = 0.436239538089845, t[1] = 0.924201304222828;
        S1(532.585436013470480, 353.821023826750040);  t[2] = 0.058147195169712, t[3] = 0.906195089219209;
        S2(562.400435164756000, 342.938361667251680);  t[4] = 0.039055369839726, t[5] = 0.516064927597030;

       

      Red Curve: degree 4, control points,
        P0(481.00, 296.00), P1(813.00, 607.00), P2(50.00, 120.00), P3(899.00, 422.00), P4(491.00, 310.00);

       

      Self Intersection point at:
        S0(497.628498862507800, 311.812614714303830);  t[0] = 0.013388887744710, t[1] = 0.995859698720602;
        S1(557.530411367998570, 327.353378794937610);  t[2] = 0.677536607630758, t[3] = 0.947478751028856;
        S2(517.543076334643160, 331.543809132441200);  t[4] = 0.032454164042016, t[5] = 0.560068935539816;

       

      The Intersection point(s) of these two curves:
        X00(536.994587138007550, 352.161961736873310), X01(533.664168926726920, 348.495298015618000), X02(543.641997683741010, 359.724524727734550);
        X03(529.462551957199930, 382.483729402115160), X04(521.324900612037030, 374.941837651575610), X05(511.140779404885680, 362.197782510652360);
        X06(540.197721624213730, 327.097777850243740), X07(592.464728473590180, 332.624528363492460), X08(573.720712372247140, 329.091783088698660);
        X09(541.764426147850830, 323.447966621060520), X10(587.915357840668430, 334.149686556735450), X11(572.484816238581970, 330.862120063143270);


      Blue Curve's t value(s):
        t[00] = 0.055099324686673, t[01] = 0.899330038559955, t[02] = 0.466006933746555;
        t[03] = 0.938029352362295, t[04] = 0.417129144858024, t[05] = 0.074456528663603;
        t[06] = 0.866825317964481, t[07] = 0.022613654956977, t[08] = 0.557605267303758;
        t[09] = 0.860155758982648, t[10] = 0.024959441163513, t[11] = 0.552180042611492;


      Red Curve's t value(s):
        t[00] = 0.056557710111227, t[01] = 0.051851696600769, t[02] = 0.067024596081098;
        t[03] = 0.320258734889256, t[04] = 0.350912665703650, t[05] = 0.400671475678879;
        t[06] = 0.632903843108723, t[07] = 0.773728167171568, t[08] = 0.718447115250430;
        t[09] = 0.962879745842401, t[10] = 0.903852762338031, t[11] = 0.929457675005021;

      4X4z-SW.png

       

      DataPicture

      Blue Curve: degree 3, control points,
        P0(288.00, 305.00), P1(146.00, 63.00), P2(594.00, 199.00), P3(97.00, 271.00);

       

      Self Intersection point at:
        S0(260.175080447889460, 236.379369995136440);  t[1] = 0.113874694802425, t[2] = 0.852492498811599;

       

      Red Curve: degree 3, control points,
        P0(167.00, 234.00), P1(566.00, 358.00), P2(40.00, 105.00), P3(341.00, 225.00);

       

      The Intersection point(s) of these two curves:
        X00(216.080467030494330, 248.711593116638620), X01(267.262200293321600, 262.195597765329750), X02(285.631852013617620, 227.224765623157050);
        X03(259.723581224777830, 208.439145949994610), X04(263.370857553068670, 195.988587686783660), X05(313.087871035373550, 214.020485406213200);


      Blue Curve's t value(s):
        t[00] = 0.903277127822281, t[01] = 0.065486862194814, t[02] = 0.814823658439919;
        t[03] = 0.180123984016696, t[04] = 0.218191575529078, t[05] = 0.759177641562334;


      Red Curve's t value(s):
        t[00] = 0.045706191702026, t[01] = 0.109750691073050, t[02] = 0.519228233565162;
        t[03] = 0.621152627374970, t[04] = 0.874731348935366, t[05] = 0.965987432302451;

      3X3-SW.png

       

      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. Welcome for anyone to challenge the correctness and precision of these data!

       

      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