Ordenar pontos no sentido horário?

Dada uma matriz de x, y pontos, como classifico os pontos dessa matriz no sentido horário (em torno do ponto central médio geral)? Meu objective é passar os pontos para uma function de criação de linha para acabar com algo que pareça “sólido”, tão convexo quanto possível, sem interseção de linhas.

Por que vale a pena, estou usando Lua, mas qualquer pseudocódigo seria apreciado. Muito obrigado por qualquer ajuda!

Atualização: Para referência, este é o código Lua baseado na excelente resposta do Ciamej (ignore meu prefixo “app”):

function appSortPointsClockwise(points) local centerPoint = appGetCenterPointOfPoints(points) app.pointsCenterPoint = centerPoint table.sort(points, appGetIsLess) return points end function appGetIsLess(a, b) local center = app.pointsCenterPoint if ax >= 0 and bx  by end local det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y) if det  0 then return false end local d1 = (ax - center.x) * (ax - center.x) + (ay - center.y) * (ay - center.y) local d2 = (bx - center.x) * (bx - center.x) + (by - center.y) * (by - center.y) return d1 > d2 end function appGetCenterPointOfPoints(points) local pointsSum = {x = 0, y = 0} for i = 1, #points do pointsSum.x = pointsSum.x + points[i].x; pointsSum.y = pointsSum.y + points[i].y end return {x = pointsSum.x / #points, y = pointsSum.y / #points} end 

Primeiro, calcule o ponto central. Em seguida, classifique os pontos usando qualquer algoritmo de sorting desejado, mas use uma rotina de comparação especial para determinar se um ponto é menor que o outro.

Você pode verificar se um ponto (a) está à esquerda ou à direita do outro (b) em relação ao centro por este simples cálculo:

 det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y) 

se o resultado for zero, então eles estão na mesma linha do centro, se for positivo ou negativo, então é de um lado ou de outro, então um ponto irá preceder o outro. Usando-o você pode construir uma relação menor do que para comparar pontos e determinar a ordem em que eles devem aparecer na matriz ordenada. Mas você tem que definir onde é o início dessa ordem, quero dizer qual será o ângulo inicial (por exemplo, a metade positiva do eixo x).

