Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Uniformly Distribute Points inside Polygon

Subject: Uniformly Distribute Points inside Polygon

From: spiffyguy917@gmail.com

Date: 5 Jun, 2008 00:05:36

Message: 1 of 17

Hello..

I'm looking for a way to uniformly distribute N points inside a convex
polygon made from X points... I'm working in matlab and right now I'm
just breaking the polygon up into a m x n (such that m*n = N) grid,
selecting the mid point of each box and checking to see if that point
is inside the polygon. I'm wondering if anyone knows a method to
distribute all the points with the polygon evenly..

Thanks!

Subject: Uniformly Distribute Points inside Polygon

From: us

Date: 5 Jun, 2008 00:16:02

Message: 2 of 17

spiffyguy917@gmail.com:
<SNIP causing a mess inside a polygon...

can you show CSSM what you've done so far...
us

Subject: Uniformly Distribute Points inside Polygon

From: spiffyguy917@gmail.com

Date: 5 Jun, 2008 00:26:37

Message: 3 of 17

On Jun 4, 5:16=A0pm, "us " <u...@neurol.unizh.ch> wrote:
> spiffyguy...@gmail.com:
> <SNIP causing a mess inside a polygon...
>
> can you show CSSM what you've done so far...
> us

The exact code I can't copy over here.. but here are the basic
steps..

- I have 2 vectors, a and b, size X by 1, with the vertices of the
polygon...
- I find the minimums and maximums of the polygon and basically create
a square grid using linspace(xmin, xmax, num_points_in_x) and
linspace(ymin, ymax, num_points_in_y)
- I loop through and make coordinate pairs (x,y) and then I use the
inpolygon function to determine whether its inside the polygon and the
convhull function create the vectors for the polygon sides.
- If it is, I keep the point, otherwise I throw it out.

Basically I want to have ALL the points distributed uniformly inside
the polygon and honestly, i'm not sure where to begin.

Thanks for your help!

Subject: Uniformly Distribute Points inside Polygon

From: Roger Stafford

Date: 5 Jun, 2008 00:32:02

Message: 4 of 17

spiffyguy917@gmail.com wrote in message <15675137-8bde-4220-abea-
e9cc67b3694c@f36g2000hsa.googlegroups.com>...
> Hello..
>
> I'm looking for a way to uniformly distribute N points inside a convex
> polygon made from X points... I'm working in matlab and right now I'm
> just breaking the polygon up into a m x n (such that m*n = N) grid,
> selecting the mid point of each box and checking to see if that point
> is inside the polygon. I'm wondering if anyone knows a method to
> distribute all the points with the polygon evenly..
>
> Thanks!
-----------
  I have the feeling John D'Errico will have an instant answer to this question,
but until he shows up, here are my thoughts. You should subdivide the
polygon up into triangles and select each triangle in proportion to its area.
Within a triangle you can uniformly distribute using two 'rand' calls. If P1 =
(x1,y1), P2 = (x2,y2), and P3 = (x3,y3) are the three vertices of the triangle,
then choose P = (x,y) according as

 t = sqrt(rand); s = rand;
 P = (1-t)*P1 + t*((1-s)*P2+s*P3)

Roger Stafford

Subject: Uniformly Distribute Points inside Polygon

From: us

Date: 5 Jun, 2008 00:40:04

Message: 5 of 17

spiffyguy917@gmail.com:
<SNIP seems to have a recipe but doesn't start to cook...

> The exact code I can't copy over here...

why not? just copy/paste a simple, parsimonious skeleton of
what you got...

> i'm not sure where to begin...

well, if you (really) have some code, you should already be
past the beginning...

us

Subject: Uniformly Distribute Points inside Polygon

From: spiffyguy917@gmail.com

Date: 5 Jun, 2008 01:04:40

Message: 6 of 17

On Jun 4, 5:40=A0pm, "us " <u...@neurol.unizh.ch> wrote:
> spiffyguy...@gmail.com:
> <SNIP seems to have a recipe but doesn't start to cook...
>
> > The exact code I can't copy over here...
>
> why not? just copy/paste a simple, parsimonious skeleton of
> what you got...
>
> > i'm not sure where to begin...
>
> well, if you (really) have some code, you should already be
> past the beginning...
>
> us

Here's the basic skeleton...

-Assume a and b are vectors to the polygon in a cartesian plane, a has
the x direction points and b has the y direction points
-Assume m points in the x direction
-Assume n points in the y direction
----------------------
x_min =3D min(a);
x_max =3D max(a);
y_min =3D min(b);
y_max =3D max(b);

x_points =3D linspace(x_min,x_max,m);
y_points =3D linspace(y_min,y_max,n);

indx =3D 1;

