Mejor algoritmo para encontrar los bordes (polígono) de los 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 pude pensar es verificar uno por uno si golpean la forma formada por los otros. 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 de los algoritmos poliédricos es elegir uno que se ajuste a su entrada y a 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 finalizar con vértices, por lo que el algoritmo Graham scan para calcular los vértices del convex hull debería ser el truco, aunque podría llevar algún esfuerzo extenderlo más allá del caso 2-D. Es O (n log n) en el número 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, debe encontrar un algoritmo de coincidencia.

Answer 3

The Convex Hull es uno de los problemas más investigados de Geometría Computacional. El Graham Scan es uno de los más simples convex hull algorithms, pero ciertamente no el único. The Gift-wrapping Algorithm, también llamado Jarvis 'March, es el más simple que conozco. The Stony Brook algorithm repository tiene varias implementaciones de algoritmos de casco convexo en C y C++. Geometry in Action muestra principalmente aplicaciones de cascos convexos. Aquí hay una colección de low-dimensional y arbitrary-dimensional programas de cálculo de casco convexo.