AN ALGORITHM FOR THE COMPUTATION OF SOME DISTANCE FUNCTIONS BETWEEN CONVEX POLYGONS / UM ALGORITMO LINEAR PARA O CÁLCULO DE ALGUMAS FUNÇÕES DISTÂNCIA ENTRE POLÍGONOS CONVEXOS

AUTOR(ES)
DATA DE PUBLICAÇÃO

1990

RESUMO

Apresenta-se nesta dissertação um novo algoritmo para o cálculo de algumas funções distância entre polígonos convexos, no caso geral em que os polígonos podem se interseptar, cuja complexidade linear de pior caso é melhor do que a dos algoritmos até então conhecidos na literatura. O algoritmo é baseado em um algoritmo de complexidade linear originalmente proposto para determinação da distância de Hausdorff entre polígonos convexos disjuntos e utiliza como sua principal componente um algoritmo linear para o cálculo da interseção entre polígonos convexos. A motivação para o estudo de algoritmos eficientes para este problema de cálculo de distâncias decorre de aplicações em reconhecimento de formas e superposição ótima de contornos. Resultados computacionais também são apresentados.

ASSUNTO(S)

linear algorithm poligonos convexos convex polygons algoritmo linear

ACESSO AO ARTIGO

Documentos Relacionados