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) {
        return TopologyRelation.INTERSECT;
    } else if (wA - 1 > -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的应用场景的一些例子，希望对大家能有所帮助。