I want to create Voronoï cells inside of an unconstrained enclosing shape (convex, concave, doesn't matter).

I found an implementation of Fortune's algorithm in C# here, and got some results:

Convex envelope: [attachment=16782:voronoi convex.png]

In the screenshots the white polygon is my envelope (hand-defined), the magenta points are the cell centers (hand-defined also), and the tiny red points + blue lines are Fortune's results.

I feed the algorithm all the points (envelope + cell centers), so I guess it considers the envelope points as cell centers as well; I haven't found anything that would specify that the envelope is only a boundary.

As you can see with a convex shape the result is kinda satisfying, I could more or less see how to finish the job (add some cells to fill the holes, cut some out-of-bounds triangles). But with the concave one there are many Voronoï vertices outside of the envelope, I would have to cut a lot of crap and then end up with concave cells in some cases... and I haven't even yet tried it with some really bad shapes. Anyway I believe this algorithm generates a convex hull of the point soup as by-product of the computation, or even uses it somehow, so I can't see it playing well with concave.

All in all it doesn't seem like this algorithm is quite right for the job: any ideas?

On a side-note, I'd like the cell centers to be randomly generated: how can I generate random points inside of any shape? A dumb solution would be to randomize inside the AABB and then check if the point is inside, repeat if not, but maybe a better solution exists?

All in all it doesn't seem like this algorithm is quite right for the job: any ideas?

You haven't told us what "the job" is, so it's hard to tell. Having vertices outside of your region is perfectly normal, and so is getting concave shapes, if your envelope is concave.

To get a random point inside of a polygon, find a triangulation of the polygon, pick a random triangle with probability proportional to area and pick a random point within the triangle.

What about generating the Voronoi cells in the AABB and then clipping the cells using your shape?

You haven't told us what "the job" is

I thought I did: "I want to create Voronoï cells inside of an unconstrained enclosing shape"

But a picture is worth a thousand words right? so here's a mockup of the result I'd want (green = wanted cells):

[attachment=16820:voronoi convex - mockup.jpg]

So basically it would consider the envelope as edges, and use them when figuring out the cells. Ideally it would automagically introduce new cells to fill some holes (but if the holes are too small then it should just enlarge the neighboring cells).

To get a random point inside of a polygon, find a triangulation of the polygon, pick a random triangle with probability proportional to area and pick a random point within the triangle.

Thanks, that seems perfect! I'll try that.

What about generating the Voronoi cells in the AABB and then clipping the cells using your shape?

Well that's more or less what happens now, but I'm afraid the "clipping" part is gonna lead to uninteresting results (tiny triangle cells, or concave cells, etc).

I wish to tell the algorithm that I already have static boundaries for the "exterior" cells, force it to use some predefined edges/vertices.

You don't need to adapt Voronoi cells to get roughly equal-sized polygons. This procedure works with a maximum piece area at least twice the minimum piece area: 1) Decompose the shape into convex pieces by adding appropriate diagonals ending in a reflex vertex (two if possible, like in your example). 2) Pick a random line and evaluate the area of the two slices it splits your shape into; if the smallest slice is large enough (above the minimum piece size), split the slices recursively until they are below the maximum piece size. How to pick a random line? If it goes through the barycenter, at any random angle, the slices have exactly the same area; you can disrupt regular patterns by choosing a point near the barycenter. If you pick the line through two random points of opposite edges, or a vertex and a random point of its opposite edge, you can easily guarantee that no edges are cut into excessively short segments and/or sweep an end of the line until the area constraint is satisfied.

Well that's more or less what happens now, but I'm afraid the "clipping" part is gonna lead to uninteresting results (tiny triangle cells, or concave cells, etc).
I wish to tell the algorithm that I already have static boundaries for the "exterior" cells, force it to use some predefined edges/vertices.

I was thinking about polygon clipping. I don't see how this procedure may produce unwanted tiny triangle or concave cells.

Ideally it would automagically introduce new cells to fill some holes (but if the holes are too small then it should just enlarge the neighboring cells).

Voronoi cells do not have "holes". Each cell is defined as the set of points which are nearest to one of the points of the set. It is quite clear than any point should be in one of those cells.. Any algorithm which computes the Voronoi complex of a set of points shouldn't leave any hole. If it does, there is something wrong about it. In your case, the problem is that you are adding the vertices of your shape to the points used to compute the Voronoi complex. It is what you want?