確定平面內n個點所在正多邊形的一種方法

牛立尚

[摘 要]本文給出了確定平面內n個點所在正多邊形的一種方法，不管這n個點各自異邊，還是若干點同邊，只要它們構成一個凸包圍，就可以用這種方法確定它們是否在某一個正多邊形上，如果是，則能夠給出該正多邊形的頂點。

[關鍵詞]正多邊形；凸包圍；自洽

[DOI]10.13939/j.cnki.zgsc.2015.07.135

1 引 言

2013高教社杯數學建模[1， 2]競賽C題中，有一個問題是，根據古塔每層的八個數據點，確定各層的中心位置。參賽隊大多數的做法是牽強地假設古塔為八角塔，且數據點位于古塔的棱角上，這些假設顯然是不合適的。

利用本文的方法，可確定該題中所給八個數據點在地面上的投影點不在正四、六邊形上，并計算出了投影點所在的正八邊形的頂點。另外，給出了一組五個數據點，用該法計算出了它們所在的正五邊形的頂點。

2 相關概念

（1）正多邊形內角角度：每個內角的角度為[SX（]（M-2）π[]M[SX）]。

（2）自洽：如果穿過1點的多邊形的邊（稱為邊1）方向已知，則穿過2點的邊（稱為邊2）的方向也將“幾乎已知”：兩條邊要么是同一條邊，要么所成的角為內角[SX（]（M-2）π[]M[SX）]；若邊2的方向已知，則依同樣的方法能確定邊3；依次類推，如果邊M的方向與邊1也滿足以上要求，那么這個直線方向序列就能夠圍成一個正多邊形（稱這一系列方向自洽）。

3 算法的詳細步驟及計算過程

3.1 對輸入n點進行順時針排序

使得輸入點按照順時針方向存入結果數組R中。

3.2 計算穿過每個點的直線方向的取值范圍

給定第1個節點的斜率，遞推地，可得所有節點的斜率，相應得到各個直線與x軸所成角，形成AngleBiTree。

根據AngleBiTree每個節點對應的角、斜率范圍Rk，可判斷AngleBiTree中該節點對應的直線角是否合法，若合法，將IsOkBiTree的相應節點置為1，否則置0。

3.4 遍歷IsOkBiTree，尋找一條節點值都是1的路徑

3.5 在第一條直線方向角取值范圍內采樣，對每個采樣，執行4，并判斷各方向角是否自洽

若自洽，則4中路徑對應的各方向角為正多邊形各邊的方向角，否則用下一個采樣點執行4。若最終找不到自洽的直線序列，則需要更改邊數M。

4 實驗結果

5 結 論

實驗和理論均表明，本文給出的算法能夠找到給定的一些點所在的正多邊形，但很顯然，這樣的多邊形有時不唯一，若想找到這些點能夠確定的所有多邊形，可窮舉邊1的角度初值，找到所有自洽的多邊形。而實際應用中，這種方式是不必要的。例如，可選擇靠近多邊形頂點的一些點作為給定點，此時能夠找到符合實際要求的多邊形。

參考文獻：

[1]趙靜，但琦.數學建模與數學實驗[M].北京：高等教育出版社，2003.

[2]姜啟源，謝金星，葉俊.數學模型[M].北京：高等教育出版社，2011.

[3]嚴蔚敏.數據結構[M].北京：清華大學出版社，2007.