Generating points interior to a concave polygon

Do you have to generate many points for a given polygon? If that's the case, you can triangulate your polygon and then generate random points by picking a random triangle (with probability proportional to area) and then generating a random point in the triangle.

A few methods:

1. Triangulate, choose a triangle weighted by area, choose a point in that triangle. (Alvaro's method.)

1.5. Cut into slabs, choose a slab weighted by area, choose a point in that slab. Better time complexity than the previous method.

2. Rejection sampling: Pick a random point in the polygon's bounding box, use crossing test to see if it's inside. Repeat until one is.

3. Random descent through a BSP tree, weighted by the area on each side. The leaf will be a triangle, which you then randomly sample. (Haven't thought this one through too much, but it seems neat-o.)

4. If you're generating a LOT of points, you can use Metropolis-Hastings. This one's tricky to describe, and not relevant unless you need thousands or millions of points in the polygon... let me know.

I need to determine whether the polygon is inside, outside, or on the edge of a polyhedron. (For constructive solid geometry operations). The simplest method I know is to do raycasts from the polygon and see what it intersects. Problem is, the results become unreliable if the ray intersects a polygon edge, so I detect this, perturb the ray and recast.

I only need to generate a few points inside each polygon. No particular distribution is required, and it's okay if only a small part of the polygon is used. However it is important that points do not lie on the edge of the polygon. (Within epsilon tolerance)

Oh! If you don't need uniform distribution, that's a lot easier. For each point, find its interior bisector (that is, the ray into the polygon from the vertex which makes equal angles with each of the two neighboring edges). Find the first intersection of that ray with the other edges of the polygon. Now you have a bunch of line segments to generate points along, one for each vertex. As before, each segment costs you O(n).

I do believe Alvaro's method is the simplest. Not only that, if you don't require uniform or specific distribution, you can always have a set of points that are the center of each of the triangles that make up your polygon, so they're also trivial to compute.