Minimizar Polygon Vértices

Question

O que é um bom algoritmo para reduzir o número de vértices em um polígono sem alterar a forma como ele se parece muito?

Input: Um polígono, representado como uma lista de pontos, com forma muitas vértices:. Entrada bruta do rato, por exemplo

Output: Um polígono com muito menos vértices que ainda se parece muito com o original: utilizável algo para detecção de colisão, por exemplo (não necessariamente convexo)

.

Edit: A solução para isso seria semelhante a encontrar uma linha multi-segmentada de melhor ajuste em um gráfico. É chamado segmentadas Mínimos Quadrados em meu algoritmos livro.

Edit2:. O Peucker Algoritmo Douglas é o que eu realmente quero

Answer 1

Edit: Oh olhar, Simplificar Polígonos

Você mencionou detecção de colisão. Você poderia ir realmente simples e calcular um casco delimitadora convexo em torno dele.

Se você se preocupava com as áreas côncavas, você pode calcular um casco côncavo tomando o centróide de seu polígono, e escolhendo um ponto para começar. A partir da rotação ponto de partida em torno do baricentro, encontrando cada vértice que deseja manter, e atribuindo isso como o próximo vértice no casco delimitadora. A complexidade do algoritmo viria na forma como você determinou quais vértices para manter, mas eu tenho certeza que você pensou que já. Você pode jogar todos os seus vértices em baldes com base em sua localização em relação ao centróide. Quando um balde fica mais do que um número arbitrário de vértices completos, você pode dividi-lo. Em seguida, tomar a média dos vértices em que balde como o vértice para usar em seu casco delimitadora. Ou, esqueça os baldes, e quando você está se movendo ao redor do baricentro, só escolher um ponto se o seu mais de uma determinada distância a partir do último ponto.

Na verdade, você poderia provavelmente apenas usar todos os vértices em seu polígono como "nuvem de pontos" e calcular o casco côncavo em torno disso. Eu vou olhar para um link algoritmo. Pior caso sobre isso seria um polígono convexo completamente.

Outra alternativa é começar com um retângulo delimitador. Para cada vértice no retângulo, saber a distância do ponto ao polígono. Para o vértice mais distante, dividi-lo em mais dois vértices e movê-los em alguns. Repita até que alguma proporção de tanto vértices ou área for atendida. Eu teria que pensar sobre os detalhes de um presente um pouco mais.

Se você se preocupa com o polígono realmente olhando semelhante, mesmo no caso de um polígono auto-interseção, então seria necessária outra abordagem, mas não soa como isso é necessário uma vez que você perguntou sobre a detecção de colisão.

Este pós tem alguns detalhes sobre a parte convexa casco.

Answer 2

Há um monte de fora o material lá. Apenas google para coisas como "malha redução", "malha simplificação", "mesh optimization", etc.