Projetos de GeoComp

Resumo

• 5 em Python, usando a interface do Alexis:
  • Par de pontos mais próximos: o algoritmo força-bruta, o de divisão e conquista e um de linha de varredura (ainda por fazer).
  • Interseção de segmentos: o de força-bruta e o de linha de varredura, com EDs diferente para a linha (ABB simples, ABB rubro-negra 2-3, e skip list).
  • Triangulação de Delaunay: o algoritmo que constrói o diagrama de Voronoi, e dele deduz a triangulação, e um incremental probabilístico.
  • Diagrama de Voronoi: o bonito algoritmo de Fortune (temos duas implementações para ele, já que este algoritmo é usado num dos algoritmos acima).
• 3 em Java:
  • Triangulação de polígonos: o algoritmo de triangulação por remoção de orelhas e o algoritmo de linha de varredura.
  • Partição convexa: duas versões do algoritmo de Hertel e Mehlhorn, uma delas probabilística.
  • Plano de locomoção de robôs: um algoritmo que encontra um caminho mínimo para o robô, usando o grafos de visibilidade.
• 2 em C++, usando e gtk ou opengl:
  • Interseção de discos e circunferências: o primeiro apenas detecta interseção enquanto o segundo encontra todas as interseções entre as circunferências dadas.
  • Remoção de superfície escondida: dos vários objetos em uma sala, quais são enxergados a partir de um ponto?
• 2 em Ruby:
  • Localização de ponto: um algoritmo por linha de varredura, que grava a linha antes de processar cada evento, e depois faz uma busca em duas fases, e um algoritmo que usa uma trapezoidalização da região.
  • Plano de locomoção de robôs: um algoritmo que encontra um caminho para o robô, usando o trapezoidalização.

As implementações vêm com uma animação. Alguns dos projetos foram feitos em dupla.

1. Par de pontos mais próximos:
   implementar o algoritmo de divisão e conquista de Shamos e Hoey (visto em aula), e um algoritmo de linha de varredura para esse problema, que por exemplo aparece descrito aqui.
   Autor: Fábio Hirano
   Linguagem: Python.
   EDs: para o segundo algoritmo, está implementando uma árvore 2-4 para guardar os pontos da faixa.
   Comentários: o segundo algoritmo ainda está sendo implementado. Na animação do primeiro algoritmo, falta mostrar a faixa e as comparações feitas entre elementos da faixa. Adaptou a implementação/animação do força bruta do Alexis para o par mais distante, para calcular o par mais próximo.
   Correção: O força-bruta dá resposta errada para os arquivos 7pts e 128pts. Não parece ter consertado os problemas apontados no primeiro algoritmo, e não entregou o segundo algoritmo. Em particular, o primeiro algoritmo parece não implementar a faixa corretamente; parece que são feitos cálculos de distâncias entre pontos que não estariam na faixa do momento. Na verdade, produz a resposta errada para os exemplos colinear_x e colinear_y.

2. Interseção de segmentos:
   fazer duas implementações do algoritmo de linha de varredura de Bentley e Hoey (visto em aula) para detectar interseção de segmentos: uma usando uma ABBB e outra usando uma skip list.
   Autores: Alexandre e Luiz
   Linguagem: Python.
   EDs: usa uma ABB simples (implementação iterativa), uma rubro-negra 2-3 (implementação recursiva), e uma skip-list (implementação iterativa); a fila de eventos é uma lista do python.
   Comentários: as operações de comparação calcularam a interseção com a linha, mas isso não é necessário, e vai ser mudado. O contador que é mostrado é exatamente o número de chamadas às funções primitivas Area2 e Dist (essa última não é usada neste problema). Na animação, deixar os segmentos que já passaram pela linha de uma cor, os da linha de outra, e os que ainda não entraram na linha de outra, para ficar mais fácil de ver.
   Correção: Foi consertada a comparação usada na linha de varredura, as cores foram trocadas. Ficou legal, e agora dá para perceber o quadrático da ABB simples naquele exemplo bem particular. Mas em geral a ABB simples se dá tão bem quanto a balanceada.

