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.

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.

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.

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).