GraphicsPath.IsClockWise() Extension Method

Question

I need to create an extension method for a GraphicsPath object that determines if the GraphicsPath is wound clockwise or counter-clockwise.

Something like this:

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

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

        return bClockWise;
    }

Note: I just assume that we'd need a foreach on the points in the GraphicsPath here, but if there is a better way, please feel free to offer.

The reason for this is because the FillMode of the GraphicsPath determines if overlapping sections of adjacent GraphicsPaths are 'filled' (Winding) or 'holes' (Alternate). However, this is only true if the adjacent GraphicsPaths are wound in the same direction.

If the two paths are wound in opposing directions, even setting the FillMode to Winding results in the (unwanted) holes.

Interestingly enough, the GraphicsPath DOES have a .Reverse() method that allows one to change the direction of the path (and this DOES solve the problem), but it is impossible to know WHEN the GraphicsPath needs to be .Reversed without knowing the direction of the path.

Can you help out with this extension method?

Answer 1

I'm mostly throwing this out there because this question caught my interest, it was something I have no expertise in, and I'd like to generate discussion.

I took the Point in Polygon pseudo-code and tried to make it fit your situation. It seemed you are only interested in determining if something is winding clockwise or counter-clockwise. Here is a simple test and a very simple (rough around the edges) C# implementation.

[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;
}

The difference that I've put in that makes this a bit specific to your problem is that I've calculated the average values of X and Y from all points and use that as the "point in polygon" value. So, passing in just an array of points, it will find something in the middle of them.

I've also made the assumption that the V i+1 should wrap around when it gets to the bounds of the points array so that

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

This hasn't been optimized, it's just something to potentially answers your question. And perhaps you've already come up with this yourself.

Here's hoping for constructive criticism. :)

Answer 2

No, you will have to loop over the points to determine winding order. There are a number of algorithms on the web, eg.

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

I think when I needed to implement it, I used an algorithm from The Graphics Gems books, modified for the surface of the Earth (a geospatial app). off the top of my head I think it multiplied component vectors and summed them. The sign of the total gave you the winding order.

Answer 3

EDIT:

Ignore all this below. I found the issue.

The last line of the code above should be changed from:

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

to

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

Otherwise, the code works great, and I have accepted this as the answer (but I do want to give props to @winwaed who found the article with the algorithm).

---ignore--- (for historical purposes only)

Hi Dave,

I'm not sure what is happening (yet), but I am getting an incorrect response of "clockwise" from the function for outlines that are counter clockwise.

Here is one of the outlines, displayed in Inkscape 0.48, which has a (new) option to show the direction of the path with tiny half-arrow heads. As you can see, the outer path winds counter-clockwise (even though the function returned clockwise).

I'm going to look into this shortly...