Como determinar se uma lista de pontos poligonais está no sentido horário?

260

Tendo uma lista de pontos, como localizo se eles estão no sentido horário?

Por exemplo:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

diria que é anti-horário (ou anti-horário, para algumas pessoas).

Stécy
fonte
5
ATENÇÃO: A resposta aceita, e muitas respostas depois dela, exigem muitas adições e multiplicações (elas são baseadas em cálculos de área que terminam em negativos ou positivos; por exemplo, "fórmula de cadarço"). Antes de implementar uma delas, considere a resposta do lhf , que é mais simples / rápida - com base no wiki - orientação de polígono simples .
Home
Eu sempre penso nisso em termos do produto cruzado de dois vetores adjacentes. Se eu ando pelo perímetro do polígono, minha cabeça aponta para fora do avião. Atravesso o vetor fora do plano para o meu vetor de direção a pé para obter a terceira direção no meu sistema de coordenadas. Se esse vetor aponta para que o interior fique à minha esquerda, é no sentido anti-horário; se o interior estiver à minha direita, é no sentido horário.
Duffymo # 419

Respostas:

416

Alguns dos métodos sugeridos falharão no caso de um polígono não convexo, como um crescente. Aqui está um exemplo simples que funcionará com polígonos não convexos (até funcionará com um polígono auto-interceptável como a figura oito, informando se é principalmente no sentido horário).

Soma sobre as arestas, (x 2 - x 1 ) (y 2 + y 1 ). Se o resultado for positivo, a curva será no sentido horário; se for negativa, a curva será no sentido anti-horário. (O resultado é o dobro da área fechada, com uma convenção +/-.)

point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4
point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18
point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30
point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0
point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0
                                         ---
                                         -44  counter-clockwise
Beta
fonte
28
É cálculo aplicado a um caso simples. (Não tenho habilidade para postar gráficos.) A área sob um segmento de linha é igual à sua altura média (y2 + y1) / 2 vezes seu comprimento horizontal (x2-x1). Observe a convenção de sinal em x. Tente isso com alguns triângulos e você verá em breve como funciona.
Beta
72
Uma pequena advertência: essa resposta assume um sistema de coordenadas cartesianas normal. O motivo que vale a pena mencionar é que alguns contextos comuns, como a tela HTML5, usam um eixo Y invertido. Então a regra precisa ser invertida: se a área for negativa , a curva será no sentido horário.
LarsH 11/11
8
@ Mr.Qbs: Então, meu método funciona, mas se você pular uma parte vital , não funciona. Isso não é novidade.
Beta
11
@ Mr.Qbs: Você sempre precisa vincular o último ponto ao primeiro. Se você tiver N pontos numerados de 0 a N-1, deverá calcular: Sum( (x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]) )para i = 0 a N-1. Ou seja, deve-se levar o índice Módulo N ( N ≡ 0) A fórmula funciona apenas para polígonos fechados . Os polígonos não têm arestas imaginárias.
Olivier Jacot-Descombes
4
Este blog.element84.com/polygon-winding.html explica em inglês simples por que essa solução funciona.
David Zorychta
49

O produto cruzado mede o grau de perpendicularidade de dois vetores. Imagine que cada aresta do seu polígono é um vetor no plano xy de um espaço tridimensional (3-D) xyz. O produto cruzado de duas arestas sucessivas é um vetor na direção z (direção z positiva se o segundo segmento for no sentido horário, menos a direção z se for no sentido anti-horário). A magnitude desse vetor é proporcional ao seno do ângulo entre as duas arestas originais, portanto atinge o máximo quando são perpendiculares e diminui para desaparecer quando as arestas são colineares (paralelas).

Portanto, para cada vértice (ponto) do polígono, calcule a magnitude do produto cruzado das duas arestas adjacentes:

Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)

Portanto, rotule as arestas consecutivamente como
edgeAé o segmento de point0para point1e
edgeBentre point1para point2
...
edgeEé entre point4e point0.

