Algorithm for random polygon generation

As the random distribution is not specified, I would suggest the following simple approach: start with a triangle, which is always a convex polygon except the case when all three point are on the same line, so throw out the cases when it happens. (As you are dealing with approximate floating-point arithmetic, never check anything for equality, create some '>' or '>=' criteria, in this case, for example, specify some minimal angle you would allow for a triangle). On next step, add a random point to replace a line segment (polygon side) with a two adjacent segments. On each step, it's easy to determine the constraints for a random point (new vertex) the way to keep the new polygon convex.

—SA

I just got an idea of an alternative, simpler algorithm.

Start with a random triangle, as in Solution one, and, in a random number of steps, create a N+1-side polygon from an N-side using the "cut of a corner" operation. For this purpose, take two random but adjacent sides. In each side, choose a random point insider of the line segment representing a side. Connect these two points with a line segment, which should replace the "cut out" corner. This will create two new corners (vertices) instead of "cut-out" one. Proceed to the next step.

As it is easy to see, each step guarantees that a new polygon is convex provided the previous polygon was convex. As you start from a convex polygon (triangle), the polygon on each step is also convex.

—SA