Apresentação geometria computacional

Análise de Algoritmo - Geometria Computacional

Aldisio Medeiros | Jovane Pires Dezembro, 06 de 2013

Instituto Federal do Ceará - IFCE | Ciência da Computação

Aldisio Medeiros [email protected]

Jovane Pires [email protected]

Projeto Final da Disciplina Análise de Algoritmo: Geometria Computacional

mailto:[email protected]






1. Origem e Definição da Geometria Computacional

2. Operações Primitivas

a. Estruturas Básicas

b. Operações

i. Esquerda-Direita

ii. EmCírculo

3. Fecho Convexo 2D

a. Algoritmo Incremental

b. Algoritmo de Graham

4. Fecho Convexo 3D

5. Implementações e Aplicações

6. Conclusão

7. Referências

Sumário





➯ A Geometria Computacional emergiu da área de desenvolvimento e análise de algoritmos

em meados dos anos 70

➯ Todavia sua origem permeiam os fundamentos da geometria euclidiana

o O caráter algorítmo já era observado

o Existia um certo número de operações elementares com régua e compasso.

o Ex:

c1. Dados a e b, obter um segmento de reta;

c2. Traçar um círculo de centro o e raio igual ao segmento ab;

c3. Obter a interseção de entre retas e ente círculos

o Ex: Obter um circulo que contenha 3 pontos não colineares, a, b e c.

➯ “Geometria Computacional é o estudo sistemático de algoritmos eficientes para

problemas geométricos”




➯ A Geometria Computacional preocupa-se em resolver problema geométricos também levando

em consideração a complexidade computacional;

➯ O que é um problema geométrico?

o A entrada é um conjunto de objetos geométricos

o A solução de um problema geométrico envolve aspectos geométricos (localização e

forma dos objetos) e aspectos topológicos (relações de adjacência e incidência entre os

objetos).

➯ Como identificar qual o melhor algoritmo?

➯ Alguns problemas:

1.1. Recontrução de Curvas:





1.2. Triangulação

1.3. Diagrama de Voronoi






1.4. Fecho Convexo 2D

1.5. Fecho Convexo 3D





1. Tipos de problemas em Geometria Computacional:

a. Seletivos: Descobrir relações topológicas. Exemplos: fecho convexo, triangulação,

árvore geradora mínima, simplicação de curvas e superfícies.

a. Construtivos: Nesses problemas temos que construir um ou mais

objetos geométricos novos a partir da entrada. Exemplos: interseção de polígonos,

círculo mínimo, diagrama de Voronoi.

a. Decisão: Nesses problemas temos somente que responder “sim”

ou “não” a uma pergunta. Ex: Dado um polígono e um ponto, o ponto está fora do

polígono?

a. Consultas: Dado um conjunto X de objetos geométricos, queremos

processá-lo previamente de modo a poder responder eficientemente

a consultas repetidas sobre ele. Ex: Conjunto de retângulos e a lista dos incidentes em

um certo retângulo




2. Operações Primitivas

As primitivas são as operações básicas de um algoritmo. Por exemplo, nos algoritmos de

ordenação a função para comparar dois elementos é uma primitiva, assim como a operação de

troca de elementos. Como contamos a eficiência de um algoritmo? Contando a quantidade de

operações primitivas executadas.

2. Exemplo de Primitivas:

a. Operações com vetores

b. Distância e angulos

c. Ângulos orientados no plano

d. Ponto é interno ao poligono

e. Produto Vetorial

f. Esquerda-Direita

g. In-circle




2.1. Produto Vetorial

O produto vetorial pode ser calculado a partir do seguinte determinante:




2.1. Esquerda-Direita

Esta primitiva consiste em sabermos a posição de um ponto em relação a um vetor

(segmento orientado). Então dados três pontos A, B e C tal que AB é um segmento orientado,

temos que a primitiva Esquerda(A,B,C) é verdadeira se o ponto C está a esquerda da reta

formada ao estendermos o segmento AB nos dois sentidos. A primitiva é falsa caso contrário.

Analogamente temos a primitiva Direita.

Se esta for positiva, o ponto C está à esquerda ( a ); se for negativa, C está à direita ( b ). Se a área

calculada for nula, então A, B e C estão alinhados ( c ).




2.2. In-Circle

Esta primitiva consiste em sabermos a posição de um ponto em relação a uma

circunferência no plano. Sabemos que se tivermos três pontos de uma circunferência no plano

então conseguimos representá-la pois apenas uma circunferência pode passar por 3 pontos fixos.

Então dados quatro pontos A, B, C e D onde A, B e C representam uma única circunferência.

Digamos que seu centro seja M e seu raio R. Como observação,

distância(A,M) = distância(B,M) = distância(C,M) = R

A primitiva In-Circle(A,B,C,D) é verdadeira se o ponto D é interno à circunferência dada, isto é, a

distância(D,M) < R. Esta primitiva é falsa caso contrário.a




3. Fecho Convexo 2D

3.1. Definição

3.2. Algoritmo Incremental

3.3. Algoritmo QuickHull

3.4. Algoritmo Graham




3. Fecho Convexo 2D

