http://www.ime.usp.br/~cris/geocomp/listas/
Não precisa entregar nada... mas, claro, usem-na para estudar para a prova da semana que vem...
Até,
Cris
Profa, o exercício 3 é pra mostrar um algoritmo que detecta se um polígono é simples. Comecei usando o algoritmo do CLRS. O algoritmo de lá é bem parecido com o que a gente viu até agora, mas ele permite pontos eventos com mesma X-coordenada. As restrições dele são: 1) não permite-se segmentos verticais e 2) não permite-se interseções triplas
Eu quero saber (por favor) se existe um jeito mais fácil, e se o que eu pensei até agora está certo:
a idéia é basicamente usar o mesmo algoritmo para detectar interseções, mas trocando-se o Inter(a,b,c,d) por um certo Inter2(a,b,c,d). (aqui (a,b) e (c,d) são segmentos do polígono dado)
O Inter2(a,b,c,d) devolve verdadeiro se e somente se Inter(a,b,c,d) é verdadeiro e a != c , a != d , b != c , b != d (aqui esta implicito a != b e c != d)
(Ou seja, o Inter2(a,b,c,d) serve para detectar todas as interseções que o Inter(a,b,c,d) detectava com exceção das interseções que ocorrem em arestas consecutivas de um polígono (isto é, não quero detectar interseção (por exemplo) na curva poligonal <a,e1,b,e2,c> )
O que resta (eu acho) é provar que o algoritmo continua correto, para isso acho que dá pra copiar a argumentação do CLRS: consideramos a interseção (no sentido Inter2) mais à esquerda e, em caso de empate, a com menor Y-coordenada dentre as mais à esquerda. Chame os segmentos envolvidos na interseção de (a,b) e (c,d).
Agora, como não há interseção tripla (*) observamos que existe um ponto evento q à esquerda ou sobre a interseção e, após processar q, os segmentos (a,b) e (c,d) passam a ser vizinhos (aqui precisa dividir em casos, vou omitir aqui)
Isso daria quase um algoritmo que o ex. 3 pede. O que resta é se livrar das 2 restrições do algoritmo CLRS (está como exercício no capítulo dele)..
Eu quero saber (por favor) se existe um jeito mais fácil, e se o que eu pensei até agora está certo:
a idéia é basicamente usar o mesmo algoritmo para detectar interseções, mas trocando-se o Inter(a,b,c,d) por um certo Inter2(a,b,c,d). (aqui (a,b) e (c,d) são segmentos do polígono dado)
O Inter2(a,b,c,d) devolve verdadeiro se e somente se Inter(a,b,c,d) é verdadeiro e a != c , a != d , b != c , b != d (aqui esta implicito a != b e c != d)
(Ou seja, o Inter2(a,b,c,d) serve para detectar todas as interseções que o Inter(a,b,c,d) detectava com exceção das interseções que ocorrem em arestas consecutivas de um polígono (isto é, não quero detectar interseção (por exemplo) na curva poligonal <a,e1,b,e2,c> )
O que resta (eu acho) é provar que o algoritmo continua correto, para isso acho que dá pra copiar a argumentação do CLRS: consideramos a interseção (no sentido Inter2) mais à esquerda e, em caso de empate, a com menor Y-coordenada dentre as mais à esquerda. Chame os segmentos envolvidos na interseção de (a,b) e (c,d).
Agora, como não há interseção tripla (*) observamos que existe um ponto evento q à esquerda ou sobre a interseção e, após processar q, os segmentos (a,b) e (c,d) passam a ser vizinhos (aqui precisa dividir em casos, vou omitir aqui)
Isso daria quase um algoritmo que o ex. 3 pede. O que resta é se livrar das 2 restrições do algoritmo CLRS (está como exercício no capítulo dele)..
Oi Alexandre,
Hoje na aula vou falar sobre como lidar com os casos particulares no algoritmo de Shamos e Hoey, e depois vou falar da generalização deste algoritmo que detecta todas as interseções. Esta generalização deve-se a Bentley e Ottmann.
O mais fácil para resolver esse problema é usar essa generalização diretamente. Para que você possa usá-la, deixe-me tornar a descrição do algoritmo mais precisa. Essa generalização (que vou chamar de algoritmo de Bentley e Ottmann) recebe uma coleção de segmentos, no mesmo formato que o algoritmo de Shamos e Hoey, e devolve uma lista dos pares de índices de segmentos da coleção que se intersectam.
Veremos detalhes deste algoritmo hoje, mas para resolver esse exercício da lista, isso deve ser o suficiente.
A sua idéia de usar uma variante do inter, o tal inter2 que você descreveu, parece quase ok... O que acontece se o polígono for como uma gravata borboleta: dois triangulos com um vértice em comum? Isso pode dar problema, não?
Cris
Hoje na aula vou falar sobre como lidar com os casos particulares no algoritmo de Shamos e Hoey, e depois vou falar da generalização deste algoritmo que detecta todas as interseções. Esta generalização deve-se a Bentley e Ottmann.
O mais fácil para resolver esse problema é usar essa generalização diretamente. Para que você possa usá-la, deixe-me tornar a descrição do algoritmo mais precisa. Essa generalização (que vou chamar de algoritmo de Bentley e Ottmann) recebe uma coleção de segmentos, no mesmo formato que o algoritmo de Shamos e Hoey, e devolve uma lista dos pares de índices de segmentos da coleção que se intersectam.
Veremos detalhes deste algoritmo hoje, mas para resolver esse exercício da lista, isso deve ser o suficiente.
A sua idéia de usar uma variante do inter, o tal inter2 que você descreveu, parece quase ok... O que acontece se o polígono for como uma gravata borboleta: dois triangulos com um vértice em comum? Isso pode dar problema, não?
Cris
é verdade, a "gravata borboleta" dá problema..
Acho que aconteceu de ela ter uma caracteristica que eu não esperava,na curva poligonal da gravata borboleta, existe uma subsequência (própria) de vértices e arestas que formam em si uma curva poligonal fechada (certo?).
E se agora eu for mais cuidadoso e verificar se a curva poligonal dada na entrada não possui essa característica? (tipo um pré-processamento). Se ela possuir a característica, eu respondo "a curva não é simples".
Pra detectar a característica eu poderia usar o que foi pedido em um exercício do par de pontos mais próximo: em tempo O(nlogn), remover pontos repetidos da coleção. Usariamos esse algoritmo (dois sorts, sendo um estável) para acusar pontos repetidos na curva poligonal dada (a menos do v_0 e v_n-1, que são os únicos que podem (e até devem) ser repetidos)
Acho que aconteceu de ela ter uma caracteristica que eu não esperava,na curva poligonal da gravata borboleta, existe uma subsequência (própria) de vértices e arestas que formam em si uma curva poligonal fechada (certo?).
E se agora eu for mais cuidadoso e verificar se a curva poligonal dada na entrada não possui essa característica? (tipo um pré-processamento). Se ela possuir a característica, eu respondo "a curva não é simples".
Pra detectar a característica eu poderia usar o que foi pedido em um exercício do par de pontos mais próximo: em tempo O(nlogn), remover pontos repetidos da coleção. Usariamos esse algoritmo (dois sorts, sendo um estável) para acusar pontos repetidos na curva poligonal dada (a menos do v_0 e v_n-1, que são os únicos que podem (e até devem) ser repetidos)