如何將平面上無序的一組點連成一個簡單多邊形？

01-05

最近因為實驗室的項目要求要寫一個小的演算法。內容大致是這樣的：一組無序點，
1，2，3，4，5，6.然後我按順時針或者逆時針的順序將各個點連接起來。我最後要得到的是連接起來後這個多邊形的面積。
因為這是在計算機上實現的，計算機是無法自動將這些點一次鏈接起來的，我覺得首先要解決的第一步應該是亂序點的排序問題，只有解決了亂序點的排序問題才能將無序點變成有序點連接起來，然後進行多邊形的計算。
===========================
滿足題意的簡單多邊形（邊不自交的多邊形）可能有很多個，任意輸出一個即可。

補充：針對@cloak shining 最後一個演算法，如果選取相鄰2個（1和2）點的情況。不管順時針還是逆時針都不能連成一個多邊形的。

不太明白題主的意思，不過：

如果這些點可以形成一個凸多邊形的話，就凸包就行，演算法多了去了Jarvis March, Graham Scan, Quick Hull, randomized incremental construction……算完也就把順序排出來了。

如果不是的話，請首先弄明白自己的需求，定義一個良序，因為有很多種方法可以連出一個邊不自交的多邊形，排序結果不唯一。當然，如果題主不是很介意，生成任意一個不自交的多邊形都可以，我提一種簡單粗暴的增量演算法：

1、取任意不共線的三點連成一個三角形X（在你給的例子中，比如取1-4-5-1）。

2、然後遍歷剩餘的點（記為P）和已有的多邊形X的邊（記為AB），若三角形ABP中不含其他點，把點P插入已有的多邊形X中（原來的邊AB變成AX, XB兩條邊）。

3、重複步驟2，直到選完所有頂點。

嗯，複雜度是O(N^4)……

=============================

好吧，再提一個更快的分治演算法：

1、預處理：先把所有點按x坐標從左到右排序，時間為O(NlgN)。

2、分治：用一條豎線把所有的點切成兩半，分別遞歸執行本演算法，得到左右兩邊的多邊形X和Y。

3、合併：把X的最低點重新連到Y的最低點，再把Y的左鏈的次低點連到X的右鏈的次低點。（左、右鏈就是把整個多邊形（一個圈）從最高點和最低點斷開，拆成兩部分啦！）

分治、合併部分的複雜度是T(N) = 2*T(N/2) + O(N)，也即T(N) = O(NlgN)，算上預處理部分，總的複雜度也是O(NlgN)。（其實合併部分如果做得好可以O(1)完成，因此分治+遞歸只需要O(N)時間。但由於預處理就已經需要O(NlgN)的時間了，後面分治做得快也沒用啊……）

舉個例子，在題主那張圖裡，遞歸處理左右兩部分，得到多邊形X: 1-5-4-1（其中1-5叫左鏈，5-4-1叫右鏈）和Y: 6-2-3-6（其中6-2-3叫左鏈，3-6叫右鏈）。然後合併：連接5-3（多邊形X和Y的最低點，原來的連線5-4自動斷開），連接2-4（Y左鏈的次低點和X右鏈的次低點，原來的連線2-3自動斷開）。得到的多邊形就是1-5-3-6-2-4-1。

得出的多邊形大概像是城牆的形狀，像是若干個漢字「凹」連接起來的。我畫個示意圖：

===============

合併演算法稍有問題，需要再修改，不過大體是對的。

=======================繼續更=========================

想到了一個非常簡單的演算法哈哈哈：

1、對所有點按照x坐標（x相同時按y）從小到大排序，把最左邊的點記為A（若有多個取最下方的點），最右邊的點記為B（若有多個取最上方的點）。

2、構造上鏈：把所有在直線AB上方的點按x坐標（x相同時按y）從小到大連接起來；

3、構造下鏈：對位於直線AB下方的點同樣處理。

最後輸出的時候注意把下鏈顛倒一下（連的時候是從A連到B的，輸出的時候從B到A輸出）就行。

正確性顯而易見：上鏈內部是邊不交的（因為邊的端點的x坐標從小到大排列），下鏈同理，上下鏈之間也不交（因為分處直線AB兩側，沒法交）。

然後就完了！時間複雜度O(NlgN)，而且非常好寫！示意圖如下：

這答案不是唯一的吧，因為樓主沒有說連成凸包啊

比如順時針排列，142635，126354，162354，都是滿足條件的排列啊…而且面積不相等

這問題條件很松，幾乎可以隨意的弄出一個O(nlogn)的演算法吧：先把所有點按x坐標排序，最左邊三個點先構成一個三角形。然後按x坐標從小到大繼續掃所有的點。每掃到一個新的點u的時候，判斷上一個掃到的點v的兩條邊pv和qv，哪條邊對這個新點可見，必至少有一個可見的邊，不妨設為pv，把pv移除然後把pu和vu加入。正確性證明：p和q都在v的左側，所以pv和qv的可見區域的並可以覆蓋整個x&>v.x（v.x指的是點v的橫坐標）的半平面，而u必在x&>v.x這個半平面里。所以pv和qv至少有一個邊是u可見的。

因為pv是可見邊，所以px和vx必不和已經有的邊相交。補充一下，

根據這個基於可見性的做法，可以求出所有這個點集可以構成的簡單多邊形：

修改的地方在「判斷上一個掃到的點v」,簡單一點的修改方式是判斷已經構造出的包含前i個點的簡單多邊形的每一條邊是否對新的點可見。

既然是軟體，那麼就不用那麼多了。很簡單的辦法。

直接deluay三角剖分。

然後算得到的三角形集合的面積和就行了。

三角形的面積計算就太簡單了，直接兩個邊叉乘除以2

仔細看了一下原來是要算面積啊！題主你知道不自交的多邊形面積是有公式的么？

對於任意多邊形 $A_1 A_2 A_3 cdots A_n$ ，其中 $A_k$ 的坐標是 $(x_k, y_k)$ ，那麼其面積：

$[ S = frac{1}{2} iggl| egin{smallmatrix} x_1 x_2 x_3 cdots x_n x_1 \ y_1 y_2 y_3 cdots y_n y_1 end{smallmatrix} iggl| = frac{1}{2} iggl| sum_{i=0}^{n-1}(x_iy_{i+1}-x_{i+1}y_i) iggl| ]$

Yeah!! O(1)達成！

======================分割線=============================

竟然有我都會的演算法題！熱淚盈眶地謝邀！

1. 將所有點隨便什麼順序命名為 $A_1, A_2, cdots A_n$

2. 找到所有點的中點 $O$ 作為原點

3. 以 $OA_1$ 為正半軸，依次算出 $angle A_2OA_1,angle A_3OA_1, cdots angle A_nOA_1$ 的大小。

4. 隨便什麼排序法對以上角的大小進行排序。