Re: Uniformly Distribute Points inside Polygon

"Roger Stafford" <ellieandrogerxyzzy@xxxxxxxxxxxxxxxxxxxxxx> wrote in
message <g27r7u$gpb$1@xxxxxxxxxxxxxxxxxx>...
spiffyguy917@xxxxxxxxx wrote in message
<549a15b6-4c6f-48d1-95bf-
06d2e0c4844c@xxxxxxxxxxxxxxxxxxxxxxxxxx
om>...
Thanks for all your feedback everyone... While I might be able to get
this meshgrid of points to work, I'd ideally want to specify an
*exact* number of points inside the polygon. With the meshgrid, I
won't know how many points will fall into the polygon beforehand. I
think the triangle method is the best way to do it so far, but I
haven't exactly figured out how to implement it... Seems like it'd be
an iterative process depending on the number of points and creating
that same number of triangles.. Any more insight into how to do this?
Thanks again!
--------------
Since you are still interested in filling triangles, I thought I would fix up
this
little demonstration of filling a pentagon with a large number of random
points with statistically uniform area distribution within the pentagon. It
divides up the pentagon into three triangles and fills them randomly in
accordance with the scheme I mentioned previously.

It is not an absolutely uniform filling in the sense of, say, packing spheres
into a jar, but when used with a large number of points, it has a uniformity
of
a different kind. Equal areas are likely to be filled with a nearly equal
number
of points. The larger the number of points, the more uniform it will look in
a
statistical sense.

Just run the following. The pentagon here is cut into the three triangles:
p1p2p3, p1p3p4, and p1p4p5. They are randomly selected in proportion
to
their respective areas. Within each triangle the points are randomly filled in
a
statistically uniform manner.

clear
n = 4096; % <-- Choose the desired number of points, preferably large
p1 = [1.1,1.9]; p2 = [4.2,1.2]; p3 = [6.3,2.9];
p4 = [4.8,5.1]; p5 = [0.9,3.8]; % The five pentagon vertices

a23 = abs(det([p2-p1;p3-p1])); % Twice the triangles' areas
a34 = abs(det([p3-p1;p4-p1]));
a45 = abs(det([p4-p1;p5-p1]));
sa = a23+a34+a45;
a = a23/sa; b = (a23+a34)/sa; % Normalize cumulative areas
r = rand(n,1); % Use this to select the triangle
s = sqrt(rand(n,1)); s2 = [s,s]; % Use these to select
t = rand(n,1); t2 = [t,t]; % points within a triangle
pa = (r<=a)*p2 + ((a<r)&(r<=b))*p3 + (b<r)*p4; % Generalized vertices
pb = (r<=a)*p3 + ((a<r)&(r<=b))*p4 + (b<r)*p5;
p = (1-s)*p1 + s2.*((1-t2).*pa + t2.*pb); % The random points

c = [p1;p2;p3;p4;p5;p1]; % Plot the pentagon in red
plot(c(:,1),c(:,2),'ro',c(:,1),c(:,2),'r-',...
p(:,1),p(:,2),'y.') % Plot random points as yellow dots
axis equal

You will note that there is no trace left in the distribution of the dividing
lines between triangles, and each triangle is filled uniformly area-wise in a
statistical sense.

Roger,

(Sorry, I was out playing bridge yesterday.)

Yes, this is exactly the approach I take. In
fact, it is the general approach that my code
uses that generates uniform random points
inside a general object in n-dimensions.

Compute the area/volume of each simplex,
then assign points to them randomly with
probability defined by their area relative to
the total area. Within each simplex, I use a
slightly different method of generating
random points, but it is probably equivalent
mathematically to the one you have given,
since it starts out similarly.

Of course, you need a triangulation of the
polygon, but as long as the polygon is a
convex one, this is trivial with delaunay. If
it is not, then ear clipping methods seem
the simplest.

John
.

Relevant Pages

  • Re: outline polygon of overlapping triangles
    ... where I can get an algorithm that creates ... If you want the polygon that is the union of the ... triangles, the suggestion to use Alan Murtha's ...
    (comp.graphics.algorithms)
  • Re: From Triangle tiles to convex Polygons.
    ... I start out with a complicated non-convex polygon with holes. ... it into OpenGL GLU, and I get back a few hundred triangles that ... problem is that a few hundred triangles is way too many, ... I think you can do this by taking your triangulation and merge triangles to build multiple convex polygons from it. ...
    (comp.graphics.algorithms)
  • Re: From Triangle tiles to convex Polygons.
    ... all internal edges that don't have a connection to a convex vertex. ... You don't get the minimal convex decomposition that way. ... like metric to avoid all the long and thin triangles. ... the polygon with holes to a simple polygon. ...
    (comp.graphics.algorithms)
  • Re: How to get trinagles from a polygon?
    ... For arbitrary triangles there are a lot of non trivial algorithms you can ... > If the polygon is concave, start at a vertex and read the ... > other vertexes in succession (clock wise or anti-clock wise, ... > If it is convex, the previous process will generally fails (it may ...
    (microsoft.public.win32.programmer.directx.managed)
  • Re: polygonal area on a sphere
    ... polygon on the earth's surface where I know the coordinates (lat/lon) ... I must find a point internal to the polygon and then ... consider all the triangles? ... the calculus of the areas isn't very ...
    (sci.geo.satellite-nav)