Finding a random point within a body

Topics: User Forum
Oct 10, 2012 at 2:10 PM

I need to find a random point within a body. Does anyone have any suggestions for a fast and efficient way to do this?

I think that the best way would probably be to pull down it's fixtures and grab a random point from a random one of those. However I'm not quite sure how exactly to do this.

Thank you your help.

Oct 10, 2012 at 3:31 PM

Do you need a particular distribution from which to pull random points? Also note that if you have a small fixture and a big fixture and first you select randomly one of them and only then pick a random point the result will not reflect the difference in area. In other words it won't be uniform.

One of the ways to get a uniform distribution is to floodfill the shapes of each fixture (floodfill on a grid with some resolution). Put all flood-filled points in an array and pick one randomly.

Another way is to triangulate all fixtures thus reducing the problem to finding a random point in a triangle. Overlapping fixtures will be an issue.

For a "best" way you should probably read on Finite Element Method and Isoparametric Mapping.

For a fast way I'd just calculate the AABB of all fixtures, combine them and keep picking random points in a rectangle until one is inside the actual shapes and not between the actual shape and the aabb. Will work for more "rectangular" shapes and not so much for irregular shapes.

Another fast way - pick a random point on the AABB (or the rectangular border of the world). Shoot a ray towards the body's origin. Find where it intersects the body's fixtures. Pick a random point between the origin and the intersection. Will have issues with concave bodies as a ray can enter and exit more than once in a concave body.

Oct 10, 2012 at 6:14 PM

I would prefer a perfectly even distribution within each fixture. I will have neither overlapping fixtures nor concave bodies. I plan on first picking a random fixture (weighted with regards to their area) first before finding a random point on that fixture. I suppose for now I will just find a random point for that fixture based on the AABB and reroll it if it's outside. It won't be quite as efficient as I'd like but it should work well enough for what I'm doing.

Oct 10, 2012 at 6:32 PM

If your shapes are convex (which they should be to be used as collision primitives in Farseer) then you have a triangle between each pair of adjacent vertices and the body's origin (assuming no offset for the fixture). Then the problem is finding a random point in a triangle which is easy: