Marcha de Jarvis

Esta calculadora online calcula a envoltória convexa de um determinado conjunto de pontos utilizando o algoritmo de marcha de Jarvis, também conhecido como Algoritmo de embrulho para presente

Esta calculadora online implementa o algoritmo Marcha de Jarvis, introduzido por R. A. Jarvis em 1973 (também conhecido como algoritmo de embrulho para presente) para calcular a envoltória convexa de um determinado conjunto de 2d pontos. Ele possui a complexidade de O ( n h ), onde n é o número de pontos e h é o número de vértices da envoltória, portanto, é um algoritmo sensível à saída. Existem outros algoritmos com complexidade de O ( n \log n ) e O ( n \log h ), mas a Marcha de Jarvis é muito simples de implementar.

O algoritmo começa com um ponto conhecido por estar na envoltória convexa, por exemplo, o ponto mais à esquerda, e, em seguida seleciona o próximo ponto comparando os ângulos polares de todos os pontos em relação ao ponto anterior tomado para o centro das coordenadas polares. O ponto com ângulo mínimo vence. O processo continua até retornar ao ponto inicial em h etapas. O processo é semelhante a enrolar uma string (ou embrulhar um papel) em torno do conjunto de pontos, daí vem o nome algoritmo de embrulho para presente.

Insira o conjunto de pontos na calculadora abaixo - um ponto por linha, com as coordenadas x e y separadas por um ponto e vírgula. A calculadora constrói uma envoltória convexa, exibe-a como um conjunto de pontos e a plota.

PLANETCALC, Marcha de Jarvis

Marcha de Jarvis

Envoltória convexa
 

URL copiado para a área de transferência
PLANETCALC, Marcha de Jarvis

Comentários