Método de extensão GraphicsPath.Iclockwise ()

Question

Eu preciso criar um método de extensão para um GraphicsPath objeto que determina se o GraphicsPath é enrolado no sentido horário ou no sentido anti-horário.

Algo assim:

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

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

        return bClockWise;
    }

Nota: Eu apenas assumo que precisaríamos de um foreach nos pontos no GraphicsPath Aqui, mas se houver uma maneira melhor, sinta -se à vontade para oferecer.

A razão para isso é porque o FillMode do GraphicsPath Determina se as seções sobrepostas de shatspaths de graphics adjacentes são 'preenchidas' (Winding) ou 'buracos' (Alternate). No entanto, isso só é verdade se os sigos gráficos adjacentes forem enrolados na mesma direção.

Se os dois caminhos são enrolados em direções opostas, até definir o FillMode para Winding resulta nos orifícios (indesejados).

Curiosamente, o GRAPHICICSPATH tem um .Reverse() O método que permite alterar a direção do caminho (e isso resolve o problema), mas é impossível saber quando o gráfico precisa ser revertido sem saber a direção do caminho.

Você pode ajudar com este método de extensão?

Answer 1

Estou jogando isso lá fora, porque essa pergunta pegou meu interesse, era algo em que não tenho experiência e gostaria de gerar discussões.

Eu peguei o Ponto no código pseudo-código de polígono e tentou fazê -lo se encaixar na sua situação. Parecia que você está interessado apenas em determinar se algo está enrolando no sentido horário ou no sentido anti-horário. Aqui está um teste simples e uma implementação muito simples (áspera nas bordas) 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;
}

A diferença que eu coloquei que torna isso um pouco específico para o seu problema é que calculei os valores médios de x e y de todos os pontos e use -o como o valor de "ponto no polígono". Então, passando apenas uma variedade de pontos, encontrará algo no meio deles.

Eu também assumi que o V i+1 deveria envolver quando chegar aos limites da matriz de pontos para que

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

Isso não foi otimizado, é apenas algo para potencialmente responder à sua pergunta. E talvez você já tenha inventado isso você mesmo.

Aqui está esperando críticas construtivas. :)

Answer 2

Não, você terá que dar um loop sobre os pontos para determinar a ordem de enrolamento. Existem vários algoritmos na web, por exemplo.

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

Acho que quando precisava implementá -lo, usei um algoritmo dos livros GEMS GRAPHICS, modificado para a superfície da Terra (um aplicativo geoespacial). No topo da minha cabeça, acho que ela multiplicou vetores de componentes e os resumiu. O sinal do total deu a você a ordem de enrolamento.

Answer 3

EDITAR:

Ignore tudo isso abaixo. Eu encontrei o problema.

A última linha do código acima deve ser alterada de:

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

para

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

Caso contrário, o código funciona muito bem, e eu aceitei isso como resposta (mas quero dar adereços para @winwaed que encontraram o artigo com o algoritmo).

--- ignorar --- (apenas para fins históricos)

Oi Dave,

Ainda não tenho certeza do que está acontecendo (ainda), mas estou recebendo uma resposta incorreta de "no sentido horário" da função para contornos que são no sentido horário.

Aqui está um dos contornos, exibidos no Inkscape 0.48, que possui uma opção (nova) para mostrar a direção do caminho com pequenas cabeças de meia seleção. Como você pode ver, o caminho externo serpenteia no sentido anti-horário (mesmo que a função retornasse no sentido horário).

Vou investigar isso em breve ...