3.1. Definição

3.1.1 Histórico

➯ Chand-Kappur desenvolvem o algoritmo do Embrulho que é eficiente para n pontos em

uma dimensão arbitrária 1970

➯ Graham desenvolve o primeiro algoritmo com Ordem de complexidade inferior a O(n²)

➯ Jarvis desenvolve uma especialização do método de Chand-Kappur

➯ Preparata e Hong desenvolvem o primeiro algoritmo para fechos Convexos 3D em

O(nlogn)

3.1.1 Definição

Exemplos: Pontos, segmentos de retas, discos, semiplanos, triângulos, etc




3. Fecho Convexo 2D

O’Rourke [ORou94] lista uma série de definições alternativas e equivalentes do fecho

convexo, as mais interessantes das quais estão relacionadas a seguir:

➯ O fecho convexo de um conjunto S de pontos do plano é o menor polígono convexo

P que contém S, sendo “menor” entendido no sentido de que não existe outro

polígono P’ tal que P ⊃ P' ⊃ S .

➯ O fecho convexo de um conjunto S de pontos é a interseção de todos os conjuntos

convexos que contêm S.

➯ O fecho convexo de um conjunto S de pontos do plano é a união de todos os

triângulos determinados por pontos pertencentes a S.




3. Fecho Convexo 2D

Definição:

Seja FC(s) o fecho convexo do conjunto s, temos o problema:

Problema: Como encontrar o polígono que define o fecho S ?

1. Encontrar as fronteiras do polígono FC(S)

2. Encontrar os vértices do polígono FC(S)




3. Fecho Convexo 2D

3.1. Algoritmo Incremental

➯ Um primeiro algoritmo para o cálculo do fecho convexo de um conjunto de pontos é o algoritmo

incremental. Algoritmos incrementais resolvem um dado problema para um subconjunto e,

passo a passo, calculam a solução inserindo novos elementos do conjunto inicial.

➯ No caso do fecho convexo de um conjunto de n pontos, o algoritmo calcula o fecho convexo

para n-1 pontos e compõe esse resultado com o novo ponto. Basta decidir se o novo ponto está

dentro ou fora do fecho convexo atual. Se estiver dentro, é um ponto interno ao fecho e não é

preciso atualizar nada. Se estiver fora, então é necessário "consertar" o fecho atual de forma a

incluí-lo entre os vértices. Nesse processo, pode acontecer de algum(s) dos antigos vértices

deixar de ser um vértice passando a ser mais um ponto interior.




3. Fecho Convexo 2D

➯ Utilizamos as primitivas Esquerda-Direita para saber a posição de um dado ponto em relação a

um lado do fecho convexo atual. A idéia é simplificada se assumirmos que o polígono tem a

seqüência de seus vértices orientada em um sentido (anti-horário, por exemplo). Assim, basta

verificar se um novo ponto está a esquerda (se o sentido adotado for anti-horário) de todos os

lados do fecho. Se isso for verdade, então trata-se de um ponto interno ao fecho, senão é um

ponto externo que será colocado como um vértice.

➯ Analisando a sua complexidade, podemos gastar tempo O(logn) para decidir se o novo ponto

está dentro ou fora do fecho convexo dos n-1 pontos anteriores. Em seguida temos que

"consertar" o fecho anterior com o novo ponto, o que pode levar-nos a mexer em (n-1)-1arestas

do fecho anterior (as arestas que "enxergam" o novo ponto). Portanto, esse passo gasta tempo

O(n). Assim, a complexidade da inserção de um ponto é dominada pelo segundo passo,

levando tempo O(n) para ser executado. Como vamos executar esse passo n vezes, então a

complexidade total do algoritmo é O(n2).




3. Fecho Convexo 2D


● O QuickHull é um algoritmo que calcula o fecho convexo de pontos num plano, com

complexidade média O(n*logn), tornando-se um equivalente geométrico do algoritmo de

ordenação QuickSort. Ele divide o plano em 2 regiões, utilizando-se dos pontos mais extremos

(isto é, pontos com menor e maior coordenada x e maior e menor coordenada y) do conjunto. A

região interna a este quadrilátero é desprezada, pois obviamente não fará parte do fecho

convexo dos pontos (são todos pontos interiores).

● A seguir aplica-se a cada uma das regiões restantes um algoritmo recursivo, que calcula o

ponto P mais distante do segmento correspondente (na primeira vez é um segmento do

quadrilátero) e divide o problema local em duas partes, como se o segmento da iteracao atual

fosse dividido em outros dois, tendo o ponto P em comum. A recursão é aplicada até uma parte

possuir somente dois pontos, que são então conectados.




Fecho Convexo 2D


● Analisando a sua complexidade, esse algoritmo é quadrático no pior caso, mas

equivalentemente ao quicksort, podemos perceber sua eficiência: em exemplos com pontos

aleatoriamente distribuídos, muitos pontos estarão dentro do quadrilátero inicial e serão

descartados logo na primeira fase do algoritmo. Após diversos testes percebe-se que o

QuickHull se iguala ao algoritmo de Graham em relacão a tempo, quando nao possui

