O sofware de animação de algoritmos XYZ Geobench ( eXperimental geometrY Zurich), criado por volta de 1990 por Peter Shorn, fornece ferramentas para escrever e testar algoritmos geométricos. Ele fornece, ainda, uma biblioteca de tipos de dados abstratos.
O sofware foi desenvolvido em Object Pascal, com a intenção de animar algoritmos geométricos em computadores Macintosh. Ele fornece uma interface com o usuário interativa similar com a de um programa para desenhar, a qual pode ser utilizada para criar e manipular objetos geométricos tais como pontos, segmentos de linhas, polígonos, etc. Além disso, a interface com o usuário fornece um acesso com animação de algoritmos a biblioteca de programas XYZ, a qual contém muitos aprogramas tradicionais para problemas em duas dimensões, alguns problemas restritos em três dimensões e um problema d-dimensional em geometria computacional.
A figura abaixo mostra a tela da animação da computação de um diagrama de Voronoi, utilizando o algoritmo de varredura de Fortune, no sistema XYZ Geobench:
O sistema é limitado a problemas bidimensionais e possui algumas limitações, como, por exemplo, a necessidade de codificação para cada um dos eventos a serem tratados, descrevendo as modificações geométricas envolvidas.
Um exemplo de animação utilizando o software XYZ Geobench é mostrado abaixo. O algoritmo tentará achar o par mais próximo de pontos dispostos sobre o plano.
A idéia do algortmo é fazer uma varredura no plano com uma linha vertical da esquerda para a direita e se "lembrar" dos par mais próximo de pontos da esquerda dessa linha. Na tela abaixo vemos uma linha grossa representando a linha de varredura e um segmento de linha conectando os dois pontos encontrados no lado esquerdo da linha, que representam o par mais próximo até então encontrado.
Continuamos a execução do algoritmo para o próximo passo clicando duas vezes no botão "Continue" na caixa de diálogo "Animation"
Quando alinha de varredura encontra um
ponto p ( por exemplo, o quarto ponto da figura acima ) temos que determinar
se p forma um novo par mais próximo com algum outro ponto já
encontrado ( ponto a esquerda da linha de varredura ). Nào precisamos
testar todos os pontos a esquerda da linha de varredura, mas somente os
pontos mais próximos do último ponto encontrado ( só
testamos os pontos que estào no semicírculo desenhado em
torno do ponto p. O raio de semicírculo corresponde a distância
do ponto mais próximo até então encontrado. Se o semicírculo
estiver vazio, como na figura acima, continuamos sem atualizar o par mais
próximo. Clicamos novamente no botào "Continue" da caixa
de diálogo "Animation"
Agora o semicírculo nào está vazio, o que significa que um novo par mais próximo foi encontrado. Clicamos novamente no botào "Continue".
As linhas a volta do semicírculo denotam que o algoritmo nào examina os pontos no semicírculo, mas os pontos dentro do retângulo envolvente do semicírculo. Prosseguimos na animaçào pressionando o botào "Movie" que inicia o modo automático de animaçào. Ajustamos a velocidade da animação utilizando os botòes "Slower"e "Faster".
Finalmente, o par mais próximo de pontos é encontrado.
O download do sistema pode ser obtido no
endereço : neptune.inf.ethz.ch ( 129.132.100.33 ) no diretório
XYZ.
Maiores informações sobre o software
XYZGeobench podem ser obtidas, por exemplo, através do endereço
abaixo: