Re: Uniformly Distribute Points inside Polygon

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 Stafford

.

Relevant Pages

  • Re: Uniformly Distribute Points inside Polygon
    ... 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. ... Within each triangle the points are randomly filled in a statistically uniform manner. ...
    (comp.soft-sys.matlab)
  • Re: Uniformly Distribute Points inside Polygon
    ... With the meshgrid, I ... won't know how many points will fall into the polygon beforehand. ... Since you are still interested in filling triangles, I thought I would fix up ... It is not an absolutely uniform filling in the sense of, say, packing spheres ...
    (comp.soft-sys.matlab)
  • Re: Using half-planes to determine point location
    ... pentagon itself, and 5 diagonals, a.k.a. the "pentagram". ... form not just 10 triangles, but 15 triangles, plus one pentagon, 5 ... How the results of the half-plane test uniquely relate to the specific ...
    (comp.graphics.algorithms)
  • Re: Why no pentagon crystal lattices?
    ... "Can you explain why there are no crystals which have the shape ... (Triangles, squares, and hexagons are common in ... The pentagon can tesselate if it ...
    (sci.physics)
  • Using half-planes to determine point location
    ... Connect the vertices of a pentagon with five lines. ... Determine which triangles contain that point using a ... How the results of the half-plane test uniquely relate to the specific ... float fAB ...
    (comp.graphics.algorithms)