多邊形最佳演算法

『壹』 游戲任意多邊形切割演算法

1. 判斷一個點與一個多邊形關系的演算法是計算機圖形學的一個演算法. 關於具體的演算法, 你可以參考 http://blog.csdn.net/okvee/archive/2010/06/02/5643407.aspx 裡面的描述很詳細.
2. 人在冰上走的時候記錄他的行走路線的方法: 新建一個容量為N的點的隊列, 每隔一定時間(例如0.3秒)取人物的位置點, 判斷隊列里是否已經存在這個點, 若不存在則把該點壓到隊列里; 若存在則表明形成了一個多邊形(嚴格來說, 只有間隔超過兩個點才能形成一個多邊形,至少3點才能確定一個面嘛) [隊列就是類似於堆棧的數據結構, 可以壓入元素, 當壓入的元素個數超過隊列的容量後, 最先壓入的元素會被刪除]用隊列來保存人物的軌跡再好不過了.
3. 那個層次感的實現: 其實就是將多邊形軌跡往下偏移幾個像素, 並刪除不在原多邊形區域內的點即可.

『貳』 泰森多邊形計算公式

泰森多邊形沒有固定計算公式，泰森多邊形演算法的關鍵是對離散數據點合理地連成三角網，即構建Delaunay三角網。

對與每個離散點相鄰的三角形按順時針或逆時針方向排序，以便下一步連接生成泰森多邊形。排序的方法可如圖所示。設離散點為o。

找出以o為頂點的一個三角形，設為A；取三角形A除o以外的另一頂點，設為a，則另一個頂點也可找出，即為f；則下一個三角形必然是以of為邊的，即為三角形F；三角形F的另一頂點為e，則下一三角形是以oe為邊的；如此重復進行，直到回到oa邊。

(2)多邊形最佳演算法擴展閱讀：

泰森多邊形可用於定性分析、統計分析、鄰近分析等。例如，可以用離散點的性質來描述泰森多邊形區域的性質。

可用離散點的數據來計算泰森多邊形區域的數據；判斷一個離散點與其它哪些離散點相鄰時，可根據泰森多邊形直接得出。

『叄』 基於圖論的最小多邊形自動搜索演算法

圖是由點集和邊集所構成的抽象概念，圖的性質實質上可以表現為拓撲關系。如圖4.8b所示，點集由分叉點構成(4個分叉點，分別是1，2，3，4)，邊集則由地層線構成(7條地層線，分別是①，②，③，④，⑤，⑥，⑦)。需要說明的是，這里的邊是廣義上的邊，可能是直線段，也可能是多線段。

最小多邊形的自動搜索在GIS的空間分析中應用較多，搜索可分為無拓撲和含拓撲兩類。無拓撲自動搜索則完全依靠幾何計算來判斷，如夾角變化趨勢的多邊形自動搜索演算法(梁曉文等，2005)，該演算法主要依靠弧段間夾角計算來判斷，通過「左轉」或「右轉」的方法能夠唯一確定最小多邊形，原理簡單，但程序設計過程極其煩瑣。採用圖論的方法來實現，原理相對復雜，需要掌握數據結構知識，但程序代碼設計過程比較簡潔，具有擴展性。

為了簡單起見，以圖4.8b中地層線①為例，說明搜索過程。從分叉點1開始，沿地層線①在分叉點2與地層線②和③鄰接，地層線②和③又分別在分叉點3和4與兩地層線鄰接。整個鄰接關系可以用一個樹(tree)型結構來表示(圖4.10)，終止條件是回到分叉點1，形成閉合迴路或者出現自相交，則停止搜索。這樣，產生4條有意義的多邊形為：1-①-2-②-3-⑥-1，1-①-2-②-3-④-4-⑤-1，1-①-2-③-4-④-3-⑥-1，1-①-2-③-4-⑤-1。

圖4.10 分叉點1沿①為起始方向的連通圖

在上述4條連通多邊形中，面積最小者對應的就是一個最小多邊形(周秋生，1996)。若多邊形點對為(x₁，y₁)，(x₂，y₂)，…，(x_n，y_n)，面積可採用下式來計算：

S=

×[(x₁×y₂-y₁×x₂)+(x₂×y₃-y₂×x₃)+…+(x_n×y₁-y_n×x₁)](4.1)可確定1-①-2-②-3-⑥-1為當前循環的最小多邊形，同時，刪除廣義邊①與②，②與⑥，及⑥與①之間的指針聯系，從而可以避免重復查找該最小多邊形。接下來，從分叉點1沿另外兩個方向⑤和⑥分別搜索最小多邊形，完成分叉點1的查找。然後，進入下一分叉點。

最終，得到3個最小多邊形。從圖論的觀點來看，所研究的圖是一個連通的平面圖。若圖有n個分叉點，m條廣義邊，p個最小多邊形，則平面圖的面數(包括外部面)f=p+1。

根據歐拉公式(孫家廣，1998)：

f+m-n=2 (4.2)

可以得到最小多邊形數目為

p=m-n+1 (4.3)

見圖4.4b中，m=7，n=5，則p=7-5+1=3。據此可以作為搜索結果正確與否的判斷方式之一。

