Метод расширения 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;
    }

Примечание: я просто предполагаю, что нам нужно foreach по пунктам в GraphicsPath здесь, но если есть лучший способ, пожалуйста, не стесняйтесь предлагать.

Причина этого заключается в том, что FillMode из GraphicsPath определяет, являются ли перекрывающиеся секции соседних графических путей «заполненными» (Winding) или «отверстиями» (Alternate). Однако это верно только в том случае, если соседние графические пути намотаны в одном направлении.

Если два пути намотаны в противоположных направлениях, даже установка FillMode на Winding приведет к появлению (нежелательных) отверстий.

Интересно, что в GraphicsPath есть метод .Reverse(), который позволяет изменить направление пути (и это решает проблему), но невозможно знать, КОГДА нужно использовать GraphicsPath. Направление пути.

Можете ли вы помочь с этим методом расширения?

Answer 1

Я в основном выкладываю это, потому что этот вопрос заинтересовал меня, это было то, в чем я не разбираюсь, и я хотел бы вызвать обсуждение.

Я взял Point в многоугольном псевдокоде и попытался приспособить его к вашей ситуации. Казалось, вы заинтересованы только в определении того, что-то вращается по часовой стрелке или против часовой стрелки. Вот простой тест и очень простая (грубая по краям) реализация 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 для всех точек и использую их в качестве значения "точка в многоугольнике". Поэтому, передавая только массив точек, он найдет что-то посередине.

Я также сделал предположение, что V i + 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

EDIT:

Игнорируйте все это ниже. Я нашел проблему.

Последняя строка кода выше должна быть изменена с:

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

до

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

В противном случае код работает отлично, и я принял это как ответ (но я хочу дать реквизит @winwaed, который нашел статью с помощью алгоритма).

--- игнорировать --- (только для исторических целей)

Привет, Дейв,

Я не уверен, что происходит (пока), но я получаю неправильный ответ «по часовой стрелке» от функции для контуров, которые против часовой стрелки.

Вот один из контуров, отображаемых в Inkscape 0.48, который имеет (новую) опцию, показывающую направление пути с крошечными пол стрелками. Как видите, внешний путь вращается против часовой стрелки (даже если функция возвращена по часовой стрелке).

Я собираюсь разобраться в этом в ближайшее время ...