3. Diagrama de Voronoi:
   Veremos em aula um bonito algoritmo de linha de varredura para encontrar o diagrama de Voronoi de uma coleção de pontos.
   Autores: Camila e César
   Linguagem: Python.
   EDs: uma ABB para a linha de varredura, o heap do Python para a fila de eventos, e a lista de arestas duplamente ligadas para o diagrama de Voronoi.
   Comentários: no momento, está com problema na remoção da ABB, pois esta tem uma série de ligações e a sua manipulação é bem delicada. Momentaneamente, decidimos não nos preocupar em manter a árvore balanceada, para tentar chegar numa implementação que funcione.
   Correção: A animação ficou legal. A ABB é uma ABB simples, não balanceada.

4. Triangulação de Delaunay:
   Há um algoritmo que usa o diagrama de Voronoi para obter uma triangulação de Delaunay (devemos vê-lo em aula).
   Autor: Luiz Corte Real
   Linguagem: Python.
   EDs: ABBs rubro-negras de uma biblioteca da linguagem para a linha de varredura e para a fila de eventos, e a lista de arestas duplamente ligadas para o diagrama de Voronoi.
   Comentários: Aparentemente há um problema na determinação de um evento-círculo que deve ser inserido na fila de eventos. Isso parece vir do fato de que não é suficiente olhar o y do evento-círculo para decidir se ele deve ser incluído ou não na fila de eventos.
   Correção: O algoritmo para construir o Voronoi está bem legal. Seria legal ter deixado o Voronoi mais claro junto com a triangulação, para se ver a relação entre os dois. Possivelmente limpando isso como um último passo. De qualquer modo, está ótimo.

5. Triangulação de Delaunay:
   Há um algoritmo incremental probabilístico descrito no capítulo 9 de dBvKOS. Toma-se uma permutação aleatória dos pontos dados, e constrói-se o diagrama de Delaunay inserindo um a um cada ponto da coleção no diagrama corrente.
   Autor: Raphael
   Linguagem: Python.
   EDs: usa um DAG que representa a evolução da triangulação. O DAG tem um único nó com grau de entrada zero (a "raiz"), que corresponde a um grande triângulo artificial contendo todos os pontos dados, um nó com grau de saída zero ("folha") para cada triângulo da triangulação corrente e os nós "internos" correspondendo a cada triângulo que um dia fez parte da triangulação. Os "filhos" dos nós internos indicam os triângulos que os substituiram durante a evolução da triangulação. Essa ED serve para encontrarmos o triângulo da triangulação corrente que contém o novo ponto. Este triângulo é então subdividido (há um caso especial quando o novo ponto cai sobre uma aresta da triangulação), e é feito um teste de legalidade em cada uma de suas arestas. Caso alguma delas tenha ficado ilegal, ela é trocada pela outra diagonal, e o teste de legalidade se propaga para as arestas dos novos triângulos. Na animação, o triangulo correspondente ao nó do DAG em que estamos na busca fica vermelho, e o teste de pertinência são três testes de esquerda, marcados em amarelo. As arestas que sofrem o teste de legalidade são marcadas em azul, e quando trocadas, a nova aresta é marcada em verde.
   Comentários: no momento, a implementação corrente não aceita pontos colineares.
   Correção: Está bem legal. As cores estão ajudando bastante a entender a animação do algoritmo, que não é simples. Tudo parece estar funcionando.