for i=3D1:m
   for j =3D 1:n
      points(indx,1) =3D x_points(i);
      points(indx,2) =3D y_points(j);
      points(indx,3) =3D 0;
      indx =3D indx + 1;
   end
end


for i=3D1:length(points)
   if(inpolygon(points(i,1),points(i,2),a,b))
      points(i,3) =3D 1;
   end
end
--------------

This is obviously just a hit or miss way to get the points within the
polygon... I guess breaking the polygon into equal area'ed triangles
and the picking its center point might do the trick... Still thinking
about that one.

Thanks again for all your help... this is the first time I've posted
up on this kind of forum so I'm kind of new :)

Subject: Uniformly Distribute Points inside Polygon

From: us

Date: 5 Jun, 2008 01:21:03

Message: 7 of 17

spiffyguy917@gmail.com:
<SNIP has become a good CSSMer...

one of the solutions might look like this

% the data
     x=[1,2,3,4,1];
     y=[1,2 4 2 1];
     nx=50;
     ny=25;
% the engine
     xp=linspace(min(x),max(x),nx);
     yp=linspace(min(y),max(y),ny);
     [xd,yd]=meshgrid(xp,yp);
     ip=inpolygon(xd,yd,x,y);
% the result
     plot(x,y,'linewidth',2);
     line(xd(ip),yd(ip),'marker','.','linestyle','none');

us

Subject: Uniformly Distribute Points inside Polygon

From: matt dash

Date: 5 Jun, 2008 01:28:02

Message: 8 of 17

Obviously there's no closed form solution for this, so
whatever you do is going to be iterative. You could probably
use some kind of optimization routine to maximize some
measure of "uniformness"... I believe this type of problem
is generally known as sphere packing (circle packing in your
case, with the points at the center of the circle) Try
googling that and maybe you can find an algorithm. You'll
have to consider whether you want points on the edge of the
polygon, or whether you want them uniformly spaced from each
other *and* the edges.

If you only need a "good enough" answer, you might try
calculating the ratio R of the polygon to the square
containing the polygon, then generate a uniform grid of N/R
points over the square and throw out those that arent in the
polygon... this will yield approximately N points in the
polygon.

Subject: Uniformly Distribute Points inside Polygon

From: Roger Stafford

Date: 5 Jun, 2008 01:59:03

Message: 9 of 17

spiffyguy917@gmail.com wrote in message <de4780ca-dfdc-4d69-
b457-14cd0f50ea75@w7g2000hsa.googlegroups.com>...
> .......
> -Assume a and b are vectors to the polygon in a cartesian plane, a has
> the x direction points and b has the y direction points
> -Assume m points in the x direction
> -Assume n points in the y direction
> ......
--------
  When I first read your question, I interpreted it as asking for a random
distribution of points within the polygon with a statistically uniform distribution
therein. That is what I described. If you want an actually uniform distribution of
a meshwork of points, then what you are doing is probably as good a method as
any. Sorry for the misinterpretation.

Roger Stafford

Subject: Uniformly Distribute Points inside Polygon

From: spiffyguy917@gmail.com

Date: 5 Jun, 2008 02:08:46

Message: 10 of 17

On Jun 4, 6:59=A0pm, "Roger Stafford"
<ellieandrogerxy...@mindspring.com.invalid> wrote:
> spiffyguy...@gmail.com wrote in message <de4780ca-dfdc-4d69-
>
> b457-14cd0f50e...@w7g2000hsa.googlegroups.com>...> .......
> > -Assume a and b are vectors to the polygon in a cartesian plane, a has
> > the x direction points and b has the y direction points
> > -Assume m points in the x direction
> > -Assume n points in the y direction
> > ......
>
> --------
> =A0 When I first read your question, I interpreted it as asking for a rand=
om
> distribution of points within the polygon with a statistically uniform dis=
tribution
> therein. =A0That is what I described. =A0If you want an actually uniform d=
istribution of
> a meshwork of points, then what you are doing is probably as good a method=
 as
> any. =A0Sorry for the misinterpretation.
>
> Roger Stafford

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!

Subject: Uniformly Distribute Points inside Polygon

From: ImageAnalyst

Date: 5 Jun, 2008 02:40:47

Message: 11 of 17

On Jun 4, 8:05=A0pm, spiffyguy...@gmail.com wrote:
> Hello..
>
> I'm looking for a way to uniformly distribute N points inside a convex
> polygon made from X points... I'm working in matlab and right now I'm
> just breaking the polygon up into a m x n (such that m*n =3D N) grid,
> selecting the mid point of each box and checking to see if that point
> is inside the polygon. I'm wondering if anyone knows a method to
> distribute all the points with the polygon evenly..
>
> Thanks!

