[pt] 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. / [en] We present in this dissertation a new algorithm for the
computation of some distance functions between convex
polygons, in the general case where they can intersect,
whose worst case time complexity is better than of the
previously known algorithms. The algorthm is based on an
algorithm originally proposed for the computation of the
Hausdorff distance between disjoint polygons and uses as
its main component a linear time algorithm for finding the
intersection of convex polygons. The motivation for the
study of efficient algorithms for this distance computation
problem comes from applications in pattern recognition and
contour fitting. Computatioal results are also presented.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:9412 |
| Date | 28 December 2006 |
| Creators | SERGIO LIFSCHITZ |
| Contributors | CELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | English |
| Type | TEXTO |
Page generated in 0.0024 seconds