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

Recommended Posts

I am wondering about something. I want to choose random points over a convex polygon. By averaging the coordinates of the vertices with random weights (random linear combination), is it guaranteed that the point is going to be inside the convex n-gon? Is that guarantee present at least for triangles? What is the best technique to obtain random points on a polygon?

Share on other sites
http://apodeline.free.fr/FAQ/CGAFAQ/CGAFAQ-7.html

Quote:
 7.5 : How can I generate a random point inside a triangle?Use barycentric coordinates (see item 53) . Let A, B, C be the three vertices of your triangle. Any point P inside can be expressed uniquely as P = aA + bB + cC, where a+b+c=1 and a,b,c are each >= 0. Knowing a and b permits you to calculate c=1-a-b. So if you can generate two random numbers a and b, each in [0,1], such that their sum <=1, you've got a random point in your triangle. Generate random a and b independently and uniformly in [0,1] (just divide the standard C rand() by its max value to get such a random number.) If a+b>1, replace a by 1-a, b by 1-b. Let c=1-a-b. Then aA + bB + cC is uniformly distributed in triangle ABC: the reflection step a=1-a; b=1-b gives a point (a,b) uniformly distributed in the triangle (0,0)(1,0)(0,1), which is then mapped affinely to ABC. Now you have barycentric coordinates a,b,c. Compute your point P = aA + bB + cC.Reference: [Gems I], Turk, pp. 24-28.

For a general polygon, perhaps add points randomly (from a total set) based on area of each triangle and total polygon area (ratio):

Example: polygon composed of 2 triangles-

TotalArea = AreaTri1 + AreaTri2

pointCount1 = numPoints*AreaTri1/TotalArea
pointCount2 = numPoints*AreaTri2/TotalArea

Generate random points for each triangle using the above counts.

• Game Developer Survey We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 30
• 9
• 16
• 22