Winding Number: 一個強大的計算幾何工具

一、什麼是winding number?

Winding number，中文翻譯為「繞數」，是計算幾何中一個非常重要的概念。它可以用於計算一個點是否在一個多邊形內部，也可以用於計算兩個多邊形之間的拓撲關係，還可以用於計算曲線的方向等等。下面我們詳細了解一下.

二、計算winding number的方法

計算winding number的方法就是通過統計多邊形的邊沿方向與點所在直線的夾角的加減情況。具體的，如果一個點p在一個多邊形內部，那麼以p為圓心的射線必然會與多邊形的某些邊沿相交。假設這些邊沿按照順時針方向排列，我們就定義這些邊沿的夾角為正。如果這些邊沿按照逆時針方向排列，我們就定義這些邊沿的夾角為負。統計這些夾角的和，我們就可以得到這個多邊形對這個點的winding number值。

double windingNumber(Point2D[] polygon, Point2D p) {
    double angle = 0.0;
    int n = polygon.length;
    for (int i = 0; i < n; i++) {
        Point2D v1 = polygon[i].subtract(p);
        Point2D v2 = polygon[(i + 1) % n].subtract(p);
        angle += angleBetween(v1, v2);
    }
    return angle / (2 * Math.PI);
}

三、winding number的應用

1. 點在多邊形內部

假設一個點p對於一個多邊形的winding number值為w，那麼我們可以通過判斷w是否等於0來判斷點是否在多邊形的外部，w是否等於1來判斷點是否在多邊形的內部。如果w為其他值，說明點在多邊形的邊界上。

boolean isPointInsidePolygon(Point2D[] polygon, Point2D p) {
    double w = windingNumber(polygon, p);
    return Math.abs(w) > 0.5;
}

2. 計算兩個多邊形之間的拓撲關係

在計算幾何中，拓撲關係是指兩個圖形之間的相對位置關係。winding number可以用於判斷兩個多邊形之間的拓撲關係。假設我們有兩個多邊形A和B，如果B的每個點都在A內部，那麼B是在A內部的。如果A和B都不在彼此內部，那麼它們必然是相交的。如果一個多邊形在另一個多邊形內部，那麼這個多邊形的winding number值必然為1，而另一個多邊形對於這個多邊形的winding number值必然為0。

enum TopologyRelation {
    INSIDE, OUTSIDE, INTERSECT
}

TopologyRelation getTopologyRelation(Point2D[] A, Point2D[] B) {
    double wA = Math.abs(windingNumber(B, A[0]));
    double wB = Math.abs(windingNumber(A, B[0]));
    if (wA < 0.5 && wB  -0.5) { // A contains B
        return TopologyRelation.INSIDE;
    } else if (wB - 1 > -0.5) { // B contains A
        return TopologyRelation.OUTSIDE;
    } else { // partially overlap
        return TopologyRelation.INTERSECT;
    }
}

3. 計算曲線的方向

假設我們有一條曲線，需要對其進行繪製，我們就需要知道這條曲線的方向，以便正確地繪製出曲線。winding number可以幫助我們計算曲線的方向。具體的，我們可以通過計算一個無限小區域內上下輪廓線的winding number之差獲得該區域內上下輪廓線的方向。如果該差值大於0，說明該區域內上輪廓線的方向和下輪廓線的方向是逆時針的，也就是曲線應該沿著順時針方向繪製；如果該差值小於0，說明該區域內上輪廓線的方向和下輪廓線的方向是順時針的，也就是曲線應該沿著逆時針方向繪製。

double contourOrientation(Matrix2D C, double x) {
    double windingNumberTop = windingNumber(C.getTopContour(), new Point2D(x, Double.POSITIVE_INFINITY));
    double windingNumberBottom = windingNumber(C.getBottomContour(), new Point2D(x, Double.NEGATIVE_INFINITY));
    return windingNumberTop - windingNumberBottom;
}

四、總結

Winding number是計算幾何中非常重要的一個概念，它可以用於計算點是否在多邊形內部、計算兩個多邊形之間的拓撲關係、計算曲線的方向等等。以上是winding number的應用場景的一些例子，希望對大家能有所幫助。