Então o vértice A ( point0) está entre
edgeE[From point4to point0]
edgeA[From point0to `point1 '

Essas duas arestas são vetores, cujas coordenadas x e y podem ser determinadas subtraindo as coordenadas de seus pontos inicial e final:

edgeE= point0- point4= (1, 0) - (5, 0)= (-4, 0) e
edgeA= point1- point0= (6, 4) - (1, 0)= (5, 4) e

E o produto de cruzamento destas duas bordas adjacentes é calculada usando o determinante da matriz seguinte, o qual é construído colocando as coordenadas dos dois vectores abaixo os símbolos que representam as três coordenadas eixo ( i, j, & k). A terceira coordenada avaliada (zero) existe porque o conceito de produto cruzado é uma construção 3D e, portanto, estendemos esses vetores 2-D em 3-D para aplicar o produto cruzado:

 i    j    k 
-4    0    0
 1    4    0    

Dado que todos os produtos cruzados produzem um vetor perpendicular ao plano de dois vetores sendo multiplicados, o determinante da matriz acima tem apenas um kcomponente (ou eixo z).
A fórmula para calcular a magnitude do kcomponente ou do eixo z é
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16

A magnitude desse valor ( -16) é uma medida do seno do ângulo entre os 2 vetores originais, multiplicado pelo produto das magnitudes dos 2 vetores.
Na verdade, outra fórmula para seu valor é
A X B (Cross Product) = |A| * |B| * sin(AB).

Portanto, voltando a uma medida do ângulo, você precisa dividir esse valor ( -16) pelo produto das magnitudes dos dois vetores.

|A| * |B| = 4 * Sqrt(17) =16.4924...

Então a medida do pecado (AB) = -16 / 16.4924=-.97014...

Esta é uma medida de se o próximo segmento após o vértice se curvou para a esquerda ou direita e quanto. Não há necessidade de tomar arco-seno. Tudo o que nos importa é a sua magnitude e, claro, o seu sinal (positivo ou negativo)!

Faça isso para cada um dos outros 4 pontos ao redor do caminho fechado e adicione os valores desse cálculo em cada vértice.

Se a soma final for positiva, você foi no sentido horário, negativo e anti-horário.

Charles Bretana
fonte
3
Na verdade, esta solução é uma solução diferente da solução aceita. Se eles são equivalentes ou não, é uma pergunta que estou investigando, mas suspeito que não ... A resposta aceita calcula a área do polígono, calculando a diferença entre a área sob a borda superior do polígono e a área sob a borda inferior do polígono. Um será negativo (aquele em que você está passando da esquerda para a direita) e o outro será negativo. Ao percorrer no sentido horário, a borda superior é deslocada da esquerda para a direita e é maior, portanto o total é positivo.
22813 Charles Bretana
1
Minha solução mede a soma dos senos das mudanças nos ângulos das arestas em cada vértice. Isso será positivo ao percorrer no sentido horário e negativo ao percorrer no sentido anti-horário.
Charles Bretana 06/04
2
Parece com esta abordagem que você precisa tomar o arco seno, a menos que você assume convexidade (caso em que você só precisa verificar um vértice)
agentp
2
Você precisa tomar o arcsin. Experimente em um monte de polígonos não convexos aleatórios e você descobrirá que o teste falhará em alguns polígonos se você não usar o arcsin.
Luke Hutchison
1
@CharlesBretana - embora eu não tenha executado o teste de Luke, acredito que ele esteja correto. Essa é a natureza da soma combinada com uma escala não linear [sem arcsin vs. arcsin]. Considere o que marsbear sugeriu e que você rejeitou corretamente. Ele sugeriu que você "apenas contasse" e apontou que um punhado de valores grandes poderia superar um grande número de valores pequenos. Agora considere arcsin de cada valor vs não. Ainda não é o caso de não tomar arcsin dar peso incorreto a cada valor, portanto, tem a mesma falha (embora muito menos)?
Home
47

Acho que essa é uma pergunta bastante antiga, mas vou lançar outra solução de qualquer maneira, porque é direta e não matematicamente intensa - ela usa apenas álgebra básica. Calcule a área assinada do polígono. Se negativo, os pontos estão no sentido horário, se positivo, estão no sentido anti-horário. (Isso é muito semelhante à solução Beta).

Calcule a área assinada: A = 1/2 * (x 1 * y 2 - x 2 * y 1 + x 2 * y 3 - x 3 * y 2 + ... + x n * y 1 - x 1 * y n )

Ou no pseudo-código:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2

Observe que, se você estiver apenas verificando o pedido, não precisará se preocupar em dividir por 2.

Fontes: http://mathworld.wolfram.com/PolygonArea.html

Sean, o Feijão
fonte
Isso foi um erro de digitação na fórmula da sua área assinada acima? Termina com "xn * y1 - x1 * yn"; quando acredito que deveria ser "x_n y_ {n + 1} - y_n x_ {n-1}" (no LaTeX, pelo menos). Por outro lado, já se passaram dez anos desde que fiz aulas de álgebra linear.
Michael Eric Oberlin
Não. Se você verificar a fonte , verá que a fórmula de fato faz referência ao primeiro ponto novamente no último termo (y1 e x1). (Desculpe, eu não estou muito familiarizado com o LaTeX, mas eu formatado os subscritos para torná-los mais legíveis.)
Sean Bean
Usei esta solução e ela funcionou perfeitamente para o meu uso. Observe que, se você pode planejar com antecedência e poupar e extra dois vetores em sua matriz, poderá se livrar da comparação (ou%) adicionando o primeiro vetor na cauda da matriz. Dessa forma, você simplesmente passa por todos os elementos, exceto o último (comprimento-2 em vez de comprimento-1).
Eric Fortier
2
@EricFortier - FWIW, em vez de redimensionar uma matriz possivelmente grande, uma alternativa eficiente é que cada iteração salve seu ponto previousPointda próxima iteração. Antes de iniciar o loop, defina previousPointo último ponto da matriz. O trade-off é uma cópia extra local da variável, mas menos acessos à matriz. E o mais importante, não precisa tocar na matriz de entrada.
Home
2
@MichaelEricOberlin - é necessário fechar o polígono, incluindo o segmento de linha do último ponto ao primeiro ponto. (Um cálculo correcto será o mesmo, não importa qual o ponto inicia o polígono fechado.)
ToolmakerSteve
38

Encontre o vértice com o menor y (e o maior x se houver laços). Seja o vértice Ae o vértice anterior na lista seja Be o próximo vértice na lista seja C. Agora calcule o sinal do produto cruzado de ABe AC.


Referências:

lhf
fonte
7
Isso também é explicado em en.wikipedia.org/wiki/Curve_orientation . O ponto é que o ponto encontrado deve estar no casco convexo e é necessário apenas olhar localmente em um único ponto no casco convexo (e seus vizinhos imediatos) para determinar a orientação de todo o polígono.
M Katz
1
Chocado e impressionado, isso não recebeu mais votos. Para polígonos simples ( que é a maioria dos polígonos em alguns campos ), essa resposta gera uma O(1)solução. Todas as outras respostas produzem O(n)soluções para no número de pontos poligonais. Para otimizações ainda mais profundas, consulte a subseção Considerações práticas do fantástico artigo de orientação de curvas da Wikipedia .
perfil completo de Cecil Curry
8
Esclarecimento: essa solução éO(1)apenas se (A) esse polígono é convexo (nesse caso, qualquer vértice arbitrário reside no casco convexo e, portanto, é suficiente) ou (B) você já conhece o vértice com a menor coordenada Y. Se esse não foro caso (ou seja, esse polígono não é convexo e você não sabe nada sobre isso),O(n)é necessáriaumapesquisa. Como nenhum somatório é necessário, no entanto, isso ainda é muito mais rápido do que qualquer outra solução para polígonos simples.
perfil completo de Cecil Curry
1
@CecilCurry Acho que seu segundo comentário explica por que isso não recebeu mais votos positivos. Ele gera respostas erradas em certos cenários, sem nenhuma menção a essas limitações.
LarsH
24

Aqui está uma implementação simples de C # do algoritmo com base nesta resposta .

Vamos supor que temos um Vectortipo tendo Xe Ypropriedades do tipo double.

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

%é o operador de módulo ou restante executando a operação de módulo que (de acordo com a Wikipedia ) encontra o restante após a divisão de um número por outro.

Olivier Jacot-Descombes
fonte
6

Comece em um dos vértices e calcule o ângulo subtendido por cada lado.

O primeiro e o último serão zero (pule esses); para o resto, o seno do ângulo será dado pelo produto cruzado das normalizações para o comprimento unitário de (ponto [n] - ponto [0]) e (ponto [n-1] - ponto [0]).

Se a soma dos valores for positiva, seu polígono será desenhado no sentido anti-horário.

Steve Gilham
fonte
Como o produto cruzado se resume basicamente a um fator de escala positivo vezes o seno do ângulo, provavelmente é melhor fazer apenas um produto cruzado. Vai ser mais rápido e menos complicado.
ReaperUnreal
4

Pelo que vale, usei esse mixin para calcular a ordem de enrolamento dos aplicativos da API do Google Maps v3.

O código aproveita o efeito colateral das áreas poligonais: uma ordem de vértices no sentido horário produz uma área positiva, enquanto uma ordem de giro no sentido anti-horário dos mesmos vértices produz a mesma área que um valor negativo. O código também usa uma espécie de API privada na biblioteca de geometria do Google Maps. Eu me senti confortável em usá-lo - use por seu próprio risco.

Uso da amostra:

var myPolygon = new google.maps.Polygon({/*options*/});
var isCW = myPolygon.isPathClockwise();

Exemplo completo com testes de unidade @ http://jsfiddle.net/stevejansen/bq2ec/

/** Mixin to extend the behavior of the Google Maps JS API Polygon type
 *  to determine if a polygon path has clockwise of counter-clockwise winding order.
 *  
 *  Tested against v3.14 of the GMaps API.
 *
 *  @author  [email protected]
 *
 *  @license http://opensource.org/licenses/MIT
 *
 *  @version 1.0
 *
 *  @mixin
 *  
 *  @param {(number|Array|google.maps.MVCArray)} [path] - an optional polygon path; defaults to the first path of the polygon
 *  @returns {boolean} true if the path is clockwise; false if the path is counter-clockwise
 */
(function() {
  var category = 'google.maps.Polygon.isPathClockwise';
     // check that the GMaps API was already loaded
  if (null == google || null == google.maps || null == google.maps.Polygon) {
    console.error(category, 'Google Maps API not found');
    return;
  }
  if (typeof(google.maps.geometry.spherical.computeArea) !== 'function') {
    console.error(category, 'Google Maps geometry library not found');
    return;
  }

  if (typeof(google.maps.geometry.spherical.computeSignedArea) !== 'function') {
    console.error(category, 'Google Maps geometry library private function computeSignedArea() is missing; this may break this mixin');
  }

  function isPathClockwise(path) {
    var self = this,
        isCounterClockwise;

    if (null === path)
      throw new Error('Path is optional, but cannot be null');

    // default to the first path
    if (arguments.length === 0)
        path = self.getPath();

    // support for passing an index number to a path
    if (typeof(path) === 'number')
        path = self.getPaths().getAt(path);

    if (!path instanceof Array && !path instanceof google.maps.MVCArray)
      throw new Error('Path must be an Array or MVCArray');

    // negative polygon areas have counter-clockwise paths
    isCounterClockwise = (google.maps.geometry.spherical.computeSignedArea(path) < 0);

    return (!isCounterClockwise);
  }

  if (typeof(google.maps.Polygon.prototype.isPathClockwise) !== 'function') {
    google.maps.Polygon.prototype.isPathClockwise = isPathClockwise;
  }
})();
Steve Jansen
fonte
Ao tentar isso, obtenho exatamente o resultado oposto: um polígono desenhado no sentido horário produz uma área negativa, enquanto um polígono desenhado no sentido horário produz um resultado positivo. Nos dois casos, esse trecho ainda é super útil em 5 anos, obrigado.
Cameron Roberts
@CameronRoberts A norma (consulte IETF em particular para geoJson) é seguir a 'regra da mão direita'. Eu acho que o Google está reclamando. Nesse caso, o anel externo deve estar no sentido anti-horário (com área positiva) e os anéis internos (orifícios) estão girando no sentido horário (área negativa a ser removida da área principal).
Allez l'OM
4

Uma implementação da resposta de Sean em JavaScript:

function calcArea(poly) {
    if(!poly || poly.length < 3) return null;
    let end = poly.length - 1;
    let sum = poly[end][0]*poly[0][1] - poly[0][0]*poly[end][1];
    for(let i=0; i<end; ++i) {
        const n=i+1;
        sum += poly[i][0]*poly[n][1] - poly[n][0]*poly[i][1];
    }
    return sum;
}

function isClockwise(poly) {
    return calcArea(poly) > 0;
}

let poly = [[352,168],[305,208],[312,256],[366,287],[434,248],[416,186]];

console.log(isClockwise(poly));

let poly2 = [[618,186],[650,170],[701,179],[716,207],[708,247],[666,259],[637,246],[615,219]];

console.log(isClockwise(poly2));

Tenho certeza que isso está certo. Parece que está funcionando :-)

Esses polígonos ficam assim, se você está se perguntando:

mpen
fonte
3

Esta é a função implementada para o OpenLayers 2 . A condição para ter um polígono no sentido horário é area < 0, confirmada por esta referência .

function IsClockwise(feature)
{
    if(feature.geometry == null)
        return -1;

    var vertices = feature.geometry.getVertices();
    var area = 0;

    for (var i = 0; i < (vertices.length); i++) {
        j = (i + 1) % vertices.length;

        area += vertices[i].x * vertices[j].y;
        area -= vertices[j].x * vertices[i].y;
        // console.log(area);
    }

    return (area < 0);
}
MSS
fonte
Openlayers é uma biblioteca javascript baseado mapa gestão como googlemaps e é escreveu e usado em openlayers 2.
MSS
Você pode explicar um pouco o que seu código faz e por que está fazendo isso?
N26 26/02
@ nbro este código implementa a resposta lhf . É fácil manter a parte não OpenLayer em uma função javascript pura, tendo vértices diretamente como parâmetro. Funciona bem e pode ser adaptado ao caso do multiPolygon .
Allez l'OM
2

Se você usa o Matlab, a função ispolycwretornará true se os vértices do polígono estiverem no sentido horário.

Frederick
fonte
1

Como também explicado neste artigo da Wikipedia Orientação em curva , dados 3 pontos p, qe rno plano (ou seja, com coordenadas x e y), você pode calcular o sinal do seguinte determinante

insira a descrição da imagem aqui

Se o determinante for negativo (ie Orient(p, q, r) < 0), o polígono será orientado no sentido horário (CW). Se o determinante for positivo (ou seja Orient(p, q, r) > 0), o polígono é orientado no sentido anti-horário (CCW). O determinante é zero (ou seja Orient(p, q, r) == 0) se pontos p, qe rsão colineares .

Na fórmula acima, nós preceder os em frente das coordenadas p, q e rporque está a utilizar coordenadas homogéneas .

Ian
fonte
@ tibetty Você pode explicar por que esse método não funcionaria em muitas situações se o polígono é côncavo?
Nbro 25/02/19
1
Por favor, olhe a última tabela na referência de item do wiki em sua postagem. É fácil para mim dar um exemplo falso, mas difícil de provar.
Tibetty
1
Por favor, olhe a última tabela na referência de item do wiki em sua postagem. É fácil para mim dar um exemplo falso, mas difícil de provar.
Tibetty
1
@tibetty está correto. Você não pode simplesmente levar três pontos ao longo do polígono; você pode estar em uma região convexa ou côncava desse polígono. Lendo cuidadosamente o wiki, é preciso levar três pontos ao longo do casco convexo que envolve o polígono . De "considerações práticas": "Não é necessário construir o casco convexo de um polígono para encontrar um vértice adequado. Uma escolha comum é o vértice do polígono com a menor coordenada X. Se houver vários deles, o único com a menor coordenada Y é selecionada. É garantido que seja [um] vértice do casco convexo do polígono. "
Home
1
Daí a resposta anterior do lhf , que é semelhante e faz referência ao mesmo artigo da wiki, mas especifica esse ponto. [Aparentemente, não importa se alguém leva a menor ou a maior, x ou y, desde que evite ficar no meio; efetivamente um está trabalhando de uma borda da caixa delimitadora ao redor do polígono, a garantia de uma região côncava].
ToolmakerSteve
0

Penso que, para que alguns pontos sejam dados no sentido horário, todas as arestas precisam ser positivas, não apenas a soma das arestas. Se uma aresta for negativa, pelo menos 3 pontos serão dados no sentido anti-horário.

daniel
fonte
É verdade, mas você não entende o conceito da ordem de enrolamento de um polígono (no sentido horário ou anti-horário). Em um polígono totalmente convexo, o ângulo em todos os pontos será no sentido horário ou todos no sentido anti-horário [como em sua primeira frase]. Em um polígono com região (s) côncava (s), as "cavernas" estarão na direção oposta, mas o polígono como um todo ainda possui um interior bem definido e é considerado no sentido horário ou anti-horário de acordo. Veja en.wikipedia.org/wiki/…
ToolmakerSteve
0

Minha solução C # / LINQ é baseada nos conselhos de vários produtos da @charlesbretana abaixo. Você pode especificar uma referência normal para o enrolamento. Ele deve funcionar desde que a curva esteja principalmente no plano definido pelo vetor up.

using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace SolidworksAddinFramework.Geometry
{
    public static class PlanePolygon
    {
        /// <summary>
        /// Assumes that polygon is closed, ie first and last points are the same
        /// </summary>
       public static bool Orientation
           (this IEnumerable<Vector3> polygon, Vector3 up)
        {
            var sum = polygon
                .Buffer(2, 1) // from Interactive Extensions Nuget Pkg
                .Where(b => b.Count == 2)
                .Aggregate
                  ( Vector3.Zero
                  , (p, b) => p + Vector3.Cross(b[0], b[1])
                                  /b[0].Length()/b[1].Length());

            return Vector3.Dot(up, sum) > 0;

        } 

    }
}

com um teste de unidade

namespace SolidworksAddinFramework.Spec.Geometry
{
    public class PlanePolygonSpec
    {
        [Fact]
        public void OrientationShouldWork()
        {

            var points = Sequences.LinSpace(0, Math.PI*2, 100)
                .Select(t => new Vector3((float) Math.Cos(t), (float) Math.Sin(t), 0))
                .ToList();

            points.Orientation(Vector3.UnitZ).Should().BeTrue();
            points.Reverse();
            points.Orientation(Vector3.UnitZ).Should().BeFalse();



        } 
    }
}
bradgonesurfing
fonte
0

Esta é a minha solução usando as explicações nas outras respostas:

def segments(poly):
    """A sequence of (x,y) numeric coordinates pairs """
    return zip(poly, poly[1:] + [poly[0]])

def check_clockwise(poly):
    clockwise = False
    if (sum(x0*y1 - x1*y0 for ((x0, y0), (x1, y1)) in segments(poly))) < 0:
        clockwise = not clockwise
    return clockwise

poly = [(2,2),(6,2),(6,6),(2,6)]
check_clockwise(poly)
False

poly = [(2, 6), (6, 6), (6, 2), (2, 2)]
check_clockwise(poly)
True
Gianni Spear
fonte
1
Você pode especificar em quais outras respostas exatamente essa resposta se baseia?
N
0

Um método muito mais computacionalmente mais simples, se você já conhece um ponto dentro do polígono :

  1. Escolha qualquer segmento de linha do polígono original, pontos e suas coordenadas nessa ordem.

  2. Adicione um ponto "interno" conhecido e forme um triângulo.

  3. Calcule CW ou CCW como sugerido aqui com esses três pontos.

Venkata Goli
fonte
Talvez isso funcione se o polígono for totalmente convexo. Definitivamente, não é confiável se houver regiões côncavas - é fácil escolher um ponto do lado "errado" de uma das bordas da caverna e conectá-lo a essa borda. Receberá resposta errada.
Home
Funciona mesmo que o polígono seja côncavo. O ponto precisa estar dentro desse polígono côncavo. No entanto, eu não estou certo sobre polígono complexo (não teste.)
Venkata Goli
"Funciona mesmo que o polígono seja côncavo." - Contra-exemplo: poli (0,0), (1,1), (0,2), (2,2), (2,0). Segmento de linha (1,1), (0, 2). Se você escolher um ponto interior entre (1,1), (0,2), (1,2) para formar um triângulo -> (1,1), (0,2), (0,5,1,5)), obtém enrolamento oposto do que se você escolher um ponto interior entre (0,0), (1,1), (1,0)> (1,1), (0,2), (0,5,0,5). Ambos são interiores ao polígono original, mas têm enrolamentos opostos. Portanto, um deles dá a resposta errada.
precisa
Em geral, se um polígono tiver alguma região côncava, escolha um segmento na região côncava. Por ser côncavo, você pode encontrar dois pontos "interiores" que estão em lados opostos dessa linha. Por estarem em lados opostos dessa linha, os triângulos formados têm enrolamentos opostos. Fim da prova.
Home
0

Após testar várias implementações não confiáveis, o algoritmo que forneceu resultados satisfatórios em relação à orientação CW / CCW fora da caixa foi o postado pelo OP neste segmento (shoelace_formula_3 ).

Como sempre, um número positivo representa uma orientação CW, enquanto um número negativo CCW.

Marjan Moderc
fonte
0

Aqui está a solução 3.0 rápida, com base nas respostas acima:

    for (i, point) in allPoints.enumerated() {
        let nextPoint = i == allPoints.count - 1 ? allPoints[0] : allPoints[i+1]
        signedArea += (point.x * nextPoint.y - nextPoint.x * point.y)
    }

    let clockwise  = signedArea < 0
Toby Evetts
fonte
0

Outra solução para isso;

const isClockwise = (vertices=[]) => {
    const len = vertices.length;
    const sum = vertices.map(({x, y}, index) => {
        let nextIndex = index + 1;
        if (nextIndex === len) nextIndex = 0;

        return {
            x1: x,
            x2: vertices[nextIndex].x,
            y1: x,
            y2: vertices[nextIndex].x
        }
    }).map(({ x1, x2, y1, y2}) => ((x2 - x1) * (y1 + y2))).reduce((a, b) => a + b);

    if (sum > -1) return true;
    if (sum < 0) return false;
}

Pegue todos os vértices como uma matriz como esta;

const vertices = [{x: 5, y: 0}, {x: 6, y: 4}, {x: 4, y: 5}, {x: 1, y: 5}, {x: 1, y: 0}];
isClockwise(vertices);
Ind
fonte
0

Solução para R para determinar a direção e reverter no sentido horário (considerado necessário para objetos owin):

coords <- cbind(x = c(5,6,4,1,1),y = c(0,4,5,5,0))
a <- numeric()
for (i in 1:dim(coords)[1]){
  #print(i)
  q <- i + 1
  if (i == (dim(coords)[1])) q <- 1
  out <- ((coords[q,1]) - (coords[i,1])) * ((coords[q,2]) + (coords[i,2]))
  a[q] <- out
  rm(q,out)
} #end i loop

rm(i)

a <- sum(a) #-ve is anti-clockwise

b <- cbind(x = rev(coords[,1]), y = rev(coords[,2]))

if (a>0) coords <- b #reverses coords if polygon not traced in anti-clockwise direction
dez
fonte
0

Embora essas respostas estejam corretas, elas são mais matematicamente intensas do que o necessário. Assuma as coordenadas do mapa, onde o ponto mais ao norte é o ponto mais alto no mapa. Encontre o ponto mais ao norte e, se 2 pontos estiverem empatados, é o mais ao norte e o mais ao leste (este é o ponto que lhf usa em sua resposta). Nos seus pontos,

ponto [0] = (5,0)

ponto [1] = (6,4)

ponto [2] = (4,5)

ponto [3] = (1,5)

ponto [4] = (1,0)

Se assumirmos que P2 é o ponto mais ao norte, então o ponto leste, o ponto anterior ou o próximo, determinam no sentido horário, CW ou CCW. Como o ponto mais ao norte está na face norte, se o P1 (anterior) ao P2 se mover para o leste, a direção é CW. Nesse caso, ele se move para oeste, então a direção é anti-horária, como diz a resposta aceita. Se o ponto anterior não tiver movimento horizontal, o mesmo sistema se aplica ao próximo ponto, P3. Se P3 estiver a oeste de P2, o movimento é no sentido anti-horário. Se o movimento P2 para P3 for leste, é oeste neste caso, o movimento é CW. Suponha que nte, P2 nos seus dados, seja o ponto mais ao norte que o leste e o prv seja o ponto anterior, P1 nos seus dados e nxt seja o próximo ponto, P3 nos seus dados e [0] seja horizontal ou leste / oeste, onde oeste é menor que leste e [1] é vertical.

if (nte[0] >= prv[0] && nxt[0] >= nte[0]) return(CW);
if (nte[0] <= prv[0] && nxt[0] <= nte[0]) return(CCW);
// Okay, it's not easy-peasy, so now, do the math
if (nte[0] * nxt[1] - nte[1] * nxt[0] - prv[0] * (nxt[1] - crt[1]) + prv[1] * (nxt[0] - nte[0]) >= 0) return(CCW); // For quadrant 3 return(CW)
return(CW) // For quadrant 3 return (CCW)
VectorVortec
fonte
IMHO, seria mais seguro manter a matemática fundamental mostrada na resposta da lhf - obrigado por mencioná-lo. O desafio de reduzi-lo a quadrantes é que é uma quantidade razoável de trabalho para provar que sua fórmula está correta em todos os casos. Você calculou corretamente "mais a oeste"? Em um polígono côncavo onde ambos [1] e [3] são "oeste e sul" de [2]? Você lidou corretamente com comprimentos diferentes de [1] e [3] nessa situação? Eu não tenho ideia, enquanto se eu calcular diretamente esse ângulo (ou seu determinante), estou usando fórmulas conhecidas.
Home
@ToolmakerSteve as instruções if sempre funcionam se os 3 pontos forem convexos. As declarações if retornarão, então você obterá a resposta certa. As instruções if não retornarão, se a forma for côncava e extrema. É quando você tem que fazer as contas. A maioria das imagens possui um quadrante, facilitando a parte. Mais de 99% das minhas chamadas de sub-rotina são tratadas pelas instruções if.
VectorVortec 6/02/19
Isso não trata da minha preocupação. Qual é essa fórmula? É a determinante da orientação, conforme indicado no link wiki da resposta da lhf? Se sim, então diga. Explique que o que você está fazendo é verificações rápidas que lidam com a maioria dos casos, para evitar a matemática padrão. Se é assim, então sua resposta agora faz sentido para mim. (Menor nit: seria mais fácil de ler se você usou .xe .yde uma estrutura, em vez de [0]e [1]eu não sabia o que seu código estava dizendo, primeira vez que eu olhei para ele..)
ToolmakerSteve
Como não confiava na sua abordagem, implementei a abordagem da lhf ; fórmula a partir de seu link. A parte lenta é encontrar a pesquisa apropriada de vértice - O (N). Uma vez encontrado, o determinante é uma operação O (1), usando 6 multiplicações com 5 adições. Essa última parte é o que você otimizou; mas você fez isso adicionando testes if adicionais. Pessoalmente, não posso justificar a adoção de uma abordagem fora do padrão - seria necessário verificar se cada etapa está correta - mas obrigado por uma análise interessante dos quadrantes!
Home
0

Código C # para implementar a resposta do lhf :

// https://en.wikipedia.org/wiki/Curve_orientation#Orientation_of_a_simple_polygon
public static WindingOrder DetermineWindingOrder(IList<Vector2> vertices)
{
    int nVerts = vertices.Count;
    // If vertices duplicates first as last to represent closed polygon,
    // skip last.
    Vector2 lastV = vertices[nVerts - 1];
    if (lastV.Equals(vertices[0]))
        nVerts -= 1;
    int iMinVertex = FindCornerVertex(vertices);
    // Orientation matrix:
    //     [ 1  xa  ya ]
    // O = | 1  xb  yb |
    //     [ 1  xc  yc ]
    Vector2 a = vertices[WrapAt(iMinVertex - 1, nVerts)];
    Vector2 b = vertices[iMinVertex];
    Vector2 c = vertices[WrapAt(iMinVertex + 1, nVerts)];
    // determinant(O) = (xb*yc + xa*yb + ya*xc) - (ya*xb + yb*xc + xa*yc)
    double detOrient = (b.X * c.Y + a.X * b.Y + a.Y * c.X) - (a.Y * b.X + b.Y * c.X + a.X * c.Y);

    // TBD: check for "==0", in which case is not defined?
    // Can that happen?  Do we need to check other vertices / eliminate duplicate vertices?
    WindingOrder result = detOrient > 0
            ? WindingOrder.Clockwise
            : WindingOrder.CounterClockwise;
    return result;
}

public enum WindingOrder
{
    Clockwise,
    CounterClockwise
}

// Find vertex along one edge of bounding box.
// In this case, we find smallest y; in case of tie also smallest x.
private static int FindCornerVertex(IList<Vector2> vertices)
{
    int iMinVertex = -1;
    float minY = float.MaxValue;
    float minXAtMinY = float.MaxValue;
    for (int i = 0; i < vertices.Count; i++)
    {
        Vector2 vert = vertices[i];
        float y = vert.Y;
        if (y > minY)
            continue;
        if (y == minY)
            if (vert.X >= minXAtMinY)
                continue;

        // Minimum so far.
        iMinVertex = i;
        minY = y;
        minXAtMinY = vert.X;
    }

    return iMinVertex;
}

// Return value in (0..n-1).
// Works for i in (-n..+infinity).
// If need to allow more negative values, need more complex formula.
private static int WrapAt(int i, int n)
{
    // "+n": Moves (-n..) up to (0..).
    return (i + n) % n;
}
Fabricante de ferramentas
fonte
1
Parece ser para as coordenadas Y negativas. Gire CW / CCW para coordenadas padrão.
Warwick Allison
0

Aqui está uma implementação simples do Python 3 com base nesta resposta (que, por sua vez, se baseia na solução proposta na resposta aceita )

def is_clockwise(points):
    # points is your list (or array) of 2d points.
    assert len(points) > 0
    s = 0.0
    for p1, p2 in zip(points, points[1:] + [points[0]]):
        s += (p2[0] - p1[0]) * (p2[1] + p1[1])
    return s > 0.0
nbro
fonte
-4

encontre o centro de massa desses pontos.

suponha que existam linhas deste ponto para seus pontos.

Encontre o ângulo entre duas linhas para a linha0 linha1

do que para as linhas 1 e 2

...

...

se esse ângulo estiver aumentando monotonicamente do que no sentido anti-horário,

caso contrário, se diminuir monotonicamente, é no sentido horário

mais (não é monotônico)

você não pode decidir, então não é sábio

ufukgun
fonte
por "centro de massa" eu acho que você quer dizer "centróide"?
Vicky Chijwani 9/10/12
Provavelmente funciona se o polígono for totalmente convexo. Mas é melhor usar uma resposta que funcione para polígonos não convexos.
Home