Thread Subject: Randomly generated convex polygon

Hi there! I am a newbie... :)

Could anyone help me out: I am trying to create a randomly generated convex polygon. I have succeeded in creating a randomly generated polygon using rand but I cannot keep it convex?

Thanx for any help!

In article <1254637.1189974898598.JavaMail.jakarta@nitrogen.mathforum.org>,
Yanis <jaana.nykanen@gmail.com> wrote:

>Could anyone help me out: I am trying to create a randomly generated
>convex polygon. I have succeeded in creating a randomly generated
>polygon using rand but I cannot keep it convex?

Pick a centre. You might as well use (0,0). Now generate by polar
coordinates with consistantly increasing angle (clockwise or
counterclockwise doesn't matter, as long as you are consistant). By
induction, the polygon will be convex provided that for each new point,
P(n), a line segment to point P(n-2) does not pass "outside" (relative
to the centre) the point P(n-1). You can generate the first three
points without checking, since a triangle is always convex. (Mind you,
a poor choice of third point could badly constrain where the rest must
be.)

If you need to generate N points, then for the angles you can use
sort(rand(1,N)) * 2 * pi . Actually, you can fix the angle to the first
point as 0 and generate N-1 random angles instead, since you can rotate
and translate the generated polygon.

A good question about the scheme of sort(rand(1,N)) * 2 * pi for
the angles is whether it can ever get "stuck". The answer to that
is that I lied a little when I said "by induction": the induction
can fail at the last point because the closure back to the first
point must be convex with respect to a segment drawn between the
last point and the second point, and similarily projecting between
the second last point and the first point must be convex with
respect to the last point. But until you get to those last two points,
you can always find a radius that will continue the convexness
(provided that you never generate a radius of 0!). But I don't make
any promises that with random angles and random radii that you
can always close the polygon (gotta leave some parts for you
to work out the constraints on ;-) )
--
  Prototypes are supertypes of their clones. -- maplesoft

In article
<1254637.1189974898598.JavaMail.jakarta@nitrogen.mathforum.org>, Yanis
<jaana.nykanen@gmail.com> wrote:

> Hi there! I am a newbie... :)
>
> Could anyone help me out: I am trying to create a randomly generated
convex polygon. I have succeeded in creating a randomly generated polygon
using rand but I cannot keep it convex?
>
> Thanx for any help!
-----------------------
  Yanis, here is another method for getting random convex polygons. Let n
be the desired number of vertices.

 a = rand(n,1);
 a = 2*pi*(rand+cumsum(a/sum(a))); % Generate n increasing angles
 r = rand(n,1);
 r = r/sum(r); % Generate random side lengths with sum of 1
 x = cumsum(r.*cos(a));
 y = cumsum(r.*sin(a)); % Lay out initial polygon
 r = cumsum(r);
 x = rand+[0;x-x(n)*r]; % Then adjust the vertices so that the
 y = rand+[0;y-y(n)*r]; % last point coincides with the first one

Then x and y are n+1 element vectors with the polygon's vertex coordinates
where the first and last elements are at the same location.

  The first six lines of the above code generate a series of successively
increasing random angles, a, spanning a range of 2*pi and randomly varying
side lengths, r. The corresponding vertex coordinates, x, and y, are
computed and would represent a convex polygon, except for the fact that
the first and last points will not in general coincide. The last three
lines adjusts the position of each point in the opposite direction of the
vector difference between the last to first points so as to bring these
together and with a relative change in successive points in proportion to
the length of the segment connecting them. As a last step each vertex is
moved by the same random amount.

  I have been unable to prove rigorously that convexity is always
preserved, but what analysis I have performed makes it seem likely that it
is. Repeated trials have borne this out.

Roger Stafford

Hi,

try this :

x=rand(25,1);
y=rand(25,1);
K = convhull(x,y) ;

figure
plot(x(K),y(K),'r-')

Jérôme

In article <fcmfeu$9rj$1@news.netfinity.fr>, Jerome Briot
<dutmatlab@yahoo.fr> wrote:

> Hi,
>
> try this :
>
> x=rand(25,1);
> y=rand(25,1);
> K = convhull(x,y) ;
>
> figure
> plot(x(K),y(K),'r-')
>
> Jérôme
--------------------
  Yes, I was on the point of suggesting that method yesterday, Jerome,
when it occurred to me that Yanis might get a poor "yield" that way. For
a large number, n, of desired polygonal vertices, I would judge one would
probably have to use at least order n^2 random points for the input to
'convhull' to achieve that. The great majority of points of a random
cloud are likely to find themselves in the interior of its convex hull and
therefore won't be present in the polygon.

