For me, it seems easy if we don't have to care about the imposed restrictions: no crossing and no straight angles.

Hmmmm.... New ideas coming... Maybe we don't have to care about crossings: any crossing can be solved by reordering the vertices, so, all we have to care about is the number unique vertices positions!

I still don't know how to avoid straight angles though.