Sign in to follow this  

Any old point in a polygon

This topic is 3746 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'd like to generate a point in a polygon. It doesn't matter what the point is, as long as it's inside the polygon (and not math-breakingly close to an edge). The polygon can be concave and (ideally) have either clockwise or counterclockwise winding, but will have no self-intersection. Right now I'm calculating the winding of the polygon, then searching for a convex corner, then finding a point near that convex point by linearly blending in a bit of the normalized vectors to the neighboring two points. There must be a simpler way to do it, though. It's way too simple a thing for there not to be.

Share this post


Link to post
Share on other sites
What if the convex corner has a nearby concave corner, causing your result to be outside the polygon? To really do this robustly, it might be necessary to first find a triangle that is fully enclosed in the polygon, and then take the average of its corners. Unless the points you're blending form a convex shape that is inside the polygon, there's no way to know how close the result is from another edge without explicitly computing it by checking against every edge.

Share this post


Link to post
Share on other sites
My first thought is to cut it up into convex pieces, and then calculate the average of the points from one of those convex pieces that has sufficient area.
This is obviously a lot easier if you know the winding.

My second idea:
Assuming you know how many points there are (if not, count them), pick points 0, n/3, and 2n/3. Now check that all other points are not inside this triangle. If not, swap one of those points with the point that is inside the triangle, and continue processing the rest of them (Previously tested points will still be outside). Find the average of the resulting 3 points.

Neither is highly optimised perhaps, but does it need to be fast?

Share this post


Link to post
Share on other sites
Quote:
Original post by smitty1276
Would it be easier to just generate random points within the polygon's bounding box, rejecting those that don't lie withing the polygon, until you get one?
I thought of that too. I'm not sure it would prevent picking a point that was too close to an edge.
Also, Sneftel might want a predicitable result such that if it were called again with the same polygon, you get the same point.
May be worth considering though.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Right now I'm calculating the winding of the polygon, then searching for a convex corner, then finding a point near that convex point by linearly blending in a bit of the normalized vectors to the neighboring two points. There must be a simpler way to do it, though. It's way too simple a thing for there not to be.


Find an "ear" of the polygon. This is a convex vertex, call it V1, with neighboring vertices V0 and V2, such that no other polygon vertices are in the triangle formed by <V0,V1,V2>. Randomly choose barycentric coordinates b0, b1, and b2 (all in [0,1] and b0+b1+b2=1). The point b0*V0+b1*V1+b2*V2 is inside the polygon. To stay away from the edges <V0,V1> and <V1,V2>, choose b0 and b2 to be positive (maybe b0 >= e and b2 >= e for a user-prescribed e > 0).

Share this post


Link to post
Share on other sites


Quote:
Original post by Sneftel
Right now I'm calculating the winding of the polygon, then searching for a convex corner, then finding a point near that convex point by linearly blending in a bit of the normalized vectors to the neighboring two points. There must be a simpler way to do it, though. It's way too simple a thing for there not to be.
Simply-stated problems don't necessarily have simple solutions. I don't think there is a simple solution to this one. Also, Vorpy's comment below applies to what you describe.

Quote:
Original post by Vorpy
What if the convex corner has a nearby concave corner, causing your result to be outside the polygon? To really do this robustly, it might be necessary to first find a triangle that is fully enclosed in the polygon, and then take the average of its corners.
This could certainly be the case. If you wanted to be on the safe side, you could use effectively use ear clipping (i.e. the initial clip) to find a triangle that is guaranteed to lie inside the polygon and then pick the centroid of that triangle. Meisters showed there are at least two ears for a polygon of the type Sneftel has, so this will always work.

Share this post


Link to post
Share on other sites

This topic is 3746 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this