# Generating points interior to a concave polygon

This topic is 3011 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I need an algorithm to randomly generate a point which is guaranteed to lie inside a concave polygon. The initial method I was using was to find a diagonal to the polygon, which is a line between two vertices that does not intersect any edges of the polygon. This can be done in O(n). I can then generate random points on the line, which are all interior to the polygon.

However a line is only a 1D region, and points need to be generated over 2 dimensions. Is there a reliable and fast algorithm that can achieve this?

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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)

##### Share on other sites
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).

##### Share on other sites
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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 9
• 13
• 9
• 9
• 15
• ### Forum Statistics

• Total Topics
634073
• Total Posts
3015343
×