desempenho melhor. Como no Quicksort, o QuickHull possui no "caso médio" tempo O(n*logn).

Aqui a primitiva utiizada continua sendo a primitiva Esquerda-Direita.




3. Fecho Convexo 2D

3.3. Algoritmo Graham

O algoritmo de Graham calcula o fecho convexo de pontos num plano, com complexidade de

tempo O(n*logn). Ele encontra o ponto P com menor coordenada y e então ordena os pontos

restantes pelo ângulo em relação à linha horizontal que passa pelo ponto P. Agora, com ajuda

de uma pilha, o algoritmo trabalha em tempo linear. Empilhamos os dois primeiros pontos e

então basta percorrermos os pontos ordenados fazendo o seguinte:

• se o ponto X em questão está a esquerda do vetor penúltimo-último elemento da pilha (último

elemento da pilha é o topo) então empilhamos e olhamos o próximo;

• se o ponto X em questão está a direita deste mesmo vetor, então desempilhamos e voltamos a

analisar X.




3. Fecho Convexo 2D

➯ Ao final temos na pilha uma lista de pontos que forma o fecho convexo dos pontos. A

complexidade do algoritmo é O(n*logn) porque precisamos gastar esse tempo para ordená-los.

Já o processamento após os pontos estarem ordenados é linear, nao alterando a complexidade

final. O algoritmo de Graham é um algoritmo ótimo para o cálculo do fecho convexo. Aqui a

primitiva pode ser considerada a operação Esquerda que verifica se um ponto está a esquerda

de um vetor.

➯ Convém ressaltar que tudo funciona desse modo obedecendo a definição de que um polígono

seja definido como uma lista de vértices ordenados em um sentido. Assim, um ponto fora do

polígono estará a esquerda de todas as arestas orientadas do polígono se o sentido escolhido

for o sentido anti-horário. Se definirmos o polígono ordenado no sentido horário, um ponto

estará fora do polígono se estiver a direita das arestas orientadas.

http://www.ime.usp.br/~freitas/gc/primitivas.html




3. Fecho Convexo 2D




3. Fecho Convexo 2D

Problema 1 .

Se origem em P0 , este não pertence ao fecho, o que no final precisaria de

um método para remover da pontos internos da pilha

Problema 2.

Se origem em P1 e P2 não fisse parte do fecho




3. Fecho Convexo 2D

Solução .

Se ordenamos os pontos a partir da coordenada y ou pelo ângulo formado

a partir de um ponto P0, e tomamos o ponto inicial o menor ponto desse

conjunto garantimos:

1. O ponto inicial fará parte do fecho (Problema 1 resolvido)

2. O ponto seguinte também fará parte do fecho (Problema 2 resolvido)




3. Fecho Convexo 2D




3. Fecho Convexo 2D

Problema 3 .

Casos onde existe colinearidade,Se origem em P0 , porém P1 é colinear de P2 ?

Solução.

Ordena-se a partir do ponto onde a expressão é verdadeira:




3. Fecho Convexo 2D




3. Fecho Convexo 2D




3. Fecho Convexo 2D

Qual a equação de recorrência do Algoritmo de Graham?




4. Fecho Convexo 3D

4.1. Definição

4.2. Dificuldade

4.3. Algumas implementações




4. Fecho Convexo 3D

3.1. Definição

O fecho convexo 3D é um Poliedro Convexo. Os poliedros são convexos quando se encontram todos

para o mesmo lado em relação ao plano de qualquer uma das suas faces, ou seja, quando as suas

faces deixam sempre as demais no mesmo semiespaço. Complicado? Vamos entender melhor isso!

Considere um poliedro e uma de suas faces: um octaedro, por exemplo. Imagine um plano apoiado

nessa face. O poliedro ficou todo de um lado só desse plano? Então ele é convexo! Veja:




4.2. Dificuldade

For a finite set of points, the convex hull is a convex polyhedron in three dimensions, or in general a

convex polytope for any number of dimensions, whose vertices are some of the points in the input

set. Its representation is not so simple as in the planar case, however. In higher dimensions, even

if the vertices of a convex polytope are known, construction of its faces is a non-trivial task, as is

the dual problem of constructing the vertices given the faces. The size of the output may be

exponentially larger than the size of the input, and even in cases where the input and output are

both of comparable size the known algorithms for high-dimensional convex hulls are not output-

sensitive due both to issues with degenerate inputs and with intermediate results of high

complexity.

4. Fecho Convexo 3D




http://computacion.cs.cinvestav.mx/~anzures/geom/hull.php

Comparativo

Algorithm Speed

Brute Force

Graham Scan

QuickHull

Incremental








http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html


Implementações















Novembro, 08 de 2012

Onde Aplicamos Fecho Convexo?





Conclusão...








Obrigado.




http://www.ime.usp.br/~freitas/gc/fecho.html

http://www.ime.usp.br/~freitas/gc/java/FechoApp.html

http://lhf.impa.br/cursos/gc/notas.pdf

http://www.dpi.inpe.br/gilberto/livro/geocomp/geometria.pdf

Referências












Documents

Apresentação geometria computacional