Generate random polygons in C#

[random polygons]


I needed a method for generating random polygons for a graphics program and the following code shows the result.

// Make random polygons inside the bounding rectangle.
private static Random rand = new Random();
public static PointF[] MakeRandomPolygon(
    int num_vertices, Rectangle bounds)
{
    // Pick random radii.
    double[] radii = new double[num_vertices];
    const double min_radius = 0.5;
    const double max_radius = 1.0;
    for (int i = 0; i < num_vertices; i++)
    {
        radii[i] = rand.NextDouble(min_radius, max_radius);
    }

    // Pick random angle weights.
    double[] angle_weights = new double[num_vertices];
    const double min_weight = 1.0;
    const double max_weight = 10.0;
    double total_weight = 0;
    for (int i = 0; i < num_vertices; i++)
    {
        angle_weights[i] = rand.NextDouble(min_weight, max_weight);
        total_weight += angle_weights[i];
    }

    // Convert the weights into fractions of 2 * Pi radians.
    double[] angles = new double[num_vertices];
    double to_radians = 2 * Math.PI / total_weight;
    for (int i = 0; i < num_vertices; i++)
    {
        angles[i] = angle_weights[i] * to_radians;
    }

    // Calculate the points' locations.
    PointF[] points = new PointF[num_vertices];
    float rx = bounds.Width / 2f;
    float ry = bounds.Height / 2f;
    float cx = bounds.MidX();
    float cy = bounds.MidY();
    double theta = 0;
    for (int i = 0; i < num_vertices; i++)
    {
        points[i] = new PointF(
            cx + (int)(rx * radii[i] * Math.Cos(theta)),
            cy + (int)(ry * radii[i] * Math.Sin(theta)));
        theta += angles[i];
    }

    // Return the points.
    return points;
}

The basic idea is to create points for random polygons based on those that lie on an ellipse within the bounds given as a parameter. The points’ angles around the ellipse and their distances from the center are randomly changed to produce the random polygon.

The code first picks random radii for the points ranging from 0.5 to 1.0. This is reasonably straightforward. (For information on the Random class’s NextDouble extension method, see Make extension methods to generate random double values in C#.)

Next the code generates random angles for the points. Unfortunately this part is a little trickier.

The program eventually needs the angles to be between 0 and 2π radians and it needs them in sorted order. To generate the angles, the code first picks a random “weight” between 1.0 and 10.0 for each point. The code keeps track of the total of the weights in variable total_weight.

The program then treats each of the weights as a fraction of the whole 2π radians in the ellipse. Each point’s angle represents the angle between that point and the previous point, and it uses the weight to determine the fraction. For example, suppose the fourth point’s angle is 3 and the total of all angles is 20. Then the angle between the third and fourth points should be (3 / 20) * 2π radians.

To convert the weights into angles, the program loops through the weights and converts each weight into an angle by multiplying each angle by 2 * Math.PI / total_weight.

(I did think of a simpler method for generating the angles: pick random values between 2π radians and then sort them. Unfortunately that could produce some duplicate values or values that are very close together, and that would give the polygon ugly spikes. The method shown here is more complicated but creates upper and lower bounds on the amount by which adjacent points’ angles can differ.)

Finally the code uses the angles and radii to calculate each point’s position. It uses the Rectangle class’s MidX and MidY extension methods to find the midpoint of the bounds. (See Make rectangle extension methods in C# for information on those methods.)

The program uses Math.Sin and Math.Cos to determine the direction of offset for each point, multiplies by the bounding ellipse’s X and Y radii, and then multiplies by the point’s random radius to get the final location.

The method then simply returns the points in an array so the calling code can use the Graphics object’s DrawPolygon method to draw it.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, geometry, graphics and tagged , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *