My question is this.. I am working on some clustering algorithms.. For this first i am experimenting with 2d shapes..
Given a particular area say 500sq units .. I need to generate random shapes for a particular area
say a Rect, Square, Triangle of 500 sq units.. etc .. Any suggestions on how i should go about this problem.. I am using R language..
It's fairly straightforward to do this for regular polygon.
The area of an n-sided regular polygon, with a circumscribed circle of radius R is
A = 1/2 nR^2 * sin((2pi)/n)
Therefore, knowing n and A you can easily find R
R = sqrt((2*A)/(n*sin((2pi)/n))
So, you can pick the center, go at distance R and generate n points at 2pi/n angle increments.
In R:
regular.poly <- function(nSides, area)
{
# Find the radius of the circumscribed circle
radius <- sqrt((2*area)/(nSides*sin((2*pi)/nSides)))
# I assume the center is at (0;0) and the first point lies at (0; radius)
points <- list(x=NULL, y=NULL)
angles <- (2*pi)/nSides * 1:nSides
points$x <- cos(angles) * radius
points$y <- sin(angles) * radius
return (points);
}
# Some examples
par(mfrow=c(3,3))
for (i in 3:11)
{
p <- regular.poly(i, 100)
plot(0, 0, "n", xlim=c(-10, 10), ylim=c(-10, 10), xlab="", ylab="", main=paste("n=", i))
polygon(p)
}
We can extrapolate to a generic convex polygon.
The area of a convex polygon can be found as:
A = 1/2 * [(x1*y2 + x2*y3 + ... + xn*y1) - (y1*x2 + y2*x3 + ... + yn*x1)]
We generate the polygon as above, but deviate angles and radii from those of the regular polygon.
We then scale the points to get the desired area.
convex.poly <- function(nSides, area)
{
# Find the radius of the circumscribed circle, and the angle of each point if this was a regular polygon
radius <- sqrt((2*area)/(nSides*sin((2*pi)/nSides)))
angle <- (2*pi)/nSides
# Randomize the radii/angles
radii <- rnorm(nSides, radius, radius/10)
angles <- rnorm(nSides, angle, angle/10) * 1:nSides
angles <- sort(angles)
points <- list(x=NULL, y=NULL)
points$x <- cos(angles) * radii
points$y <- sin(angles) * radii
# Find the area of the polygon
m <- matrix(unlist(points), ncol=2)
m <- rbind(m, m[1,])
current.area <- 0.5 * (sum(m[1:nSides,1]*m[2:(nSides+1),2]) - sum(m[1:nSides,2]*m[2:(nSides+1),1]))
points$x <- points$x * sqrt(area/current.area)
points$y <- points$y * sqrt(area/current.area)
return (points)
}
A random square of area 500m^2 is easy - its a square of side sqrt(500)m. Do you care about rotations? Then rotate it by runif(x,0,2*pi). Do you care about its location? Add an (x,y) offset computed from runif or whatever.
Rectangle? Given the length of any one pair of sides you only have the freedom to choose the length of the other two. How do you choose the length of the first pair of sides? Well, you might want to use runif() between some 'sensible' limits for your application. You could use rnorm() but that might give you negative lengths, so maybe rnorm-squared. Then once you've got that side, the other side length is 500/L. Rotate, translate, and add salt and pepper to taste.
For triangles, the area formula is half-base-times-height. So generate a base length - again, runif, rnorm etc etc - then choose another point giving the required height. Rotate, etc.
Summarily, a shape has a number of "degrees of freedom", and constraining the area to be fixed will limit at least one of those freedoms[1], so if you start building a shape with random numbers you'll come to a point where you have to put in a computed value.
[1] exactly one? I'm not sure - these aren't degrees of freedom in the statistical sense...
I would suggest coding a random walk of adjacent tiny squares, so that the aggregation of the tiny squares could be of arbitrary shape with known area.
It would be very tough to make a generic method. But you could code up example for 3, 4, 5 sided objects. Here is an example of a random triangle.(in C#)
class Triangle
{
double Angle1;
double Angle2;
//double angle3; 180 - angle1 - angle2;
double Base;
}
Triangle randomTriangle(double area){
//A = (base*hieght)/2.0;
double angle1 = *random number < 180*;
double angle2 = *random number < (180 - angle1)*;
*use trig to get height in terms of angles and base*
double base = (area*2.0)/height;
return new Triangle(){Angle1 = angle1, Angle2 = angle2, Base = base};
}