Jump to content
  • Advertisement
Sign in to follow this  
taz0010

Generating points interior to a concave polygon

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!