GraphicsPath.IsClockWise() 扩展方法

Question

我需要为 GraphicsPath 对象创建一个扩展方法，用于确定 GraphicsPath 是顺时针缠绕还是逆时针缠绕。

像这样的东西：

    public static bool IsClockwise(GraphicsPath gp)
    {
        bool bClockWise = false;
        PointF[] pts = gp.PathPoints;

        foreach (PointF pt in pts)
        {
            //??
        }

        return bClockWise;
    }

注意：我只是假设我们需要在 GraphicsPath 中的点上使用 foreach ，但如果有更好的方法，请随时提供。

原因是 GraphicsPath 的 FillMode 确定相邻 GraphicsPath 的重叠部分是“填充”（Winding）还是“孔” （备用）。然而，只有当相邻的 GraphicsPaths 以相同的方向缠绕时，这才是正确的。

如果两条路径以相反方向缠绕，甚至将 FillMode 设置为缠绕会产生（不需要的）孔。

有趣的是，GraphicsPath 确实有一个 .Reverse() 方法，允许人们改变路径的方向（这确实解决了问题），但不可能知道 GraphicsPath 何时需要改变在不知道路径方向的情况下反转。

您能帮忙解决这个扩展方法吗？

Answer 1

我之所以把这个问题抛在那里，是因为这个问题引起了我的兴趣，这是我没有专业知识的事情，我想引发讨论。

我采用了多边形中的点伪代码并尝试使其适合您的情况。看来您只对确定某物是顺时针还是逆时针缠绕感兴趣。这是一个简单的测试和一个非常简单（粗略的）C# 实现。

[Test]
public void Test_DetermineWindingDirection()
{

    GraphicsPath path = new GraphicsPath();

    // Set up points collection
    PointF[] pts = new[] {new PointF(10, 60),
                    new PointF(50, 110),
                    new PointF(90, 60)};
    path.AddLines(pts);

    foreach(var point in path.PathPoints)
    {
        Console.WriteLine("X: {0}, Y: {1}",point.X, point.Y);
    }

    WindingDirection windingVal = DetermineWindingDirection(path.PathPoints);
    Console.WriteLine("Winding value: {0}", windingVal);
    Assert.AreEqual(WindingDirection.Clockwise, windingVal);

    path.Reverse();
    foreach(var point in path.PathPoints)
    {
        Console.WriteLine("X: {0}, Y: {1}",point.X, point.Y);
    }

    windingVal = DetermineWindingDirection(path.PathPoints);
    Console.WriteLine("Winding value: {0}", windingVal);
    Assert.AreEqual(WindingDirection.CounterClockWise, windingVal);
}

public enum WindingDirection
{
    Clockwise,
    CounterClockWise
}

public static WindingDirection DetermineWindingDirection(PointF[] polygon)
{
    // find a point in the middle
    float middleX = polygon.Average(p => p.X);
    float middleY = polygon.Average(p => p.Y);
    var pointInPolygon = new PointF(middleX, middleY);
    Console.WriteLine("MiddlePoint = {0}", pointInPolygon);

    double w = 0;
    var points = polygon.Select(point =>
                                    { 
                                        var newPoint = new PointF(point.X - pointInPolygon.X, point.Y - pointInPolygon.Y);
                                        Console.WriteLine("New Point: {0}", newPoint);
                                        return newPoint;
                                    }).ToList();

    for (int i = 0; i < points.Count; i++)
    {
        var secondPoint = i + 1 == points.Count ? 0 : i + 1;
        double X = points[i].X;
        double Xp1 = points[secondPoint].X;
        double Y = points[i].Y;
        double Yp1 = points[secondPoint].Y;

        if (Y * Yp1 < 0)
        {
            double r = X + ((Y * (Xp1 - X)) / (Y - Yp1));
            if (r > 0)
                if (Y < 0)
                    w = w + 1;
                else
                    w = w - 1;
        }
        else if ((Y == 0) && (X > 0))
        {
            if (Yp1 > 0)
                w = w + .5;
            else
                w = w - .5;
        }
        else if ((Yp1 == 0) && (Xp1 > 0))
        {
            if (Y < 0)
                w = w + .5;
            else
                w = w - .5;
        }
    }
    return w > 0 ? WindingDirection.ClockWise : WindingDirection.CounterClockwise;
}

我所放入的差异使得这对您的问题有点特殊，因为我计算了所有点的 X 和 Y 的平均值，并将其用作“多边形中的点”值。因此，只要传入一个点数组，它就会在它们中间找到一些东西。

我还假设 Vi+1 在到达点数组的边界时应该环绕，因此

if (i + 1 == points.Count)
    // use points[0] instead

这还没有被优化，它只是可能回答您的问题。也许您自己已经想到了这一点。

在此希望得到建设性的批评。 :)

Answer 2

不，您必须遍历这些点才能确定缠绕顺序。网络上有很多算法，例如。

http://www.engr.colostate.edu/~dga/dga /papers/point_in_polygon.pdf

我想当我需要实现它时，我使用了 The Graphics Gems 书中的算法，并针对地球表面进行了修改（地理空间应用程序）。我突然想到它是将分量向量相乘并对它们求和。总数的符号为您提供了缠绕顺序。

Answer 3

编辑：

忽略下面的所有内容。我发现了这个问题。

上面代码的最后一行应该从： 更改

return w > 0 ? WindingDirection.CounterClockWise : WindingDirection.Clockwise;

为

return w > 0 ? WindingDirection.ClockWise : WindingDirection.CounterClockwise;

否则，代码工作得很好，我已经接受了这个作为答案（但我确实想向@winwaed 提供支持，他找到了带有算法的文章）。

---忽略---（仅用于历史目的）

嗨戴夫，

我不确定发生了什么（还），但我从逆时针轮廓的函数中得到了“顺时针”的错误响应。

这是 Inkscape 0.48 中显示的轮廓之一，它有一个（新）选项，可以用微小的半箭头显示路径的方向。正如您所看到的，外部路径逆时针缠绕（即使函数按顺时针方向返回）。

我很快就会研究这个......