6. Interseção de discos e circunferências:
   implementar o algoritmo de linha de varredura para detectar interseção entre dois discos de uma coleção dada de discos, e o algoritmo de linha de varredura para encontrar todas as interseções entre duas circunferências de uma coleção dada de circunferências.
   Autor: Rafael
   Linguagem: C++ e gtk, para a interface.
   EDs: fila de prioridade para a fila de eventos, que é dinâmica, e linha de varredura. Para a fila de prioridade, usou a priority queue da stl, que parece ser uma rubro-negra. Para a linha de varredura, usou um multimap da stl, que também parece ser uma rubro-negra.
   Comentários: A ordem na linha de varredura parece estar com problemas nas duas implementações. A implementação do segundo algoritmo não detecta inteserção em algumas situações por conta disso. O primeiro algoritmo foi implementado para detectar todas as interseções, mas como discos podem se intersectar numa região (numa infinidade de pontos) isso fica mal-definido. Um jeito de contornar esse problema seria imprimir não os pontos de interseção, mas todos os pares de discos que tem interseção. Infelizmente isso parece mais difícil de implementar com esse método. Então resolvemos que o primeiro algoritmo implementará apenas o teste de interseção (vai decidir se há ou não interseção entre os discos dados). Já o segundo deve imprimir todos os pontos de interseção entre as circunferências dadas. Para isso, é preciso consertar a ordem que está sendo usada na ABBB das duas implementações e simplificar o primeiro algoritmo, que poderá interromper a execução uma vez que encontre a primeira interseção.
   Correção: ordem na linha de varredura parece ter sido consertada. Imprime os pares de círculos/discos que se intersectam, então a saída fica consistente nos dois casos. Na animação, destaca os pontos de interseção dos círculos. No caso de interseção de discos, os pontos vermelhos são apenas pontos auxiliares. Poderia, na documentação, ter deixado mais claro qual é a ordem que é mantida na linha de varredura. Isso é uma coisa que ajuda muito alguém a entender o código do seu programa, ou mesmo explicar o funcionamento do algoritmo dada a animação.

7. Remoção de superfície escondida:
   Dado um conjunto de objetos e a posição de um observador, determinar quais partes de cada objeto estão visíveis. O capítulo 12 de dBvKOS descreve uma ED e um algoritmo para este problema, o algoritmo do pintor. Implementação da versão 2D, ou seja, dada uma coleção de segmentos, o algoritmo monta uma ED e depois aceita como queries um ponto, respondendo quais segmentos da coleção estão visíveis a partir daquele ponto.
   Autores: Fábio Colombo e João
   Linguagem: C++ e opengl, para a interface.
   EDs: constrói uma ABB, que representa uma partição (por guilhotina) do plano,
   Comentários: arrumar o misturador de arestas, para que gere uma permutação com probabilidade uniforme. O algoritmo de construção da ABB é recursivo. A primeira aresta da lista corrente determina a reta que divide a coleção corrente de segmentos em duas. Segmentos à esquerda ficam em uma lista, segmentos à direita na outra, e segmentos que cruzam a reta são divididos em dois, ficando uma parte em cada lista. O algoritmo então é aplicado recursivamente a cada uma destas duas listas, até que a lista esteja vazia ou com apenas um segmento. Ao mesmo tempo que esta divisão é feita, a ABB está sendo construída. O segmento escolhido para a divisão é a raiz da árvore da coleção corrente. Construída a ABB, dado um ponto, todos os segmentos/objetos que estão na ABB são desenhados, porém numa ordem em que, caso haja sobreposição, o mais à frente é desenhado sempre por último. A visualização da segunda fase, que mostra o que o observador enxerga, está bem legal. A visualização da construção da ABB está mais difícil de seguir.
   Correção: Está muito legal a animação, embora eu não tenha conseguido ver o passo a passo, como eu acho que tinha visto na apresentação prévia.

8. Triangulação de polígonos:
   implementar o algoritmo de triangulação por remoção de orelhas (visto em aula) e o algoritmo de linha de varredura para esse problema, que veremos nas próximas aulas.
   Autor: Lucas
   Linguagem: Java.
   EDs: para o segundo algoritmo, temos a linha de varredura. No momento, a linha está implementada como um vetor sem ordem nenhuma (busca e remoção consomem tempo linear e inserção, tempo constante). Também é preciso implementar as listas de arestas duplamente ligadas, para guardar a partição em partes monótonas, de modo a, depois, usar isso para gerar a entrada da segunda fase.
   Comentários: o primeiro algoritmo está implementado, animado e funcionando direito. O segundo está bem capenga, pois não tem a implementação da ABBB para a linha, e não está conversando com a sua segunda fase, de triangulação de polígonos monótonos. Esta fase está correta e animada, porém tem que ser executada como um algoritmo a parte. Precisa melhorar um pouco a animação da primeira fase deste algoritmo, por exemplo, destacando as arestas que estão na linha a cada momento. E, evidentemente, precisa implementar a ABBB para a linha, e a ED das listas de arestas duplamente ligadas, para que os dois algoritmos possam ser colocados juntos.
   Correção: O carregar e salvar parecem não funcionar. O make monotone não funciona para