Roger Stafford

In article <ellieandrogerxyzzy-1709071039060001@dialup-4.232.15.10.dial1.losangeles1.level3.net>,
Roger Stafford <ellieandrogerxyzzy@mindspring.com.invalid> wrote:

> Yanis, here is another method for getting random convex polygons.

Interesting method (what I've managed to understand of it). Experimentally,
though, with small number of sides, the observed number of 90 degree
angles is inordinately high. The evidence suggests that when the
random polygon would not normally close as convex, that the adjustment
done is likely to result in a 90 degree angle (or something visually
close to it 90 degrees, perhaps less sometimes.)

The conditions become rarer as the number of sides increases, it
appears, but I've seen it a few times even with n=20.

> a = rand(n,1);
> a = 2*pi*(rand+cumsum(a/sum(a))); % Generate n increasing angles

The rand() in the second statement threw me a bit, but I see now
that it is just a single random number, acting to impart a rotation
to the angles determined by cumsum(a/sum(a)) .

What is the last (i.e., maximum) value of cumsum(a/sum(a))? It'll
have to be 1. But what is the second last value? It turns out that
it can be arbitrarily small:

  Suppose you have N-1 random values each less than 1/t, followed
  by a single 1. Then sum(a) will be 1 + (N-1)/t, and the second
  last value in the cumsum will be (N-1)/t / (1+(N-1)/t). This
  simplifies to (N-1)/(t+N-1), from which we see that as t grows
  increasingly large (and thus increasingly improbable), the second
  last value can become decreasingly small. [Crosscheck: for t=1,
  the usual range for random numbers, (N-1)/(1+N-1) is (N-1)/N for
  the second last value, which is reasonable.] This particular
  sequence is, of course, improbable, but it does illustrate that
  we might expect some fairly wide gaps between the second last and last
  vertex.

For example, a test a moment ago generated
a = [0.33776 0.74589 0.16304 0.06549 0.84123]
cumsum(a/sum(a)) = [0.15685 0.50323 0.57894 0.60935 1];
The next test,
a = [0.13385 0.29837 0.613 0.12035 0.96812]
cumsum(a/sum(a)) = [0.062732 0.20257 0.48986 0.54627 1]
Second-last values around 0.71 are common; the 0.55 is the smallest
I've seen, by a fair bit. The 0.61 shows there are other patterns
that still lead to large gaps in the angles.
--
  Prototypes are supertypes of their clones. -- maplesoft

In article <fcn4l4$8hd$1@canopus.cc.umanitoba.ca>,
roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:

> In article
<ellieandrogerxyzzy-1709071039060001@dialup-4.232.15.10.dial1.losangeles1.level3.net>,
> Roger Stafford <ellieandrogerxyzzy@mindspring.com.invalid> wrote:
>
> > Yanis, here is another method for getting random convex polygons.
>
> Interesting method (what I've managed to understand of it). Experimentally,
> though, with small number of sides, the observed number of 90 degree
> angles is inordinately high. The evidence suggests that when the
> random polygon would not normally close as convex, that the adjustment
> done is likely to result in a 90 degree angle (or something visually
> close to it 90 degrees, perhaps less sometimes.)
>
> The conditions become rarer as the number of sides increases, it
> appears, but I've seen it a few times even with n=20.
>
> > a = rand(n,1);
> > a = 2*pi*(rand+cumsum(a/sum(a))); % Generate n increasing angles
>
> The rand() in the second statement threw me a bit, but I see now
> that it is just a single random number, acting to impart a rotation
> to the angles determined by cumsum(a/sum(a)) .
>
> What is the last (i.e., maximum) value of cumsum(a/sum(a))? It'll
> have to be 1. But what is the second last value? It turns out that
> it can be arbitrarily small:
>
> Suppose you have N-1 random values each less than 1/t, followed
> by a single 1. Then sum(a) will be 1 + (N-1)/t, and the second
> last value in the cumsum will be (N-1)/t / (1+(N-1)/t). This
> simplifies to (N-1)/(t+N-1), from which we see that as t grows
> increasingly large (and thus increasingly improbable), the second
> last value can become decreasingly small. [Crosscheck: for t=1,
> the usual range for random numbers, (N-1)/(1+N-1) is (N-1)/N for
> the second last value, which is reasonable.] This particular
> sequence is, of course, improbable, but it does illustrate that
> we might expect some fairly wide gaps between the second last and last
> vertex.
>
> For example, a test a moment ago generated
> a = [0.33776 0.74589 0.16304 0.06549 0.84123]
> cumsum(a/sum(a)) = [0.15685 0.50323 0.57894 0.60935 1];
> The next test,
> a = [0.13385 0.29837 0.613 0.12035 0.96812]
> cumsum(a/sum(a)) = [0.062732 0.20257 0.48986 0.54627 1]
> Second-last values around 0.71 are common; the 0.55 is the smallest
> I've seen, by a fair bit. The 0.61 shows there are other patterns
> that still lead to large gaps in the angles.
-------------------------
Hello Walter,

  I am unable to reproduce the results you refer to as to the
second-to-last value of a. Appending zero to the beginning, the
increments in a are intended to each be initially a random value in [0,1]
that is subsequently normalized to have a total sum of 1. Thus each
increment should have the same expected value, namely 1/n (for n polygon
vertices.) In particular, the difference between the last value, which is
1 because of the normalization, and the second-to-last should also average
out at 1/n. After the 'cumsum' operation, the a values represent total
angles from the beginning. In other words, the angles produced by a =
2*pi*(rand+cumsum(a/sum(a))) should be statistically uniformly distributed
over a certain range of 2*pi length, which is itself randomly determined,
if that can be considered a proper statement.

  I ran an experiment that repeated the two lines

 a = rand(n,1); % (n = 10)
 a = cumsum(a/sum(a));

one hundred thousand times and got an average of 0.90004749850469 for the
second-to-last a value, which is in good agreement with its expected
value. (I dropped the left 'rand' and the 2*pi multiplier here for
simplicity.) The idea behind this code was to give each of the n polygon
outer angles an expected value of pi+2*pi/n with a sum of precisely
(n+2)*pi as they must have, and it seems to me those two lines achieve
just that.

  The cases of 90 degree angles you refer to are the chance result of 'a'
increment values that are near pi/2, or more accurately, are near pi/2
after the final adjustment. For fairly small n this should happen
frequently, but for larger n it should be more infrequent. It is true
that the final adjustment will alter angles, but their sum remains fixed
and some should increase while others decrease. I see no particular
reason that pi/2 should be particularly favored in this respect unless one
is using an n value near 4.

  I don't follow your reasoning in, "Suppose you have N-1 random values
each less than 1/t, followed by a single 1. ...." There are actually N
(n) random values and they are not followed by a 1 to begin with, but
possess a 1 sum only after normalization. I think there must be some
misunderstanding here.

  The aspect of this method that bothers me the most is, as I mentioned
earlier, that I cannot rigorously prove that all polygons produced this
way will be convex after the final offset correction. The analysis I have
done leads me to suspect that it is actually impossible to produce a
non-convex polygon with this algorithm but the proof of this has eluded
me. Looked at from a practical point of view, in the many dozens of
polygons I have generated in tests, not one of them suffered from
non-convexity, as shown by a convexity test that utilized the full
16-decimal place accuracy of matlab. When n is large it is to be expected
that the polygon inner angles would often be close to pi, but I found none
that ever became equal to or greater than pi after adjustment.

Roger Stafford

In article <ellieandrogerxyzzy-1709072121120001@dialup-4.232.15.82.dial1.losangeles1.level3.net>,
Roger Stafford <ellieandrogerxyzzy@mindspring.com.invalid> wrote:

> I don't follow your reasoning in, "Suppose you have N-1 random values
>each less than 1/t, followed by a single 1. ...." There are actually N
>(n) random values and they are not followed by a 1 to begin with, but
>possess a 1 sum only after normalization. I think there must be some
>misunderstanding here.

Hypothesize that, randomly, the first N-1 'a' came out < 1/t,
and, that, randomly, the N'th random value came out near 1. This
is a *possible* situation -- increasingly unlikely as you increase
t for a given N, but *possible*. And in this situation, the
second last value of the cummulative normalized sum would be at
most (N-1)/(t+N-1); with t large, that would be small. This
establishes that it is *possible* for the second last value
of the cummulative sum to be arbitrarily small. The last value will
always be 1, of course, but the difference between the second last
value and 1 corresponds to the fraction of the diameter of the circle
that would have to be covered by the last side; until, that is, you
jigger the positions a bit to force convexness.

Certaintly over the long term we would expect the second last
cummulative entry to average out as (N-1)/N, but how the examples
I showed with 5 sides illustrated that final side closure of around 3/10
of the circle were common, 4/10 of the circle possible, and wider
gaps actually do happen, at least with small number of sides.

The visual effect for the user when these large gaps occur is that
an angle close to 90 degrees is observed more often than one would
expect by chance. It turns out not to be exactly 90 degrees; it
is sometimes a little more and sometimes a little less -- but visually
it looks like an artifact rather than chance.

When you pump the sides up to about 50, you get some very nice curves
seeming to appear; but in the range of about 5-8 sides especially,
the apparent artifact becomes visible.

The question here would be: could you re-examine the closure portion
and see what it would tend to produce if there did happen to be a large
angular gap between the second last and closing point?


Statistics...

T = 1000;

N = 5;

Gap=zeros(1,T);for K=1:T; A = rand(1,N); Gap(K) = A(end)/sum(A); end;
[mean(Gap), std(Gap), min(Gap), max(Gap)]
hist(Gap,40)

With rand('twister',1232), the mean is 0.20191, but the max is 0.67252 --
that is the first four points covered 1/3 of the angular range,
leaving the fifth side to extend over 2/3 of the angular range.

As I try over different N, I see different patterns (well, it is
random), but frequently the peak count is at -about- sqrt(2) times
the mean; this effect apparently reduces with larger T (e.g., 10000)
On the other hand, with T=10000, N=5, same seed, the largest gap
encountered is 0.77459, 3/4 of the arc to be closed by the final side.

If you look at the histograms, you can see that the distribution
is not a normal distribution. I consistantly (large or small T, large
or small N) see standard deviations more than half of the mean;
two standard deviations should account for 95.45% of the data, but
when the standard deviation is more than half of the mean, two standard
deviations would take us below zero. As T (the number of random trials)
increases, the distribution becomes more and more like
"a jagged-top box with a steep tail" -- right mean, but a more or
less flat distribution out to -roughly- sqrt(2) * the mean.
This will change the expectation of what the final closure of the
random polygon will tend to be like.
--
   I was very young in those days, but I was also rather dim.
   -- Christopher Priest

On Sep 17, 3:44 pm, ellieandrogerxy...@mindspring.com.invalid (Roger
Stafford) wrote:
> In article <fcmfeu$9r...@news.netfinity.fr>, Jerome Briot
>
> <dutmat...@yahoo.fr> wrote:
> > Hi,
>
> > try this :
>
> > x=3Drand(25,1);
> > y=3Drand(25,1);
> > K =3D convhull(x,y) ;
>
> > figure
> > plot(x(K),y(K),'r-')
>
> > J=E9r=F4me
>
> --------------------
> Yes, I was on the point of suggesting that method yesterday, Jerome,
> when it occurred to me that Yanis might get a poor "yield" that way. For
> a large number, n, of desired polygonal vertices, I would judge one would
> probably have to use at least order n^2 random points for the input to
> 'convhull' to achieve that. The great majority of points of a random
> cloud are likely to find themselves in the interior of its convex hull and
> therefore won't be present in the polygon.
>
> Roger Stafford

See extensive discussion at
http://www.ics.uci.edu/~eppstein/junkyard/random-n-gon.html

--Peter

A smaller question on the long and interesting discussion
on this topic.

Is there a way to create a similar random, convex polygon,
but have the sum of the sides not equal to 1?
That is, have the total area of the polygon or its
circumference equal to some user defined value ?

Thanks,
Daphne

In article <ffiqiu$7u1$1@fred.mathworks.com>,
Daphne <daphnew_too_nospam@yahoo.com> wrote:
>Is there a way to create a similar random, convex polygon,
>but have the sum of the sides not equal to 1?
>That is, have the total area of the polygon or its
>circumference equal to some user defined value ?

Generate a random polygon. Compute its area. Scale the
vertices by sqrt(required_area / computed_area)
--
  "There are some ideas so wrong that only a very intelligent person
  could believe in them." -- George Orwell

Works great. Thanks!


roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote in
message <ffisjm$er2$1@canopus.cc.umanitoba.ca>...
> In article <ffiqiu$7u1$1@fred.mathworks.com>,
> Daphne <daphnew_too_nospam@yahoo.com> wrote:
> >Is there a way to create a similar random, convex
polygon,
> >but have the sum of the sides not equal to 1?
> >That is, have the total area of the polygon or its
> >circumference equal to some user defined value ?
>
> Generate a random polygon. Compute its area. Scale the
> vertices by sqrt(required_area / computed_area)
> --
> "There are some ideas so wrong that only a very
intelligent person
> could believe in them." --
George Orwell