I'm working a little program that converges on vector-based approximations of raster images, inspired by Roger Alsing's genetic Mona Lisa. (I started on this after his first blog post two years ago, played a bit, and it's been on the back burner. But I'd like to un-back-burner it because I have some interesting further ideas.)
Roger Alsing's program uses randomly-generated sometimes-self-overlapping n-gons. Instead, I'm using Bézier splines linked into what, for lack of a math education, I am calling "Bézier petal" shapes. These are, simply, two cubic Bézier curves which share end points (but not control points). You can see this in action in this little youtube video.
The shapes I'm currently using are constructed by generating six random points. These are then sorted radially around their center of gravity, and two opposite points become the end-points of the two cubic Bézier curves, with the other four points used as control points where the fit into the order.
Because I, as I mentioned, have no math background, I can't prove it, but empirically this guarantees a non-degenerate petal, with no overlaps or twists. But, it's frustratingly limiting, since it will never produce crescents or S shapes — theoretically-valid "petals". (The results are not always convex, but concavities can only happen at the end points.)
(Here's a video of what happens if I allow self-intersecting shapes — not graceful.)
I'd love suggestions for a process which generates all possible non-intersecting shapes. It's clearly better for the application if the process can be done with minimal computation, although I'm willing to pay a bit of time in exchange for nicer results.
A further constraint is that small changes in the "source" data — in the current case, the six random points — needs to produce relatively small changes in the output, or else my stochastic hill-climbing approach can't get anywhere.
Also, it's fine if some input values produce no output — those will just get discarded.
Another possible way of asking the same question: is there an optimization for finding whether two cubic Bézier curves that share endpoints intersect? If I can calculate that quickly, I can simply discard the invalid ones.
Best Answer
One way of finding out whether two Bezier curves sharing the endpoints intersect is to calculate all the intersections of two general Bezier curves and discard the $0$ and $1$ parameters from the solutions.
One way of calculating the intersections of two Bezier curve is the well known "subdivision" method: when the convex hulls of two Bezier curves do not overlap, the curves cannot overlap neither. If they do overlap, subdivide both the curves with De Casteljau's algorithm and recurse with all the combinations so that you check each part of the first curve with each of the parts of the second curve. Stop if convex hulls are small enough or if they can be approximate by a line segment, in which case simply compute their intersection.
Alternatively, as you are interested in a visual setting, chop off the ends of one of the curves (i.e., remove the parts with parameter $[0, \epsilon]$ and $[1-\epsilon, 1]$, where $\epsilon$ is a small number), so that you don't look for intersection at the endpoints only to discard them later.
More on intersection methods of Bezier curves can be found in Comparison of three curve intersection algorithms by Sederberg and Parry (1986).