Puzzle game: clipping of non-convex polygons on the figures

Question

I have an original figure in the SVG file. I need to break it randomly on parts, an example of which is specified below:

I have an idea, to use for partitioning Voronoi diagram (Fortune's algorithm). Can I then change the line of intersection of figures to give them a curvature? Can be obtained to identify each shape as a path? To create a game I'll be using cocos2d-x.

Answer 1

I think you've got the right idea, but the execution is going to be immensely challenging. I'm presuming when you say 'in an SVG file' you mean that the shape is defined by one (or more — your sample figure has an internal hole!) stroke paths. Unfortunately, SVG paths can be remarkably complicated, with both quadratic and cubic Bezier curves and elliptical arc segments. The intersection of a line with any of these is a solved problem, but a highly non-trivial one, and even the matter of re-parametrizing Bezier curves to split them in two at the point of intersection is a little tricky — basically, what you're looking for is complex enough to take a small book to answer, not a forum post! That said, there are several excellent references out there; the short short version of the answer is that you want to use recursive subdivision along with the so-called 'variation diminishing' property of the Bezier curve (essentially, the property that a Bezier curve is contained within the convex hull of its control points) to narrow down the possible locations of an intersection (and note that a line can have multiple intersection points, and that's another special-case that you may have to take into account). And once you solve the intersection problem, you've still got a long road ahead — you're going to have a ton of bookkeeping to do to keep track of curve and line segments and partition them correctly into pieces. This isn't to discourage you at all; just be aware of the magnitude of what you're trying to do!

Fortunately, your other question — 'can I change the line of intersection of figures to give them curvature?' — has an easier answer: absolutely. Since you're already in SVG-land, I'd use Bezier curves here too: first, choose five points p1..p5 along the line segment you want to 'curve out', probably somewhat at random in roughly equally-spaced intervals; then displace them a small random distance off the line, and use them as the control points of two separate Bezier curves, one using points p0, p1, p2, p3 and the other using points p3, p4, p5, and p6 (where p0 and p6 here are the two endpoints of the original line segment). You can take advantage of the convex-hull property of the Bezier curve here too, making sure that your displaced points don't displace too far so that the two regions to either side of the curve(s) are still simple regions. This should give you the sort of curved boundary that you're after.