XYZ Geobench

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:

http://wwwjn.inf.ethz.ch/geobench/XYZGeoBench.html