El mejor algoritmo para encontrar los bordes (polígono) de vértices

Question

Tengo una gran variedad de vértices, algunos de ellos son bordes, algunos son redundantes (dentro de la forma) y quiero eliminarlos.

El algoritmo más simple que se me ocurre es verificar uno por uno si alcanzan la forma formada por los demás. Pero debería ser un algoritmo muy lento.

Pensé en elegir uno desde el borde (el más alejado del origen, por ejemplo) y calcular el camino más largo desde este comienzo ... debería obtener el camino del borde, ¿verdad?

¿Alguna sugerencia?

Answer 1

El truco con los algoritmos poliédricos es elegir uno que se ajuste a su entrada y su salida deseada, ya que hay más de una forma de representar un poliedro y la conversión entre las representaciones puede ser costosa. En este caso, está comenzando con puntos y desea terminar con vértices, por lo que el algoritmo Graham scan calcular los vértices del casco convexo debería ser el truco, aunque podría tomar algún esfuerzo extenderlo Pasó el caso 2-D. Es O ( n log n ) en la cantidad de vértices de entrada.

Answer 2

No sé cuál es el mejor algoritmo para encontrar ese polígono, pero el polígono que está buscando se llama " Convex Hull " ;.

Al buscar eso, debería encontrar un algoritmo de coincidencia.

Answer 3

El Convex Hull es uno de los problemas más investigados de la Geometría Computacional. El Graham Scan es uno de los algoritmos de casco convexo más simples, pero ciertamente no es el único. El Algoritmo de envoltura de regalos , también llamado Jarvis 'March, es el más simple que conozco. El repositorio de algoritmos Stony Brook tiene varias implementaciones de casco convexo algoritmos en C y C ++. Geometría en acción muestra principalmente aplicaciones de cascos convexos. Aquí hay una colección de baja dimensión y programas de cálculo de casco convexo de dimensiones arbitrarias .