檢測數組中的一組點是否是順時針或逆時針順序定義的複合多邊形的頂點？

編輯：我更新了program的答案，它的效果很好！檢測數組中的一組點是否是順時針或逆時針順序定義的複合多邊形的頂點？

我正在製作一個program（隨時試用），讓用戶繪製多邊形，然後再進行三角化。他們可以點擊添加頂點並按回車鍵進行三角測量。無論如何，只要我告訴它，如果點是以順時針或逆時針方式繪製的（現在我只設置它的順時針多邊形），算法就可以正常工作。我一直在試圖弄清楚這幾天，但不知道如何確定點是順時針還是逆時針。嘗試使用前面提到的程序繪製圖形以獲得更好的想法，您可以體驗我所談論的內容，而不是嘗試解釋它。

下面是如何的點被定義：

function Point(x, y) { 
    this.x = x; 
    this.y = y; 
} 

var vertices = []; 

// Called on click 
function addPoint(mouseX, mouseY) { 
    vertices.push(new Point(mouseX, mouseY)); 
}

這裏是順時針多邊形的圖像：

Clockwise Polygon

這裏是逆時針方向多邊形的圖像：

Counterclockwise Polygon

如果你能幫我弄清楚如何確定點的「順時針方向」，我將非常感激！

來源

2013-01-24 Conner Ruhl

測量每三個點之間的角度，併爲整個多邊形求和。在一個方向上，你會得到一個積極的，而在另一個方向，你會得到一個消極的總數。對應於多邊形的時鐘方向。 – TMB

剛剛發現這個問題：http://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order接受的答案有一個類似的解決方案，但可能比我的簡單。 – kodkod

計算使用shoelace formula多邊形區域，但沒有絕對的價值符號。如果結果爲正，則點順時針排列，如果是負順時針排列。

function polygonArea() { 
    var area = 0; 
    for (var i = 0; i < vertices.length; i++) { 
     j = (i + 1) % vertices.length; 
     area += vertices[i].x * vertices[j].y; 
     area -= vertices[j].x * vertices[i].y; 
    } 
    return area/2; 
} 
var clockwise = polygonArea() > 0;

來源

2013-01-24 16:52:27 kodkod

完美的作品！我爲未來的觀衆添加了一些代碼。太感謝了！ –

由於我們只關心標誌，所以不需要再除以二;不是說它有很大的不同。 –

一般的想法是看看你的polygone的凸包，並從那裏猜測方向。然而，我認爲你不需要建立整個船體來找到方向，而只需要一個屬於它的部分。

所以：

找到你polygones的兩個點，使所有其他的點都在這條線的一側。
如果所有點都在左側（只檢查其中一個點），它是逆時針的。如果它們在右側，則是順時針方向。

例：

在上面的數字：4-5讓右邊的數字，5-11讓右邊的數字，... 在底部的數字：6- 7讓左邊的數字，7-14讓左邊的數字...

警告：雖然在您的多邊形上「行走」，不要重新計算數字，否則將是錯誤的。在最上面的圖中，4-（n-1）讓左邊的數字！

來源

2013-01-24 16:40:56

您對clockwisedness的直觀定義尚未明確定義。例如，如果我畫一個馬蹄形：

/---a-b--\ 
/ _d_c_ \ 
//  \ \ 
| |  | | 
| |  | | 
    \ \  // 
    \ \ // 
    --  --

如果0 = a < b < b < d我看a和b我就從你的描述的形狀已經繪就順時針的結論，但如果0 = c < d < a < b我可以得出結論，形狀已經逆時針繪製。由於這兩種情況都涉及到相同點的繪製方向，只是從不同的起點，我只能得出結論，你的定義是缺乏的。

我畫的馬蹄不是最好的;這個想法是，它幾乎是一個圓形，底部只有一個小孔，允許另一面朝相反的方向繪製。

如果您想了解更多的嚴格定義的東西，那麼我建議沿着以下的說法：

考慮任何有限簡單多邊形作爲平面分成兩個不同的區域（一個有限和無限的空間），我們總是可以將有限區域視爲多邊形的內部。在這種情況下，如果點的順序沿着其右側與外部運行，我們將頂點順序定義爲順時針。這被稱爲curve orientation。

一旦有了這種更堅實的定義，實現可作爲計數匝數一樣簡單。取任意有序對的中點，比如說0和1，在有序對的右邊（任意角度，比如垂直線）取一條線段，然後計算它與其他線段有多少交點：曲線順時針iff這個數字很奇怪。

這是易於實現的，直鏈在時間O(n)，並增加了空間恆定O(1)。

來源

2013-01-24 16:43:19 davin

您可以隨時在多邊形上「行走」，使內部位於左側。如果計數與這個「行走」方向一致，則它是逆時針的（在數學上是正的），否則它是順時針的。所以這個概念是明確的！ –

@Dr_Sam，這是正確的，但這不是OP定義的。讓我看看問題中內部和外部的定義，我會同意你的看法。如果他們不是，那麼就沒有方向，就像我的例子所解釋的那樣。 – davin

正如您在編輯答案中所說的那樣，有一個有界區域和一個無界區域，它們隱含地定義了內部和外部。問題是關於三角形的多邊形，所以我想內部，即有限的一部分。順便說一句，很好的答案！ –

這是一個專門用於OpenLayers的函數函數。正如你可以看到順時針多邊形的條件是區域確認它。

function IsClockwise(feature) 
{ 
if(feature.geometry==null)return -1; 
var vertices=feature.geometry.getVertices(); 
var area=0; 
for (var i = 0; i < (vertices.length); i++) 
    { 
    j = (i + 1) % vertices.length; 
    area += vertices[i].x * vertices[j].y; 
    area -= vertices[j].x * vertices[i].y; 
    // console.log(area); 
    } 
return (area < 0); 
}

來源

2014-11-18 10:45:12 MSS

如果有人使用three.js所的ShapeUtils帶有其內部使用area方法來確定計算出的面積的符號一個內置isClockWise方法。

isClockWise: function (pts) { 

    return ShapeUtils.area(pts) < 0; 

}

的ShapeUtils.isClockWise方法可以發現here。

area: function (contour) { 

    var n = contour.length; 
    var a = 0.0; 

    for (var p = n - 1, q = 0; q < n; p = q ++) { 

     a += contour[ p ].x * contour[ q ].y - contour[ q ].x * contour[ p ].y; 

    } 

    return a * 0.5; 

},

的ShapeUtils.area方法可以發現here。

來源

2017-01-23 15:34:06 Wilt

檢測數組中的一組點是否是順時針或逆時針順序定義的複合多邊形的頂點？

回答

相關問題