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 página existe graças aos esforços das seguintes pessoas:
 | Timur
|
Julia Gomes
|
Este conteúdo é licenciado de acordo com a Licença Creative Commons de Atribuição/CompartilhaIgual 3.0 (Unported). Isso significa que você pode redistribuir ou modificar livremente este conteúdo sob as mesmas condições de licença e precisa atribuir ao autor original colocando um hyperlink para este trabalho no seu site. Além disto, favor não modificar qualquer referência ao trabalho original (caso houver) que estiverem contidas neste conteúdo.
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 , 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
e
, 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.
Comentários