How would I get random positions that are inside 4 or more positions?
Decompose the poly into triangles, pick a random triangle with a chance according to its area, then pick a random spot within the triangle. Google for each of those steps.
3 Likes
Are your polygons always planar? i.e. can you project them onto a common plane without changing their area?
Do you know the shapes ahead of time? If so, you could make some tessellated meshes (in Blender or something) for these shapes. Then you can just pick a vertex index at random and use that position.
I usually prefer to rely on super-simple, data-oriented solutions rather than using clever algorithms, though. 
The image above is probably misleading. There is no mesh, the image was an example of positions with one pointing to the next, except for the last one which points to the first one. These positions are created at runtime (the player drawing a shape for entities to go inside.)
If it is just positions does the y axis need to be uniform?
bump
-
Same concept. Break the positions down into triangles. Get a random position in one of the triangles.
2 Likes
Yes, that’s the most reliable method. You can do a more naive approach of choosing a random point in the bounding box of the shape and then test if the point is in the shape or not. If not pick a new random position and repeat. This however can have very bad runtime performance depending on the ratio of the area inside and outside the shape. Also checking of a point is in a polygon does already somewhat breaks the shape into triangles that connect to the origin.
So that’s usually not worth it. How easy it is to break an arbitrary polygon down into triangles highly depends on the potential shapes. Convex polygons are the easiest. However when the user draws it manually you most likely can not assume that. Convex polygons require a bit more analysis and the easiest solution is usually the ear-clipping algorithm.
Note that a pure polygon / polyline could intersect itself in which case the concept of inside and outside becomes muddy / unclear. At this point we have to deal with positive and negative area. So it’s best to detect this or prevent the user from drawing self-intersecting shapes. This happens with such shapes:
Once you have a bunch of triangles, in order to pick a uniformly distributed point across all triangles, you first have to pick a triangle. This should be a weighted pick based on the area of the triangles. You can calculate the area of a triangle by taking the cross product of two of the sides of a triangle and take the magnitude of the resulting vector and divide it by 2.
Once you have a triangle you can use barycentric coordinates to pick a random point inside that triangle. That’s the gist of it.
3 Likes
Here’s some code
float getTriArea(Vector3 p1, Vector3 p2, Vector3 p3) => .5f * Vector3.Cross(p2 - p1, p3 - p1).magnitude;
float[] getAreas(IList<Vector3> p) {
var tc = p.Count / 3;
var r = new float[tc];
for(int i = 0; i < tc; i++) {
var x = 3 * i;
tc[i] = getTriArea(p[x], p[x+1], p[x+2]);
}
return r;
}
Here’s how to make a weighed pick (Fast weighted random selection).
And then you find random barycentric coordinates.
Vector3 getRandomPoint(Vector3 p1, Vector3 p2, Vector3 p3, Func<float> random01) {
float u = random01(), v = random01();
if(u + v >= 1f) { u = 1f - u; v = 1f - v; } // makes sure point is inside
return u * (p2 - p1) + v * (p3 - p1) + p1;
}
All bundled like this in the end (pseudo)
var p = ... // list of point triplets
var areas = getAreas(tris);
var ti = 3 * Chooser.ChooseIndex(areas);
var rp = getRandomPoint(p[ti], p[ti+1], p[ti+2], () => UnityEngine.Random.value);
This example assumes ordered triplets (with some sort of triangulation finish on the polygon, like ear clipping as mentioned above or Delaunay).
Edit: oops, forgot to extract magnitude in area computation (and fixed indices in getAreas).
1 Like