Melhor algoritmo para encontrar as bordas (polígono) de vértices

Question

Eu tenho uma grande variedade de vértices, alguns deles são bordas, alguns são redundantes (dentro da forma) e eu quero remover aqueles.

O algoritmo mais simples que eu poderia pensar é verificar um por um, se bater a forma formado pelos outros. Mas deve ser um algoritmo muito lento.

Eu pensei em escolher um a partir da borda (aquele mais distante da origem por exemplo) e calcular o caminho mais longo a partir deste início ... deve obter o caminho borda, certo?

Qualquer sugestão?

Answer 1

O truque com algoritmos poliédricas é escolher um que se encaixa com a sua entrada e sua saída desejada, já que há mais de uma maneira para representar um poliedro e conversão entre as representações podem ser caros. Neste caso, você está começando com pontos e quer acabar com vértices, de modo que o Graham varredura algoritmo para calcular os vértices do convexo casco deve fazer o truque, embora possa demorar algum esforço para estender -lo após o caso 2-D. É de O ( n log n ) no número de vértices de entrada.

Answer 2

Eu não sei qual é o melhor algoritmo para descobrir que polígono é, mas o polígono que você está procurando é chamado de "Convex casco".

Ao pesquisar para isso, você deve encontrar um algoritmo de correspondência.

Answer 3

A Convex casco é um dos problemas mais pesquisados ??de Computational Geometry. O Exame de Graham é um dos mais simples convexo algoritmos casco , mas certamente não o único. The Gift-embrulho Algoritmo , também chamado de Jarvis' de março, é o mais simples que eu conheço. O repositório algoritmo Stony Brook tem várias implementações de casco convexo algoritmos em C e C ++. geometria em programas de acção principalmente aplicações de cascas convexas. Aqui está uma coleção de low-dimensional e arbitrária-dimensional convexo casco cálculo programas