How to generate a random convex polygon?

Question

I'm trying to devise a method for generating random 2D convex polygons. It has to have the following properties:

• coordinates should be integers;
• the polygon should lie inside a square with corners (0, 0) and (C, C), where C is given;
• the polygon should have number of vertices close to a given number N.

For example, generate random polygons that have 10 vertices and lie inside square [0..100]x[0..100].

What makes this task hard, is the fact that the coordinates should be integers.

The approach I tried was to generate random set of points in the given square and compute the convex hull of these points. But the resultant convex hull is very little vertices compared to N.

Any ideas?

Answer 1

Here is the fastest algorithm I know that generates each convex polygon with equal probability. The output has exactly N vertices, and the running time is O(N log N), so it can generate even large polygons very quickly.

• Generate two lists, X and Y, of N random integers between 0 and C. Make sure there are no duplicates.
• Sort X and Y and store their maximum and minimum elements.
• Randomly divide the other (not max or min) elements into two groups: X1 and X2, and Y1 and Y2.
• Re-insert the minimum and maximum elements at the start and end of these lists (minX at the start of X1 and X2, maxX at the end, etc.).
• Find the consecutive differences (X1[i + 1] - X1[i]), reversing the order for the second group (X2[i] - X2[i + 1]). Store these in lists XVec and YVec.
• Randomize (shuffle) YVec and treat each pair XVec[i] and YVec[i] as a 2D vector.
• Sort these vectors by angle and then lay them end-to-end to form a polygon.
• Move the polygon to the original min and max coordinates.

An animation and Java implementation is available here: Generating Random Convex Polygons.

This algorithm is based on a paper by Pavel Valtr: “Probability that n random points are in convex position.” Discrete & Computational Geometry 13.1 (1995): 637-643.

Answer 2

Following @Mangara answer there is JAVA implementation, if someone is interested in Python port of it

import random
from math import atan2


def to_convex_contour(vertices_count,
                      x_generator=random.random,
                      y_generator=random.random):
    """
    Port of Valtr algorithm by Sander Verdonschot.

    Reference:
        http://cglab.ca/~sander/misc/ConvexGeneration/ValtrAlgorithm.java

    >>> contour = to_convex_contour(20)
    >>> len(contour) == 20
    True
    """
    xs = [x_generator() for _ in range(vertices_count)]
    ys = [y_generator() for _ in range(vertices_count)]
    xs = sorted(xs)
    ys = sorted(ys)
    min_x, *xs, max_x = xs
    min_y, *ys, max_y = ys
    vectors_xs = _to_vectors_coordinates(xs, min_x, max_x)
    vectors_ys = _to_vectors_coordinates(ys, min_y, max_y)
    random.shuffle(vectors_ys)

    def to_vector_angle(vector):
        x, y = vector
        return atan2(y, x)

    vectors = sorted(zip(vectors_xs, vectors_ys),
                     key=to_vector_angle)
    point_x = point_y = 0
    min_polygon_x = min_polygon_y = 0
    points = []
    for vector_x, vector_y in vectors:
        points.append((point_x, point_y))
        point_x += vector_x
        point_y += vector_y
        min_polygon_x = min(min_polygon_x, point_x)
        min_polygon_y = min(min_polygon_y, point_y)
    shift_x, shift_y = min_x - min_polygon_x, min_y - min_polygon_y
    return [(point_x + shift_x, point_y + shift_y)
            for point_x, point_y in points]


def _to_vectors_coordinates(coordinates, min_coordinate, max_coordinate):
    last_min = last_max = min_coordinate
    result = []
    for coordinate in coordinates:
        if _to_random_boolean():
            result.append(coordinate - last_min)
            last_min = coordinate
        else:
            result.append(last_max - coordinate)
            last_max = coordinate
    result.extend((max_coordinate - last_min,
                   last_max - max_coordinate))
    return result


def _to_random_boolean():
    return random.getrandbits(1)