Dada una matriz de puntos x, y, ¿cómo clasifico los puntos de esta matriz en el sentido de las agujas del reloj (alrededor de su punto central promedio general)? Mi objetivo es pasar los puntos a una función de creación de línea para terminar con algo que parece bastante "sólido", lo más convexo posible sin líneas que se crucen.
Por lo que vale, estoy usando Lua, pero cualquier pseudocódigo sería apreciado.
Actualización: Como referencia, este es el código Lua basado en la excelente respuesta de Ciamej (ignore mi prefijo de "aplicación"):
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 los índices y valores de tbl de 1 a #tbl. Así que para el cálculo de la suma, se puede hacer esto, que la mayoría de la gente encuentra apariencia más limpia:for _, p in ipairs(points) do pointsSum.x = pointsSum.x + p.x; pointsSum.y = pointsSum.y + p.y endipairses significativamente más lento que el numérico para el bucle.Respuestas:
Primero, calcule el punto central. Luego clasifique los puntos utilizando el algoritmo de clasificación que desee, pero utilice una rutina de comparación especial para determinar si un punto es menor que el otro.
Puede verificar si un punto (a) está a la izquierda o a la derecha del otro (b) en relación con el centro mediante este simple cálculo:
si el resultado es cero, entonces están en la misma línea desde el centro, si es positivo o negativo, entonces está de un lado o del otro, por lo que un punto precederá al otro. Al usarlo, puede construir una relación menor que para comparar puntos y determinar el orden en que deben aparecer en la matriz ordenada. Pero tiene que definir dónde está el comienzo de ese orden, quiero decir qué ángulo será el inicial (por ejemplo, la mitad positiva del eje x).
El código para la función de comparación puede verse así:
Esto ordenará los puntos en sentido horario a partir de las 12 en punto. Los puntos en la misma "hora" se ordenarán a partir de los que están más lejos del centro.
Si usa tipos enteros (que no están realmente presentes en Lua), debería asegurarse de que las variables det, d1 y d2 sean de un tipo que pueda contener el resultado de los cálculos realizados.
Si desea lograr algo que parezca sólido, lo más convexo posible, entonces supongo que está buscando un casco convexo . Puede calcularlo con Graham Scan . En este algoritmo, también debe ordenar los puntos en el sentido de las agujas del reloj (o en sentido contrario) a partir de un punto de giro especial. Luego repite pasos de bucle simples cada vez que verifica si gira a la izquierda o derecha agregando nuevos puntos al casco convexo, esta verificación se basa en un producto cruzado al igual que en la función de comparación anterior.
Editar:
Se agregó una instrucción if más
if (a.y - center.y >= 0 || b.y - center.y >=0)para asegurarse de que los puntos que tienen x = 0 y y negativo estén ordenados a partir de los que están más alejados del centro. Si no le importa el orden de los puntos en la misma 'hora', puede omitir esto si la declaración y siempre regresaa.y > b.y.Se corrigieron las primeras declaraciones if con suma
-center.xy-center.y.Se agregó la segunda declaración if
(a.x - center.x < 0 && b.x - center.x >= 0). Era un descuido obvio que faltaba. Las declaraciones if podrían reorganizarse ahora porque algunas verificaciones son redundantes. Por ejemplo, si la primera condición en la primera instrucción if es falsa, entonces la primera condición de la segunda if debe ser verdadera. Decidí, sin embargo, dejar el código como es por simplicidad. Es muy posible que el compilador optimice el código y produzca el mismo resultado de todos modos.fuente
atan(), sin raíz cuadrada, e incluso sin divisiones. Este es un buen ejemplo del pensamiento gráfico por computadora. Elimine todos los casos fáciles lo antes posible, e incluso en los casos difíciles, calcule lo menos posible para conocer la respuesta requerida.Un enfoque alternativo interesante para su problema sería encontrar el mínimo aproximado para el Problema del vendedor ambulante (TSP), es decir. La ruta más corta que une todos sus puntos. Si sus puntos forman una forma convexa, debería ser la solución correcta, de lo contrario, debería verse bien (una forma "sólida" puede definirse como una que tiene una baja relación perímetro / área, que es lo que estamos optimizando aquí) .
Puede usar cualquier implementación de un optimizador para el TSP, del cual estoy bastante seguro de que puede encontrar una tonelada en el idioma que elija.
fuente
Lo que estás pidiendo es un sistema conocido como coordenadas polares . La conversión de coordenadas cartesianas a polares se realiza fácilmente en cualquier idioma. Las fórmulas se pueden encontrar en esta sección .
Después de convertir a coordenadas polares, solo ordena por el ángulo, theta.
fuente
Otra versión (devuelve verdadero si a viene antes de b en sentido antihorario):
Esto es más rápido, porque el compilador (probado en Visual C ++ 2015) no genera salto para calcular dax, day, dbx, dby. Aquí el ensamblaje de salida del compilador:
Disfrutar.
fuente
Finalmente obtienes Vert ordenados Anticlockwize
list.Reverse () .................. Clockwise_order
fuente