algorithm - Find all non-overlapping regions from a graph of connected bezier paths -

i have this: set of edges, edge contains:

• a vector of conected bezier curves (the geometry)
• a set of pointers neihboor edges on each end

• pointers 2 regions adjacent edge ( null @ begining)

  class edge{ vector neighbors[2]; region* regions[2]; bezierpath geometry; }

there no intersecting edges in plane want find non-overlapping regions on plane surrounded edges

example: http://i.stack.imgur.com/s31qg.png

do know algorithm doing that?

i'll assume "bezier curve" mean "cubic bezier curve."

the parameter equation cubic bezier curve follows.

b(u, t) = u * w(t)           (2x1 column vector)  u = [u1 u2 u3 u4]            (2x4 matrix)         [    (1-t)^3      ] w(t) = [3 * (1-t)^2 * t  ]   (4x1 column vector)        [3 * (1-t)   * t^2]        [              t^3] 

the 4 column vectors of u 4 consecutive points on 1 of cubic bezier curves.

given 2 cubic bezier curves b(u, t) , b(v, t), want determine whether there exist t0 , t1 in [0,1] such b(u, t0) = b(v, t1). intersection points.

to solve equation, you'll need solve roots of system of 2 3rd-degree, 2-variable polynomials. if @ distinct t0 values among roots, tell intersection points cubic bezier curves b(u, t) , b(v, t).