9. Partição convexa:
   implementar o algoritmo de Hertel e Mehlhorn e um dos dois algoritmos de PD para encontrar partição convexa ótima.
   Autores: Atol e Leonardo (entregue)
   Linguagem: Java.
   EDs: vetor com as diagonais de uma triangulação (obtida aqui pelo algoritmo quadrático de remoção de orelhas), matriz indexada pelos vértices nas linhas e colunas com um par de vértices em cada posição. Na entrada (i,j), temos um par (u,v), onde u é o anterior ao j na ordem cíclica (sentido anti-horário) em torno do i, e v é o seguinte ao j na ordem cíclica em torno do i.
   Comentários: O algoritmo de PD não foi implementado. A matriz é preenchida em tempo linear no número de diagonais mais arestas do polígono, ou seja, em tempo linear no tamanho da triangulação. Essa matriz permite que o teste se uma diagonal é ou não essencial seja feito em tempo constante, e permite a remoção de uma diagonal (não-essencial) em tempo constante também. Falta fazer a entrada por arquivo. No momento, a entrada é feita diretamente com o mouse na tela. Há duas versões do algoritmo. Uma delas trata as diagonais numa ordem específica (lexicográfica), e a outra as trata numa ordem aleatória. Dependendo da ordem, a resposta é diferente. A animação está funcionando bem.
   Correção: A entrada por arquivo foi implementada. É possível também desenhar um polígono pelo mouse e salvá-lo para usá-lo mais tarde. Estão disponíveis vários exemplos de polígonos interessantes para testes. Em particular, os exemplo gravata e morcego mostram saídas de tamanho diferentes.
   

10. Grafos de visibilidade:
    O capítulo 15 de dBvKOS discute outros algoritmos para plano de locomoção de robôs, que buscam por rotas mais curtas. Os dados são polígonos (obstáculos) e dois pontos que representam a posição inicial do robô e a posição para onde o robô quer ir. A saída é uma rota mais curta da posição inicial do robô ao seu destino, evitando os obstáculos.
    Autor: Natan
    Linguagem: Java.
    EDs: grafo de visibilidade; usa linha de varredura para determinar as arestas deste grafo da seguinte maneira; a ED da linha de varredura é o treeset do Java; para cada ponto p (de um dos polígonos ou as duas posições especiais), a linha varre os pontos angularmente a partir de p (ou seja, os eventos são os demais pontos, ordenados angularmente em torno do ponto p); guarda-se na linha as arestas que cruzam o eixo corrente a partir do ponto, ordenadas pela distância ao ponto.
    Comentários: a implementação e a animação estão funcionando bem. A complexidade da construção do grafo de visibilidade é O(n² lg n). A entrada permite que os polígonos sejam dados mesmo em sentido horário. Ao decidir se uma aresta deve ser incluída no grafo de visibilidade, é preciso testar se ela não é interna a um dos polígonos. Isso é feito com o ray-shooting. Se a implementação permitisse apenas que os polígonos estivessem em sentido anti-horário, poderia ter usado um teste mais rápido, como o teste de diagonal interna ou externa visto em aula. Mas optamos por manter como está.
    Correção: Não deixou alguns arquivos de entrada prontos. Não explicou o formato dos arquivos de entrada, para que se possa mexer neles. Permite que os pontos sejam colocados dentro dos objetos, e nesse caso o caminho encontrado não faz sentido. Caberia algum teste para evitar esse tipo de entrada. Encontramos duas entradas onde o grafo de visibilidade não fica correto. Uma aresta que não devia ter permanecido na linha fica presente por algum tempo e isso afeta algumas das computações, e são incluídas arestas que não deviam estar presentes no grafo. Podia ter marcado o caminho encontrado em uma cor diferente.