O código para a function de comparação pode ser assim:

 bool less(point a, point b) { if (ax - center.x >= 0 && bx - center.x < 0) return true; if (ax - center.x < 0 && bx - center.x >= 0) return false; if (ax - center.x == 0 && bx - center.x == 0) { if (ay - center.y >= 0 || by - center.y >= 0) return ay > by; return by > ay; } // compute the cross product of vectors (center -> a) x (center -> b) int det = (ax - center.x) * (by - center.y) - (bx - center.x) * (ay - center.y); if (det < 0) return true; if (det > 0) return false; // points a and b are on the same line from the center // check which point is closer to the center int d1 = (ax - center.x) * (ax - center.x) + (ay - center.y) * (ay - center.y); int d2 = (bx - center.x) * (bx - center.x) + (by - center.y) * (by - center.y); return d1 > d2; } 

Isso irá ordenar os pontos no sentido horário a partir das 12 horas. Pontos na mesma “hora” serão ordenados a partir dos que estão mais longe do centro.

Se estiver usando tipos inteiros (que não estão realmente presentes em Lua), você deve assegurar que as variables ​​det, d1 e d2 sejam de um tipo capaz de manter o resultado dos cálculos executados.

Se você quer conseguir algo que pareça sólido, o mais convexo possível, então eu acho que você está procurando por um Casco Convexo . Você pode calculá-lo usando o Graham Scan . Nesse algoritmo, você também precisa classificar os pontos no sentido horário (ou anti-horário) começando de um ponto de pivô especial. Em seguida, você repete os passos de loop simples a cada vez que verifica se vira à esquerda ou à direita adicionando novos pontos ao casco convexo, essa verificação é baseada em um produto cruzado, assim como na function de comparação acima.

Editar:

Adicionado mais um if se if (ay - center.y >= 0 || by - center.y >=0) para certificar-se de que os pontos que têm x = 0 e y negativo sejam classificados a partir daqueles que estão mais longe do Centro. Se você não se importa com a ordem dos pontos na mesma ‘hora’, você pode omitir esta declaração if e sempre retornar ay > by .

Corrigidas as primeiras instruções if adicionando -center.x e -center.y .

Adicionado a segunda instrução if (ax - center.x < 0 && bx - center.x >= 0) . Foi uma falha óbvia que estava faltando. As instruções if podem ser reorganizadas agora porque algumas verificações são redundantes. Por exemplo, se a primeira condição na primeira instrução if for falsa, a primeira condição da segunda deverá ser verdadeira. Decidi, no entanto, deixar o código como é para simplificar. É bem possível que o compilador otimize o código e produza o mesmo resultado de qualquer maneira.

O que você está pedindo é um sistema conhecido como coordenadas polares . A conversão de coordenadas cartesianas para polares é feita facilmente em qualquer idioma. As fórmulas podem ser encontradas nesta seção .

Não conheço Lua, mas esta página parece oferecer trechos de código para essa conversão.

Depois de converter em coordenadas polares, apenas classifique pelo ângulo, theta.

Uma abordagem alternativa interessante para o seu problema seria encontrar o mínimo aproximado para o Problema do Vendedor Viajante (TSP), ie. o caminho mais curto que liga todos os seus pontos. Se seus pontos formam um formato convexo, deve ser a solução correta, caso contrário, ele ainda deve ter boa aparência (uma forma “sólida” pode ser definida como uma que tenha uma baixa relação perímetro / área, que é o que estamos otimizando aqui) .

Você pode usar qualquer implementação de um otimizador para o TSP, o que eu tenho certeza que você pode encontrar uma tonelada em seu idioma de escolha.

Outra versão (retorna verdadeiro se vier antes de b no sentido anti-horário):

  bool lessCcw(const Vector2D &center, const Vector2D &a, const Vector2D &b) const { // Computes the quadrant for a and b (0-3): // ^ // 1 | 0 // ---+--> // 2 | 3 const int dax = ((ax() - center.x()) > 0) ? 1 : 0; const int day = ((ay() - center.y()) > 0) ? 1 : 0; const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) < < 1); /* The previous computes the following: const int qa = ( (ax() > center.x()) ? ((ay() > center.y()) ? 0 : 3) : ((ay() > center.y()) ? 1 : 2)); */ const int dbx = ((bx() - center.x()) > 0) ? 1 : 0; const int dby = ((by() - center.y()) > 0) ? 1 : 0; const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) < < 1); if (qa == qb) { return (bx() - center.x()) * (ay() - center.y()) < (by() - center.y()) * (ax() - center.x()); } else { return qa < qb; } } 

Isso é mais rápido, porque o compilador (testado no Visual C ++ 2015) não gera salto para calcular dax, day, dbx, dby. Aqui o assembly de saída do compilador:

 ; 28 : const int dax = ((ax() - center.x()) > 0) ? 1 : 0; vmovss xmm2, DWORD PTR [ecx] vmovss xmm0, DWORD PTR [edx] ; 29 : const int day = ((ay() - center.y()) > 0) ? 1 : 0; vmovss xmm1, DWORD PTR [ecx+4] vsubss xmm4, xmm0, xmm2 vmovss xmm0, DWORD PTR [edx+4] push ebx xor ebx, ebx vxorps xmm3, xmm3, xmm3 vcomiss xmm4, xmm3 vsubss xmm5, xmm0, xmm1 seta bl xor ecx, ecx vcomiss xmm5, xmm3 push esi seta cl ; 30 : const int qa = (1 - dax) + (1 - day) + ((dax & (1 - day)) < < 1); mov esi, 2 push edi mov edi, esi ; 31 : ; 32 : /* The previous computes the following: ; 33 : ; 34 : const int qa = ; 35 : ( (ax() > center.x()) ; 36 : ? ((ay() > center.y()) ? 0 : 3) ; 37 : : ((ay() > center.y()) ? 1 : 2)); ; 38 : */ ; 39 : ; 40 : const int dbx = ((bx() - center.x()) > 0) ? 1 : 0; xor edx, edx lea eax, DWORD PTR [ecx+ecx] sub edi, eax lea eax, DWORD PTR [ebx+ebx] and edi, eax mov eax, DWORD PTR _b$[esp+8] sub edi, ecx sub edi, ebx add edi, esi vmovss xmm0, DWORD PTR [eax] vsubss xmm2, xmm0, xmm2 ; 41 : const int dby = ((by() - center.y()) > 0) ? 1 : 0; vmovss xmm0, DWORD PTR [eax+4] vcomiss xmm2, xmm3 vsubss xmm0, xmm0, xmm1 seta dl xor ecx, ecx vcomiss xmm0, xmm3 seta cl ; 42 : const int qb = (1 - dbx) + (1 - dby) + ((dbx & (1 - dby)) < < 1); lea eax, DWORD PTR [ecx+ecx] sub esi, eax lea eax, DWORD PTR [edx+edx] and esi, eax sub esi, ecx sub esi, edx add esi, 2 ; 43 : ; 44 : if (qa == qb) { cmp edi, esi jne SHORT $LN37@lessCcw ; 45 : return (bx() - center.x()) * (ay() - center.y()) < (by() - center.y()) * (ax() - center.x()); vmulss xmm1, xmm2, xmm5 vmulss xmm0, xmm0, xmm4 xor eax, eax pop edi vcomiss xmm0, xmm1 pop esi seta al pop ebx ; 46 : } else { ; 47 : return qa < qb; ; 48 : } ; 49 : } ret 0 $LN37@lessCcw: pop edi pop esi setl al pop ebx ret 0 ?lessCcw@@YA_NABVVector2D@@00@Z ENDP ; lessCcw 

Apreciar.