『肆』 對於地圖上的不規則區域，有什麼好的演算法把它變為規則的多邊形

復制的。
/*在GIS（地理信息管理系統）中，判斷一個坐標是否在多邊形內部是個經常要遇到的問題。乍聽起來還挺復雜。
根據W. Randolph Franklin 提出的PNPoly演算法，只需區區幾行代碼就解決了這個問題。
假設多邊形的坐標存放在一個數組里，首先我們需要取得該數組在橫坐標和縱坐標的最大值和最小值，
根據這四個點算出一個四邊型，首先判斷目標坐標點是否在這個四邊型之內，如果在這個四邊型之外，那可以跳過後面較為復雜的計算，直接返回false。*/

if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) {
// 這個測試都過不了。。。直接返回false；
}
接下來是核心演算法部分：
int pnpoly (int nvert, float *vertx, float *verty, float testx, float testy) {
int i, j, c = 0;
for (i = 0, j = nvert-1; i < nvert; j = i++)
{
if
(
( (verty[i]>testy) != (verty[j]>testy) ) &&(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i])
)
c = !c;
}
return c;
}

額，代碼就這么簡單，但到底啥意思呢：
首先，參數nvert 代表多邊形有幾個點。浮點數testx, testy代表待測試點的橫坐標和縱坐標，*vertx,*verty分別指向儲存多邊形橫縱坐標數組的首地址。
我們注意到，每次計算都涉及到相鄰的兩個點和待測試點，然後考慮兩個問題：
1. 被測試點的縱坐標testy是否在本次循環所測試的兩個相鄰點縱坐標范圍之內？即
verty[i] <testy <="" verty[j]或者
verty[j] <testy <="" verty[i]2. 待測點test是否在i,j兩點之間的連線之下？看不懂後半短if statement的朋友請自行在紙上寫下i,j兩點間的斜率公式，
要用到一點初中解析幾何和不等式的知識范疇，對廣大碼農來說小菜一碟。
然後每次這兩個條件同時滿足的時候我們把返回的布爾量取反。
可這到底是啥意思啊？
這個表達式的意思是說，隨便畫個多邊形，隨便定一個點，然後通過這個點水平劃一條線，先數數看這條橫線和多邊形的邊相交幾次，
（或者說先排除那些不相交的邊，第一個判斷條件），然後再數這條橫線穿越多邊形的次數是否為奇數，如果是奇數，那麼該點在多
邊形內，如果是偶數，則在多邊形外。詳細的數學證明這里就不做了，不過讀者可以自行畫多邊形進行驗證。

『伍』 幾何題，多邊形演算法

左邊的圖形，條件不足 ，無法確定紅線上方直角三角形內銳角的度數，因而無法計算紅色線處的長度，若銳角為45º，則非常簡單，如圖，點擊放大：

『陸』 如何求得任意多邊形的面積（包括內多邊形）

應當是化成三角形。
一、
對於一個三角形的三個頂點坐標知道的情況下，也就是說各個邊的邊長知道，另外還可以計算出各個頂角（因為知道了三個邊，根據餘弦定理就可以求出，或者你學過矢量的話，用兩個矢量的夾角算也成），最後用面積公式S=0.5*a*b*Sin(C)
二、
固定住一個點（比如最上面那個點），然後把與這個點不相鄰的點與這個固定點連起來。這樣就把多邊形全變成三角形。而且這里的三角形，三個邊全部知道，如上面所說的。就可以求出各個三角形的面積。

『柒』 多邊形游戲問題的演算法可以採用什麼來實現

在GIS（地理信息管理系統）中，判斷一個坐標是否在多邊形內部是個經常要遇到的問題。乍聽起來還挺復雜。根據W. Randolph Franklin 提出的PNPoly演算法，只需區區幾行代碼就解決了這個問題。 假設多邊形的坐標存放在一個數組里，首先我們需要取得該

『捌』 泰森多邊形法的泰森多邊形的建立步驟

建立泰森多邊形演算法的關鍵是對離散數據點合理地連成三角網，即構建Delaunay三角網。建立泰森多邊形的步驟如下：
1、離散點自動構建三角網，即構建Delaunay三角網。對離散點和形成的三角形編號，記錄每個三角形是由哪三個離散點構成的；
2、找出與每個離散點相鄰的所有三角形的編號，並記錄下來。這只要在已構建的三角網中找出具有一個相同頂點的所有三角形即可；
3、對與每個離散點相鄰的三角形按順時針或逆時針方向排序，以便下一步連接生成泰森多邊形。排序的方法可如圖所示。設離散點為o。找出以o為頂點的一個三角形，設為A；取三角形A除o以外的另一頂點，設為a，則另一個頂點也可找出，即為f；則下一個三角形必然是以of為邊的，即為三角形F；三角形F的另一頂點為e，則下一三角形是以oe為邊的；如此重復進行，直到回到oa邊；
4、計算每個三角形的外接圓圓心，並記錄之；
5、根據每個離散點的相鄰三角形，連接這些相鄰三角形的外接圓圓心，即得到泰森多邊形。對於三角網邊緣的泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構成泰森多邊形。
參考
泰森多邊形的建立