順時針和逆時針路徑的判斷

順時針 clockwise,逆時針 counterclockwise,假設有一個多角形,如何判斷是順著走,還是逆著走?

我試了很多個解法,有些真很很準,也不知道所以然,測試了好幾組資料,結果居然都是正確的!像這組:
https://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order/

I guess this is a pretty old question, but I’m going to throw out another solution anyway, because it’s straightforward and not mathematically intensive – it just uses basic algebra. Calculate the signed area of the polygon. If it’s negative the points are in clockwise order, if it’s positive they are counterclockwise. (This is very similar to Beta’s solution.)

Calculate the signed area: A = (x1*y2 – x2*y1 + x2*y3 – x3*y2 + … + xn*y1 – x1*yn)

Or in pseudo-code:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea

Note that if you are only checking the ordering.

Sources: http://mathworld.wolfram.com/PolygonArea.html


反而是上面很多人按讚的那個版本,我試的結果是錯的。

這個版本也不是萬能的,可能還是會出錯,但目前測試結果還沒有找到有問題的。

相關文章

寫留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *