多邊形頂點從一組點

Question

我怎樣才能從給定的一個點的多邊形。

可能的多邊形：

無效的多邊形：

多邊形必須是不能自相交。

我一直在考慮基於一點對點進行排序，但似乎它在某些情況下無效。 謝謝。

Answer 1

也許，所以：

1. 查找給定的點的凸包ħ
2. 對於未在船體的每個點P，找到最近邊緣的HiHi + 1的船體，並且與邊緣髖替換它和PHi + 1。
3. 如果兩個點具有相同的最近的邊緣，配合他們