------------------------------------------------------------
Well since I'm an image analyst I tend to think of things in terms of
images. Why not just turn the polygon into a binary image through the
use of poly2mask (in the image processing toolbox). Then find and
count the X points in the polygon using the find() command. Then take
your N points (assuming it's less than X) and distribute them along
your X points. For a simple example, say you have 1000 points in the
polygon and you want to distribute 100 points evenly throughout (not
uniformly random as I can see from reading the other messages, but
that's what I first thought), so you'd go through the list and every
10th point in the polygon (as found by the find function), you'd set a
pixel in your output image. Depending on the shapes of your sides,
the points may not be in a perfect rectangular or hexagonal matrix
(are you requiring that?) but it would be distributed evenly
horizontally. You could do the whole thing in 3 lines, one for
poly2mask, one for find, and one for the assignment. If you require a
specific pattern such as rectangular, square, hexagonal/triangular,
then that can be done too with a different algorithm but you have to
specify the pattern (then determine the pattern spacings, lay down the
pattern, and fine tune it a bit near the edges of the polygon to get
the EXACT number N).
Regards,
ImageAnalyst

Subject: Uniformly Distribute Points inside Polygon

From: Roger Stafford

Date: 5 Jun, 2008 04:49:02

Message: 12 of 17

spiffyguy917@gmail.com wrote in message
<549a15b6-4c6f-48d1-95bf-06d2e0c4844c@e53g2000hsa.googlegroups.c
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

Subject: Uniformly Distribute Points inside Polygon

From: John D'Errico

Date: 5 Jun, 2008 09:07:02

Message: 13 of 17

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in
message <g27r7u$gpb$1@fred.mathworks.com>...
> spiffyguy917@gmail.com wrote in message
> <549a15b6-4c6f-48d1-95bf-
06d2e0c4844c@e53g2000hsa.googlegroups.c
> 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

Subject: Uniformly Distribute Points inside Polygon

From: spiffyguy917@gmail.com

Date: 5 Jun, 2008 18:06:54

Message: 14 of 17

On Jun 5, 2:07=A0am, "John D'Errico" <woodch...@rochester.rr.com> wrote:
> "Roger Stafford" <ellieandrogerxy...@mindspring.com.invalid> wrote in
> message <g27r7u$gp...@fred.mathworks.com>...> spiffyguy...@gmail.com wrote=
 in message
> > <549a15b6-4c6f-48d1-95bf-
>
> 06d2e0c48...@e53g2000hsa.googlegroups.c
>
>
>
>
>
> > 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!
> > --------------
> > =A0 Since you are still interested in filling triangles, I thought I wou=
ld fix up
> this
> > little demonstration of filling a pentagon with a large number of random=

> > points with statistically uniform area distribution within the pentagon.=
 =A0It
> > divides up the pentagon into three triangles and fills them randomly in
> > accordance with the scheme I mentioned previously.
>
> > =A0 It is not an absolutely uniform filling in the sense of, say, packin=
g spheres
> > into a jar, but when used with a large number of points, it has a unifor=
mity
> of
> > a different kind. =A0Equal areas are likely to be filled with a nearly e=
qual
> number
> > of points. =A0The larger the number of points, the more uniform it will =
look in
> a
> > statistical sense.
>
> > =A0 Just run the following. =A0The pentagon here is cut into the three t=
riangles:
> > p1p2p3, p1p3p4, and p1p4p5. =A0They are randomly selected in proportion
> to
> > their respective areas. =A0Within each triangle the points are randomly =
filled in
> a
> > statistically uniform manner.
>
> > clear
> > n =3D 4096; % <-- Choose the desired number of points, preferably large
> > p1 =3D [1.1,1.9]; p2 =3D [4.2,1.2]; p3 =3D [6.3,2.9];
> > p4 =3D [4.8,5.1]; p5 =3D [0.9,3.8]; % The five pentagon vertices
>
> > a23 =3D abs(det([p2-p1;p3-p1])); % Twice the triangles' areas
> > a34 =3D abs(det([p3-p1;p4-p1]));
> > a45 =3D abs(det([p4-p1;p5-p1]));
> > sa =3D a23+a34+a45;
> > a =3D a23/sa; b =3D (a23+a34)/sa; % Normalize cumulative areas
> > r =3D rand(n,1); % Use this to select the triangle
> > s =3D sqrt(rand(n,1)); s2 =3D [s,s]; % Use these to select
> > t =3D rand(n,1); t2 =3D [t,t]; % =A0points within a triangle
> > pa =3D (r<=3Da)*p2 + ((a<r)&(r<=3Db))*p3 + (b<r)*p4; % Generalized verti=
ces
> > pb =3D (r<=3Da)*p3 + ((a<r)&(r<=3Db))*p4 + (b<r)*p5;
> > p =3D (1-s)*p1 + s2.*((1-t2).*pa + t2.*pb); % The random points
>
> > c =3D [p1;p2;p3;p4;p5;p1]; % Plot the pentagon in red
> > plot(c(:,1),c(:,2),'ro',c(:,1),c(:,2),'r-',...
> > =A0 =A0 =A0p(:,1),p(:,2),'y.') % Plot random points as yellow dots
> > axis equal
>
> > =A0 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- Hide quoted text -
>
> - Show quoted text -

Thank you so much for all your help everyone. I will try both the
image based and the triangle based ideas... I only need a few points
so I think I will try this delaunay algorithm to break the polygon
into N triangles (where N is the number of points wanted inside the
triangle, usually less than 20) and then just place the point in the
center of the triangle... Thanks again, I really appreciate it!

Subject: Uniformly Distribute Points inside Polygon

From: ImageAnalyst

Date: 8 Jun, 2008 14:06:55

Message: 15 of 17

On Jun 4, 10:40=A0pm, ImageAnalyst <imageanal...@mailinator.com> wrote:
> On Jun 4, 8:05=A0pm, spiffyguy...@gmail.com wrote:
>
> > Hello..
>
> > I'm looking for a way to uniformly distribute N points inside a convex
> >polygonmade from X points... I'm working in matlab and right now I'm
> > just breaking thepolygonup into a m x n (such that m*n =3D N) grid,
> > selecting the mid point of each box and checking to see if that point
> > is inside thepolygon. I'm wondering if anyone knows a method to
> > distribute all the points with thepolygonevenly..
>
> > Thanks!
>
> ------------------------------------------------------------
> Well since I'm an image analyst I tend to think of things in terms of
> images. =A0Why not just turn thepolygoninto a binary image through the
> use of poly2mask (in the image processing toolbox). =A0Then find and
> count the X points in thepolygonusing the find() command. =A0Then take
> your N points (assuming it's less than X) and distribute them along
> your X points. =A0For a simple example, say you have 1000 points in thepol=
ygonand you want to distribute 100 points evenly throughout (not
> uniformly random as I can see from reading the other messages, but
> that's what I first thought), so you'd go through the list and every
> 10th point in thepolygon(as found by the find function), you'd set a
> pixel in your output image. =A0Depending on the shapes of your sides,
> the points may not be in a perfect rectangular or hexagonal matrix
> (are you requiring that?) but it would be distributed evenly
> horizontally. =A0You could do the whole thing in 3 lines, one for
> poly2mask, one for find, and one for the assignment. =A0If you require a
> specific pattern such as rectangular, square, hexagonal/triangular,
> then that can be done too with a different algorithm but you have to
> specify the pattern (then determine the pattern spacings, lay down the
> pattern, and fine tune it a bit near the edges of thepolygonto get
> the EXACT number N).
> Regards,
> ImageAnalyst

---------------------------------
Something very similar to the original posters question was the March
11, 2008 "Doug's pick of the week"
http://blogs.mathworks.com/pick/page/3/

Subject: Uniformly Distribute Points inside Polygon

From: Adrian Badoiu

Date: 24 May, 2010 19:49:04

Message: 16 of 17

> 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.

And what if I have to fill-in a rectangle with random uniformly distributed points?
Thanks!

Subject: Uniformly Distribute Points inside Polygon

From: Roger Stafford

Date: 25 May, 2010 00:46:08

Message: 17 of 17

"Adrian Badoiu" <abadoiu@gmail.com> wrote in message <htel7g$rjr$1@fred.mathworks.com>...
> And what if I have to fill-in a rectangle with random uniformly distributed points?
> Thanks!
- - - - - - -
  If you have a rectangle you should ignore all the stuff about triangulation in this thread. You can fill the rectangle uniformly with just two calls to 'rand'. If P1 = (x1,y1), P2 = (x2,y2), P3 = (x3,y3) and P4 = (x4,y4) are four vertices of your rectangle (where P2-P1 = P3-P4 and dot(P2-P1,P3-P1) = 0 must hold), then do this:

% Create random rectangle
P1 = randn(1,2); P2 = randn(1,2);
P4 = P1 + 2*rand*(P2-P1)*[0 1;-1 0]; % Right angle corners
P3 = P4-P1+P2;

% Random fill points
n = 4096; % <-- choose the total number of fill points
s = rand(n,1); t = rand(n,1);
P = repmat(P1,n,1) + s*(P2-P1)+t*(P4-P1);

% Plot it
R = [P1;P2;P3;P4;P1];
plot(R(:,1),R(:,2),'m-',P(:,1),P(:,2),'y.')
axis equal

That should uniformly fill your rectangle with points.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us