Dada uma matriz de x, y pontos, como classifico os pontos dessa matriz na ordem dos ponteiros do relógio (em torno de seu ponto central médio geral)? Meu objetivo é passar os pontos para uma função de criação de linhas para terminar com algo parecendo "sólido", o mais convexo possível, sem que as linhas se cruzem.
Pelo que vale, estou usando Lua, mas qualquer pseudocódigo seria apreciado.
Atualização: Para referência, este é o código Lua baseado na excelente resposta de 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 a.x >= 0 and b.x < 0 then return true
elseif a.x == 0 and b.x == 0 then return a.y > b.y
end
local det = (a.x - center.x) * (b.y - center.y) - (b.x - center.x) * (a.y - center.y)
if det < 0 then return true
elseif det > 0 then return false
end
local d1 = (a.x - center.x) * (a.x - center.x) + (a.y - center.y) * (a.y - center.y)
local d2 = (b.x - center.x) * (b.x - center.x) + (b.y - center.y) * (b.y - 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
ipairs(tbl)que itera sobre os índices e valores de tbl de 1 a #tbl. Assim, para o cálculo soma, você pode fazer isso, o que a maioria das pessoas acham que parece mais limpo:for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y endipairsé significativamente mais lenta que o numérico para loop.Respostas:
Primeiro, calcule o ponto central. Em seguida, classifique os pontos usando o algoritmo de classificação que desejar, 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 cálculo simples:
se o resultado for zero, eles estarão na mesma linha do centro, se for positivo ou negativo, estará de um lado ou de outro, de modo que um ponto precederá o outro. Com ele, é possível construir uma relação menor que para comparar os pontos e determinar a ordem em que eles devem aparecer na matriz classificada. Mas você precisa definir onde está o início dessa ordem, quero dizer qual ângulo será o inicial (por exemplo, a metade positiva do eixo x).
O código para a função de comparação pode ser assim:
Isso ordenará os pontos no sentido horário a partir das 12 horas. Os pontos na mesma "hora" serão ordenados a partir dos pontos mais afastados do centro.
Se você estiver usando tipos inteiros (que não estão realmente presentes em Lua), será necessário garantir que as variáveis det, d1 e d2 sejam de um tipo capaz de manter o resultado dos cálculos realizados.
Se você deseja alcançar algo com uma aparência sólida, o mais convexa possível, acho que está procurando 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 em um ponto de articulação especial. Em seguida, você repete etapas simples do loop cada vez que verifica se você vira para a esquerda ou para a direita adicionando novos pontos ao casco convexo. Essa verificação é baseada em um produto cruzado, como na função de comparação acima.
Editar:
Adicionada mais uma instrução if
if (a.y - center.y >= 0 || b.y - center.y >=0)para garantir que os pontos que têm x = 0 e y negativo sejam classificados começando pelos pontos mais distantes do centro. Se você não se importa com a ordem dos pontos na mesma 'hora', pode omitir esta declaração if e sempre retornara.y > b.y.Corrigida a primeira instrução if com adição
-center.xe-center.y.Adicionada a segunda instrução if
(a.x - center.x < 0 && b.x - center.x >= 0). Era óbvio 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 se for falsa, a primeira condição da segunda se deve ser verdadeira. Decidi, contudo, deixar o código como é por uma questão de simplicidade. É bem possível que o compilador otimize o código e produza o mesmo resultado de qualquer maneira.fonte
atan(), nenhuma raiz quadrada e até mesmo nenhuma divisão. Este é um bom exemplo de pensamento em computação gráfica. Escolha todos os casos fáceis o mais rápido possível, e mesmo nos casos difíceis, calcule o mínimo possível para saber a resposta necessária.Uma abordagem alternativa interessante para o seu problema seria encontrar o mínimo aproximado para o Travelling Salesman Problem (TSP), ie. a rota mais curta que liga todos os seus pontos. Se os seus pontos formarem uma forma convexa, ela deve ser a solução certa; caso contrário, ainda deve ter uma boa aparência (uma forma "sólida" pode ser definida como uma que possui 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, do qual tenho certeza de que pode encontrar muito no idioma de sua escolha.
fonte
O que você está pedindo é um sistema conhecido como coordenadas polares . A conversão de coordenadas cartesianas em polares é feita facilmente em qualquer idioma. As fórmulas podem ser encontradas nesta seção .
Depois de converter para coordenadas polares, basta classificar pelo ângulo, theta.
fonte
Outra versão (retorne true se a vier antes de b no sentido anti-horário):
Isso é mais rápido, porque o compilador (testado no Visual C ++ 2015) não gera salto para calcular dax, day, dbx, dby. Aqui o conjunto de saída do compilador:
Aproveitar.
fonte
Finalmente, você recebe verts classificados no Anticlockwize
list.Reverse () .................. Orderwise_order
fonte