Skip to main content
GameDev.net gamedev.net
🔒 Locked

Generating polygons

Started by NMO Jan 26, 2008 at 2:13 PM 10 replies 1.2k views
Original Post
NMO
NMO
Hi, i've been looking for an algorithm that generates randomly simple polygons. There are no vertices given this means the vertices have to be randomly calculated. A polygon can be either convex or concave. Thanks in advance.
jezham
jezham
Guess just find 3+ random verts and find the silhouette.
NMO
NMO
??
I can't imagine what you mean.
jezham
jezham
------
|\....|
|.\...|
|..\..|
|...\.|
|....\|
------

Silhouette of above shape would ignore the diagonal, as that edge was used twice.

=

------
|.....|
|.....|
|.....|
|.....|
|.....|
------
shadowisadog
shadowisadog
I don't really know what you are talking about but if I had to generate a random polygon, I would do the following (in psedocode)

Side=Rand(3,12)
Size=Rand(10,100)
PolyAng=360/Side
Midx=ScreenWid/2
Midy=ScreenHei/2

For A=0 to Side

X=Midx+Cos(PolyAng*A)*Size
Y=Midy+Sin(PolyAng*A)*Size
X2=Midx+Cos(PolyAng*(A+1))*Size
Y2=Midy+Sin(PolyAng*(A+1))*Size

Line(X,Y,X2,Y2)

End


With some modifaction by reducing the size by a half if A is odd, we can make stars also: instead of *Size it would be like *(Size/(A%2+1)) or something similar..
NMO
NMO
Ok thanks for your answers.

I've added some comments to the code to give my interpretation to every single line however I'm not sure if that is correct:

Side=Rand(3,12) // to calculate a random angle
Size=Rand(10,100) // to scale the polygon with a given factor
PolyAng=360/Side // to calculate the angle
Midx=ScreenWid/2 // to center the polygon in the middle of the screen
Midy=ScreenHei/2 // --

For A=0 to Side // I can't imagine for what A is

X=Midx+Cos(PolyAng*A)*Size // to calculate the next startpoint
Y=Midy+Sin(PolyAng*A)*Size // --
X2=Midx+Cos(PolyAng*(A+1))*Size // to calculate the next endpoint
Y2=Midy+Sin(PolyAng*(A+1))*Size // --

Line(X,Y,X2,Y2) // draw the line

As mentioned with the comment I don't know what A is...
shadowisadog
shadowisadog
Well basically how my code works is that I take a circle and only sample very specific points on that circle. When I divide 360 by the number of sides, I get a value... Let's say I had 5 sides... 360/5=72..

Now A runs from 0 to the number of sides (5) or in other words it will run a loop at point 0, 1, 2, 3, and 4.

At point 0 we multiply by A and get 0. This is the first location of our point on the circle. At point 1 we multiply by 1 and get 72 or the second location. At point 2 we multiply by 2 and get 144... Ect at point 4 we have 288. Now if we were to go on to point 5 we would have 360 but remember the fact that in this case 0 is equal to 360..

Oh and one thing I forgot to do in my code was convert degrees into radians so make sure you do that by multiplying by (Pi/180)...
shadowisadog
shadowisadog
Here is some very simple C# code to do what you want:

using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;namespace PolyDraw{    public partial class Form1 : Form    {        public Form1()        {            InitializeComponent();        }        private void Form1_Paint(object sender, PaintEventArgs e)        {            Random mRand = new Random((int)DateTime.Now.Ticks);            int Sides = mRand.Next(3, 12);            int Size = mRand.Next(10, 100);            int PolyAng = 360 / Sides;            int Midx = Form1.ActiveForm.Width / 2;            int Midy = Form1.ActiveForm.Height / 2;            PointF [] mPoints=new PointF[Sides];            for (int a = 0; a<Sides; a++)            {                mPoints[a].X=(float)(Midx + Math.Cos((PolyAng * a) * (Math.PI / 180)) * Size);                mPoints[a].Y=(float)(Midy + Math.Sin((PolyAng * a) * (Math.PI / 180)) * Size);            }            e.Graphics.FillPolygon(Brushes.Blue,mPoints);        }        private void Form1_MouseClick(object sender, MouseEventArgs e)        {            if (e.Button == MouseButtons.Left)                this.Refresh();        }    }}
JakeM
JakeM
Why don't you just generate a point cloud? Total count and position can be random.
Then generate a convex hull from it.
arithma
arithma
The sin/cos algo wouldn't give you the whole range of possible polygons. It would be desirable though in case u wanted to triangulate the polygon as u can choose the origin as a common vertex and iterate over the edges to make the triangles.
[ my blog ]
NMO
NMO
Really, really nice idea.

Thanks for your effort and for the code.

By the way: By generating random size in the loop you can simply generate concave polygons too....
shadowisadog
shadowisadog
Quote:
Original post by arithma
The sin/cos algo wouldn't give you the whole range of possible polygons. It would be desirable though in case u wanted to triangulate the polygon as u can choose the origin as a common vertex and iterate over the edges to make the triangles.


Right, I have actually done this before back when I was playing around with custom vertex buffers to make dynamic 3d models.

I know it won't give all possible polygons, but it is an algorithm I have used to create standard polygons and it is better then nothing.

Quote:
Orginal post by JakeM
Why don't you just generate a point cloud? Total count and position can be random.
Then generate a convex hull from it.


Can you please elaborate on how you would go about doing something like this?

Quote:
Original post by NMO
Really, really nice idea.

Thanks for your effort and for the code.

By the way: By generating random size in the loop you can simply generate concave polygons too....


Your welcome :) .

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.