rotating_calipers
Rotating calipers 1.0
Os pinças rotativas são o módulo Python implementando um algoritmo com o mesmo nome.
O algoritmo foi inventado pela primeira vez por Michalel Shamos em 1978 e ganhou seu nome "pinças rotativas", graças a Godfried Toussant, que o apresentou em seu artigo em 1983.
O método é assim chamado porque a idéia é análoga a girar uma pinça vernier com mola ao redor de um polígono convexo. Toda vez que uma lâmina da pinça fica plana contra uma borda do polígono, forma um par antipodal com o ponto ou a borda tocando a lâmina oposta. A "rotação" completa da pinça ao redor do polígono detecta todos os pares antipodais; O conjunto de todos os pares, visto como um gráfico, forma um lançamento. O método de pinças rotativas pode ser interpretado como o duplo projetivo de um algoritmo de linha de varredura, no qual a varredura é entre as encostas das linhas, em vez de entre as coordenadas X ou Y de pontos.
A descrição acima foi adaptada da Página da Wikipedia: https://en.wikipedia.org/wiki/rotating_calipers
O algoritmo "pinça rotativo" foi implementado por mim para um projeto universitário. Surpreendentemente, tive muitos problemas para encontrar uma solução eficiente no Python. É por isso que eu queria compartilhá -lo com todos que precisam de uma implementação rápida de "pinças rotativas" no Python.
À medida que as pinças rotativas são executadas no tempo linear, ele precisa de um casco convexo na entrada, é calculado aqui usando o algoritmo de Graham, que é executado em O (nLogn). Em todos os algorihm (a complexidade do tempo do algoritmo de Graham + pinças rotativas) é O (nLogn) + O (n) = O (nLogn)
Linux:
Exemplo de uso pode ser encontrado aqui
