Draw arbitrary convex shape knowing the lengths of its sides

Question

I've got a list of values, which are the lengths of the sides of an arbitrary convex shape (polygon). How can I draw this shape? What algorithm can help me with this task?

For example, I have a list: 2, 5, 2, 3. The drawing has to look like this:

Answer 1

I will quote here an answer I posted on MathOverflow:

A chain of edges can close iff the longest edge is not longer than the sum of the lengths of all the other edges.

In your example, the longest edge is 5, and it is not longer than 2+2+3=7. If you replace the edge of length 5 by an edge of length 8, then the four segments cannot close to a convex polygon. Whenever you have more than 3 edges, the resulting convex polygon is not uniquely determined: there is flexibility in its shape.

See the references cited above for pointers to proofs.

Answer 2

There is a relatively simple (if somewhat math heavy) O(N log N) to O(N^2) (depending on implementation) recursive geometry/trigonometry based solution to this.

1. The concept starts with a line segment with length equal to the sum of the lengths.
2. Break that line segment into a triangle (see related info near bottom).
3. Recursively break each edge of the triangle into more triangles as needed.

Step 2, requires ensuring that smaller two edges of the triangle are longer than the bigger one.

Step 3, can be done by turning a triangle into 2 triangles.

For the input and outputs I would use: Input: List of edges Output: list of interior angles.

So output[a] is the interior angle of the vertex either before after the edge at input[a].

A good reference is located here.

• Method #1 gif, shows the triangles at for that many vertices.
• Method #2 gif, P is an example of where the break might occur in step 2.
• Method #4 gif, here P could be considered moved out like in #3, note that in this case, the line lengths would not be to scale and in fact would be unknown. Notice that only the vertex positions of a1 and a2 would change. Resulting in changes to the interior angles of the vertices before and after a1 and a2. In this case, a1,a2,a3,an,p.

As for determining the interior angles. Use trigonometry and/or geometry. Given 3 sides of a triangle, it's possible to determine what the angles are. Given 2 sides and an angle (or 1 angle and 2 sides) it's possible to determine the missing sides and angles.

Of course, you may have to be careful as to where you break the edge so a triangle can be formed.