11. Localização de ponto:
    Segue uma descrição informal do problema em questão aqui. Dado um mapa, dividido em regiões (estados, por exemplo), e um ponto qualquer do mapa, determinar em que região do mapa está o ponto. Em linguagem de geometria computacional, o problema poderia ser descrito como: dado um polígono, uma partição deste polígono, e um ponto, determinar em que parte da partição o ponto está. A descrição de dois algoritmos para esse problema aparece no capítulo 6 do livro de de Berg, van Kreveld, Overmans, Schwarzkopf (dBvKOS). Um dos algoritmos é mais simples, mas consome muito espaço. O segundo é o bom.
    Autores: Joel e Murilo
    Linguagem: Ruby.
    EDs: usaram a implementação do Ruby de rubro-negra, para a linha de varredura, e para a busca no primeiro nível. A ordem na linha de varredura é por X-coordenada do vértice mais à direita da aresta. O segundo algoritmo constrói um DAG que representa a trapezoidalização, como numa parte do algoritmo do Schouery.
    Comentários: a implementação e animação do primeiro algoritmo está funcionando bem, porém a escolha e uso das EDs não foram os melhores. A entrada deveria ter sido dada em forma de mapa plano. Ou seja, em forma de lista de adjacências ordenadas ciclicamente (sentido anti-horário) ou algo equivalente. A busca do primeiro nível poderia ter sido feita diretamente no vetor de pontos, que já foi ordenado para a fila de eventos da linha de varredura, por uma busca binária simples. Isso ocuparia menos espaço e resultaria em um algoritmo e armazenamento de dados mais simples. A ordem escolhida para o armazenamento das arestas na linha de varredura não foi a melhor. Como o que se deseja são as arestas ordenadas na faixa de cima para baixo, esta era a ordem correta para se ter na ABBB.
    Correção: No algoritmo de linha de varredura, devia deixar claro qual é a ED usada para armazenar os elementos da linha. Se houver uma ordem envolvida (por exemplo, se for uma ABB), deve deixar claro ainda na documentação do código qual é a ordem usada. A animação dos dois algoritmos ficou muito boa. O segundo é um algoritmo complicado, difícil de animar. Ficou legal.

12. Plano de locomoção de robôs:
    O capítulo 13 de dBvKOS descreve problemas desta classe e alguns algoritmos para resolvê-los. O problema escolhido consiste no seguinte: dada uma coleção de polígonos convexos disjuntos, representando objetos, montar uma ED que responda eficientemente queries de caminho entre dois pontos. Ou seja, dados dois pontos, essa ED permite encontrar rapidamente um caminho entre eles que não esbarre nos objetos.
    Autor: Schouery
    Linguagem: Ruby.
    EDs: um DAG idêntico ao do segundo algoritmo do Joel e Murilo, para representar uma trapezoidalização do conjunto de polígonos, um grafo que tem como vértices um ponto no centro de cada trapézio e um ponto no meio de cada segmento vertical lateral dos trapézios, e tem uma aresta entre o centro de cada trapézio e seus segmentos verticais (se não houver trapézios degenerados, cada centro tem no máximo 4 vizinhos). O comprimento das arestas é a distância entre seus extremos. Uma fila de prioridade para o Dijkstra, que é executado neste grafo.
    Comentários: Podem haver polígonos um dentro do outro, e os pontos dados podem então estar dentro do polígono e deseja-se um caminho que não passe pelas arestas de nenhum polígono. Por enquanto, o algoritmo funciona desde que não haja dois pontos dos polígonos com a mesma X-coordenada. A entrada pode ser feita por um arquivo, onde se lista as arestas de todos os polígonos, e pode ser feita pelo mouse. Clica-se vários pontos, e indica-se o final de um polígono. Neste momento, o algoritmo encontra o fecho convexo (Graham) destes pontos e este é o polígono considerado. Não é verificado se os polígonos dados são disjuntos. Falta fazer o passo a passo.
    Correção: O README tá vazio. O default das cores poderia ser já colorido. (Quando executei, estava tudo preto.) Fora isso, está bem legal e funcionando direitinho do que pude testar.