Departamento de Matemática da Universidade de Aveiro
GERAÇÃO ALEATÓRIA
DE POLÍGONOS
GERAÇÃO E PARTIÇÃO DE
POLÍGONOS
Ana Gonçalves
Inês Matos
DEFINIÇÕES
2
Definições
Polígono Monótono: um polígono simples diz-se monótono
em relação a alguma direcção se todas as linhas
perpendiculares a essa direcção intersectam o polígono, no
máximo, em dois pontos ou num intervalo fechado quando
coincide com uma aresta.
Exemplos:
y
x
3
Definições
Grafo de Visibilidade: grafo cujos vértices são os mesmos
do polígono simples e onde dois vertices são adjacentes se
são mutuamente visíveis. As arestas deste grafo são
chamadas de arestas de visibilidade e o número de arestas
deste grafo será denotado por K.
Exemplo:
v
4
Definições
Posição Geral: um conjunto de pontos está em posição
geral se não existirem três pontos colineares ou quatro
pontos cocirculares.
Heurística: também algoritmo heurístico, utiliza-se
quando existe um procedimento que encontra uma boa
solução para resolver um certo problema. No entanto,
essa solução pode não ser óptima e pode mesmo dar-se o
caso do procedimento não encontrar qualquer solução
(apesar dela existir).
5
GERAÇÃO DE
POLÍGONOS
6
Geração de Polígonos
Por geração uniforme de polígonos aleatórios entende-se
que cada polígono gerado tem probabilidade 1/k de ocorrer,
se existirem k polígonos possíveis.
A geração uniforme de polígonos aleatórios é um problema
para o qual não se conhece solução polinomial.
Sendo assim, temos que recorrer a heurísticas para gerar
polígonos. No entanto, a heurística que escolhemos deve ser
condicionada pela solução que queremos obter.
7
Geração de Polígonos
Que tipo de polígono queremos gerar?
 Simples
 Monótono
 Estrelado
 Ortogonal
 Convexo
...
Qual a característica que queremos impôr ao polígono final?
 Polígono
 Polígono
 Polígono
 Polígono
...
com n vértices
com n vértices reflexos
a partir de um dado conjunto de pontos
com uma dada área
8
Geração de Polígonos Simples
Sobre este problema existem dois trabalhos que se
evidenciam dos restantes. Ambos partem de um conjunto S
de pontos no plano (em posição geral) que são os vértices do
polígono simples final.
O trabalho mais conhecido é o RPG – Heuristics for the
Generation of Random Polygons de Thomas Auer e Martin
Held. Nele podemos encontrar diversas heurísticas para gerar
polígonos simples.
http://www.cosy.sbg.ac.at/~held/projects/rpg/rpg.html
9
Geração de Polígonos Estrelados
 Star Universe
(gera todos os polígonos estrelados possíveis)
 Quick Star – O(nlogn)
(gera uniformemente todos os polígonos estrelados
possíveis)
Star Universe
Um polígono estrelado é determinado pelo seu núcleo. O conjunto de
todos os núcleos forma uma partição do invólucro convexo. Para
gerar todos os polígonos estrelados, trabalha-se sobre esta partição.
A complexidade deste algoritmo é elevada.
10
Geração de Polígonos Estrelados
Quick Star
11
Geração de Polígonos Estrelados
Quick Star
Determina o invólucro convexo
12
Geração de Polígonos Estrelados
Quick Star
Escolhe um ponto interior
p0
13
Geração de Polígonos Estrelados
Quick Star
Ordena os restantes pontos em torno desse
ponto interior
p0
p1
14
Geração de Polígonos Estrelados
Quick Star
Ordena os restantes pontos em torno desse
ponto interior
p2
p0
p1
15
Geração de Polígonos Estrelados
Quick Star
Ordena os restantes pontos em torno desse
ponto interior
p3
p2
p0
p1
16
Geração de Polígonos Estrelados
Ordena os restantes pontos em torno desse
ponto interior
Quick Star
p3
p4
p2
p0
p1
17
Geração de Polígonos Estrelados
Ordena os restantes pontos em torno desse
ponto interior
Quick Star
p5
p3
p4
p2
p0
p1
18
Geração de Polígonos Estrelados
Ordena os restantes pontos em torno desse
ponto interior
Quick Star
p5
p3
p4
p2
p6
p0
p1
19
Geração de Polígonos Estrelados
Ordena os restantes pontos em torno desse
ponto interior
Quick Star
p5
p3
p4
p2
p6
p0
p1
p7
20
Geração de Polígonos Estrelados
Ordena os restantes pontos em torno desse
ponto interior
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
21
Geração de Polígonos Estrelados
Ordena os restantes pontos em torno desse
ponto interior
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
22
Geração de Polígonos Estrelados
Ordena os restantes pontos em torno desse
ponto interior
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
23
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
24
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
25
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
26
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
27
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
28
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
29
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
30
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
31
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
32
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
33
Geração de Polígonos Estrelados
Ligar os pontos por ordem
Quick Star
p5
p3
p4
p2
p6
p0
p1
p8
p7
p9
p10
34
Geração de Polígonos Estrelados
Quick Star
Polígono Estrelado Final
O(nlogn)
35
Geração de Polígonos Simples
 Steady Growth – O(n2)
(não gera todos os polígonos simples possíveis)
 Space Partitioning – O(nlogn)
(não gera todos os polígonos possíveis)
 Permute & Reject - O(nlogn)
(gera todos os polígonos possíveis uniformemente)
 2-Opt Moves - O(n3)
(gera todos os polígonos possíveis embora não seja
uniforme)
 Incremental Construction & Backtracking
36
Geração de Polígonos Simples
Steady Growth
37
Geração de Polígonos Simples
Encontrar três pontos que formem
um triângulo vazio
Steady Growth
s2
s1
s3
38
Geração de Polígonos Simples
Escolher um ponto si tal que não exista nenhum
ponto de S\{s1,s2,s3} interior a CH(s1,s2,s3,s4)
Steady Growth
s4
s2
s1
s3
39
Geração de Polígonos Simples
Encontrar uma aresta do polígono já formado
que seja completamente visível para si
Steady Growth
s4
s2
s1
s3
40
Geração de Polígonos Simples
Criar duas novas arestas e ir acrescentando os
vários pontos, um a um, ao polígono já formado
Steady Growth
s4
s2
s1
s3
41
Geração de Polígonos Simples
Continuar com este procedimento para todos os
diferentes pontos
Steady Growth
s5
s4
s2
s1
s3
42
Geração de Polígonos Simples
Continuar com este procedimento para todos os
diferentes pontos
Steady Growth
s5
s4
s6
s2
s1
s3
43
Geração de Polígonos Simples
Continuar com este procedimento para todos os
diferentes pontos
Steady Growth
s5
s4
s6
s2
s1
s3
s7
44
Geração de Polígonos Simples
Continuar com este procedimento para todos os
diferentes pontos
Steady Growth
s8
s5
s4
s6
s2
s1
s3
s7
45
Geração de Polígonos Simples
Continuar com este procedimento para todos os
diferentes pontos
Steady Growth
s8
s5
s9
s4
s6
s2
s1
s3
s7
46
Geração de Polígonos Simples
Continuar com este procedimento para todos os
diferentes pontos
Steady Growth
s8
s10
s5
s9
s4
s6
s2
s1
s3
s7
47
Geração de Polígonos Simples
Continuar com este procedimento para todos os
diferentes pontos
Steady Growth
s11
s8
s10
s5
s9
s4
s6
s2
s1
s3
s7
48
Geração de Polígonos Simples
Steady Growth
Polígono Simples Final
O(n2)
49
Geração de Polígonos Simples
Escolher dois pontos aleatórios
Space Partitioning
f1
i1
50
Geração de Polígonos Simples
Separar os pontos de S em dois conjuntos
Space Partitioning
f1
i1
51
Geração de Polígonos Simples
Separar os pontos de S em dois conjuntos
Space Partitioning
f1
i1
52
Geração de Polígonos Simples
Escolher um ponto x1 do conjunto da
esquerda
Space Partitioning
x1
f1
i1
53
Geração de Polígonos Simples
Dividir os pontos deste conjunto através de
uma recta que passa por x1 e intersecta a
recta inicial
Space Partitioning
x1
f1
i1
54
Geração de Polígonos Simples
Dividir os pontos deste conjunto através de
uma recta que passa por x1 e intersecta a
recta inicial
Space Partitioning
x1
f1
i1
55
Geração de Polígonos Simples
Continuar com este processo até existir um
conjunto vazio
Space Partitioning
x1
f1
x2
i1
56
Geração de Polígonos Simples
A aresta é formada pelo início e fim do
conjunto em questão
Space Partitioning
x1
f1
x2
i1
57
Geração de Polígonos Simples
A aresta é formada pelo início e fim do
conjunto em questão
Space Partitioning
x3
x1
f1
x2
i1
58
Geração de Polígonos Simples
Space Partitioning
x3
x1
f1
x2
i1
59
Geração de Polígonos Simples
Space Partitioning
x3
x1
x4
f1
x2
i1
60
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
f1
x2
x5
i1
61
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
f1
x2
x5
i1
62
Geração de Polígonos Simples
O início e o fim trocam para o conjunto da
direita
Space Partitioning
x3
x4
x1
i2
x2
x5
f2
x6
63
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
i2
x2
x5
x7
f2
x6
64
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
i2
x2
x5
x7
f2
x6
65
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
i2
x2
x5
x7
f2
x6
66
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
i2
x2
x5
x7
f2
x6
x8
67
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
i2
x2
x5
x7
f2
x9
x6
x8
68
Geração de Polígonos Simples
Space Partitioning
x3
x4
x1
i2
x2
x5
x7
f2
x9
x6
x8
69
Geração de Polígonos Simples
Space Partitioning
Polígono Simples Final
O(nlogn)
70
Geração de Polígonos Simples
Permute & Reject
Começa por calcular uma permutação dos índices dos pontos
(pode ser feita em tempo linear).
De seguida liga os pontos pela ordem da permutação e depois
verifica se gerou ou não um polígono simples.
Se o polígono final não for simples, então gera uma nova
permutação de índices.
A verificação da existência de intersecções no polígono também é
feita em tempo linear, mas o tempo real do método depende
apenas de quantos polígonos necessitam ser gerados até
encontrar um que seja realmente simples.
71
Geração de Polígonos Simples
2-Opt Moves
72
Geração de Polígonos Simples
Ligar os pontos de S aleatoriamente, por
exemplo, pela ordem por que foram gerados
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
73
Geração de Polígonos Simples
Como não resultou num polígono simples,
procura uma intersecção, por ex, s2s3 e s1s11
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
74
Geração de Polígonos Simples
Desfaz as intersecções criando as arestas s11s3 e
s1s2 ou s1s3 e s2s11.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
75
Geração de Polígonos Simples
Desfaz as intersecções criando as arestas s11s3 e
s1s2 ou s1s3 e s2s11.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
76
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
77
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
78
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
79
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
80
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
81
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
82
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
83
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
84
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
85
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
86
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
87
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
88
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
89
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
90
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
91
Geração de Polígonos Simples
Continua com este processo de modo a desfazer
as ligações sem desconexar o polígono.
2-Opt Moves
s6
s9
s10
s5
s7
s4
s11
s2
s1
s3
s8
92
Geração de Polígonos Simples
2-Opt Moves
Polígono Simples Final
O(n3)
93
Geração de Polígonos Simples
Incremental Construction & Backtracking
Escolher dois pontos aleatoriamente e uni-los. Prosseguir
escolhendo um ponto aleatório e ligando aos anteriores enquanto
a cadeia se mantiver simples. Aplicar backtracking quando existir
uma intersecção.
Obviamente, um dos objectivos principais é evitar o backtracking
exaustivo.
Este algoritmo gera todos os polígonos simples possíveis com boa
probabilidade. A sua eficiência depende do número de
backtrackings que foram necessários.
94
Geração de Polígonos Simples
Existe ainda uma heurística que é uma adaptação do
algoritmo Steady Growth. Esta encontra-se no trabalho
Generación de Polígonos Aleatorios de Pau Sanchez
Campello.
 Partition Growth - O(t log t)
(gera polígonos com pelo menos n vértices)
t é o número de vértices a mover sobre uma recta
95
Geração de Polígonos Simples
Partition Growth
Número mínimo de vértices do polígono é 10.
Gerar um polígono com três vértices.
96
Geração de Polígonos Simples
Partition Growth
Gerar uma recta que intersecte o polígono
97
Geração de Polígonos Simples
Partition Growth
Determinar os pontos de intersecção
entre a recta e o polígono.
98
Geração de Polígonos Simples
Partition Growth
Dividir em dois as arestas do polígono
que são intersectadas pela recta
99
Geração de Polígonos Simples
Partition Growth
Deslocar aleatoriamente todos os pontos de
intersecção sobre a recta, mantendo a ordem
relativa das intersecções (para não produzir
novas intersecções).
100
Geração de Polígonos Simples
Partition Growth
O número de pontos é menor que 10.
Gerar outra recta que intersecte o polígono.
101
Geração de Polígonos Simples
Partition Growth
Determinar os pontos de intersecção
entre a recta e o polígono.
102
Geração de Polígonos Simples
Partition Growth
Dividir em dois as arestas do polígono que são
intersectadas pela recta
103
Geração de Polígonos Simples
Partition Growth
Deslocar aleatoriamente todos os pontos de
intersecção sobre a recta, mantendo a ordem
relativa das intersecções (para não produzir
novas intersecções).
104
Geração de Polígonos Simples
Partition Growth
Número de pontos é menor que 10.
Gerar uma recta que intersecte o polígono.
105
Geração de Polígonos Simples
Partition Growth
Determinar os pontos de intersecção
entre a recta e o polígono.
106
Geração de Polígonos Simples
Partition Growth
Dividir em dois as arestas do polígono
que são intersectadas pela recta
107
Geração de Polígonos Simples
Partition Growth
Deslocar aleatoriamente todos os pontos de
intersecção sobre a recta mantendo a ordem
relativa das intersecções (para não produzir
novas intersecções).
108
Geração de Polígonos Simples
Partition Growth
Número de pontos é maior que 10.
O(t log t)
109
Geração de Polígonos Estrelados
Existe outra heurística para gerar polígonos estrelados que é
apresentada em Generating Random Star-Shaped Polygons de
Christian Sohler.
 Las Vegas – O(n2logn)
A heurística constrói uma partição do plano que define todos
os núcleos de polígonos estrelados (não degenerados) num
conjunto de pontos S. Trabalhando sobre esta partição,
podemos gerar todos os polígonos estrelados.
110
Geração de Polígonos
O outro trabalho tem o nome de POPS - Polygonalizations of
Point Sets de G.T. Toussaint, V. Sitaru, T. Ruso. Nele
podemos encontrar outras heurísticas para gerar polígonos
simples aleatoriamente.
http://www.cs.mcgill.ca/~ktulu/507/
 Convex Bottom - O(nlogn)
(não gera todos os polígonos simples possíveis)
 Two Peasants - O(nlogn)
(não gera todos os polígonos simples possíveis)
 Radar Sweep - O(nlogn)
(não gera todos os polígonos estrelados possíveis)
111
Geração de Polígonos Simples
Convex Bottom
112
Geração de Polígonos Simples
Convex Bottom
Encontrar os pontos de
menor e maior abcissa
xmin
xmax
113
Geração de Polígonos Simples
Convex Bottom
Criar uma recta e dividir os pontos
xmin
xmax
114
Geração de Polígonos Simples
Convex Bottom
Criar uma recta e dividir os pontos
xmin
xmax
115
Geração de Polígonos Simples
Convex Bottom
Criar o invólucro convexo de um dos grupos
de pontos
xmin
xmax
116
Geração de Polígonos Simples
Convex Bottom
Ligar os restantes pontos através da sua
abcissa
xmin
xmax
117
Geração de Polígonos Simples
Convex Bottom
Polígono Simples Final
O(nlogn)
118
Geração de Polígonos Simples
Two Peasants
119
Geração de Polígonos Simples
Two Peasants
Encontrar os pontos de
menor e maior abcissa
xmin
xmax
120
Geração de Polígonos Simples
Two Peasants
Criar uma recta e dividir os pontos
xmin
xmax
121
Geração de Polígonos Simples
Two Peasants
Criar uma recta e dividir os pontos
xmin
xmax
122
Geração de Polígonos Simples
Two Peasants
Ligar cada conjunto através da sua abcissa
xmin
xmax
123
Geração de Polígonos Simples
Two Peasants
Ligar cada conjunto através da sua abcissa
xmin
xmax
124
Geração de Polígonos Simples
Two Peasants
Ligar cada conjunto aos extremos
xmin
xmax
125
Geração de Polígonos Simples
Two Peasants
Polígono Simples Final
O(nlogn)
126
Geração de Polígonos Estrelados
Radar Sweep
127
Geração de Polígonos Estrelados
Radar Sweep
Encontrar o ponto de menor abcissa
xmin
128
Geração de Polígonos Estrelados
Radar Sweep
Ordenar os pontos em redor de p0 = xmin
p0
129
Geração de Polígonos Estrelados
Radar Sweep
Ordenar os pontos em redor de p0 = xmin
p0
p1
130
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p0
p2
p1
131
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p0
p2
p1
p3
132
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p0
p2
p1
p3
p4
133
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p0
p5
p2
p1
p3
p4
134
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p0
p5
p6
p2
p1
p3
p4
135
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p7
p0
p5
p6
p2
p1
p3
p4
136
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p8
p7
p0
p5
p6
p2
p1
p3
p4
137
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p8
p9
p7
p0
p5
p6
p2
p1
p3
p4
138
Geração de Polígonos Estrelados
Ordenar os pontos em redor de p0 = xmin
Radar Sweep
p10
p8
p9
p7
p0
p5
p6
p2
p1
p3
p4
139
Geração de Polígonos Estrelados
Ligar os pontos pela ordem que foram
encontrados (ordem dada pelos índices)
Radar Sweep
p10
p8
p9
p7
p0
p5
p6
p2
p1
p3
p4
140
Geração de Polígonos Estrelados
Ligar o primeiro ponto ao último
Radar Sweep
p10
p8
p9
p7
p0
p5
p6
p2
p1
p3
p4
141
Geração de Polígonos Estrelados
Radar Sweep
Polígono Estrelado Final
O(nlogn)
142
Geração de Polígonos Ortogonais
Em 2000, Joseph O’Rourke estava a estudar a partição de
polígonos ortogonais (de onde resultou o artigo Partitioning
Ortogonal Polygons into Fat Rectangles) e, para isso, criou
um gerador que foi baptizado de ROP – Random Orthogonal
Polygon e implementado em LISP.
Este gerador não gera polígonos através de um conjunto de
vértices mas sim através de uma grelha que vai sendo
preenchida (a selecção aleatória das células é feita por
heurísticas). A grelha tem NX por NY células e o resultado
final é um polígono cuja área contém n células. O número
final de vértices não é controlado, até porque os pontos
colineares só são retirados depois do polígono estar gerado.
Não sabemos qual a complexidade do algoritmo, mas deve
ser aproximadamente linear pois este é extremamente
rápido a obter polígonos ortogonais para um elevado número
de células.
143
Geração de Polígonos Ortogonais
Em 2003 surge o trabalho de Ana P. Tomás e de Antonio L.
Bajuelos, onde apresentam dois geradores de polígonos
ortogonais no artigo Quadratic-Time Linear-Space Algorithms
for Generating Orthogonal Polygons with a Given Number of
Vertices. Qualquer dos geradores permite controlar o número
final de vértices do polígono.
 Inflate-Cut - O(n2)
(gera todos os polígonos possíveis numa grelha)
 Inflate-Paste - O(n2)
(gera todos os polígonos possíveis numa grelha)
144
Geração de Polígonos Ortogonais
Inflate-Cut
O algoritmo começa numa célula única que vai
alargando. Para efeitos de exemplo, começa-se
já com uma parte do polígono formada
145
Geração de Polígonos Ortogonais
Inflate-Cut
Escolhe uma célula interior aleatória
146
Geração de Polígonos Ortogonais
Inflate-Cut
A célula escolhida vai “inchar” (inflate)
147
Geração de Polígonos Ortogonais
Inflate-Cut
A célula escolhida vai “inchar” (inflate)
148
Geração de Polígonos Ortogonais
Inflate-Cut
Procura as peças que podem ser cortadas (cut).
Uma peça pode cortar-se se apenas contiver
um vértice do polígono
4
1
3
2
149
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
150
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
151
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
152
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
153
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
154
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
155
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
156
Geração de Polígonos Ortogonais
Inflate-Cut
Corta a peça escolhida e obtém outro polígono
ortogonal
O(n2)
157
Geração de Polígonos Ortogonais
Inflate-Paste
O algoritmo começa por escolher
um vértice convexo v do polígono
v
158
Geração de Polígonos Ortogonais
Inflate-Paste
Selecciona uma célula que
se encontra em FSN(v).
v
Por FSN(v) entende-se o maior
polígono em escada nesta grelha
que tem v como vértice, não
intersecta o interior do polígono e
a aresta horizontal adjacente ao
vértice tem que fazer parte do
lado do polígono.
159
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
160
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
161
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
162
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
163
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
164
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
165
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
166
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
167
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
168
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
169
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
170
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
171
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
172
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
173
Geração de Polígonos Ortogonais
Inflate-Paste
Depois de seleccionada a célula, determina o ponto
central da peça e cria um novo rectângulo definido
pelo vértice v e pelo ponto central determinado.
174
Geração de Polígonos Ortogonais
Inflate-Paste
Polígono resultante.
O(n2)
175
Geração de Polígonos Ortogonais
Também existe uma alteração ao algoritmo Inflate-Cut, dos
mesmos autores, que impõe restrições à geração de
polígonos. Um exemplo de um polígono final simétrico pode
ver-se na figura seguinte:
176
Geração de Polígonos Ortogonais
No trabalho anterior existe também uma referência a um
trabalho de M. Filgueiras cuja apresentação foi apenas oral.
A ideia do algoritmo para gerar polígonos ortogonais é
semelhante à do algoritmo de O’Rourke. Este algoritmo une
rectângulos de áreas superiores à das células da grelha,
permitindo a sobreposição dos rectângulos.
177
Geração de Polígonos Monótonos
Chong Zu e outros apresentam um trabalho denominado
Generating Polygons with Given Vertices que consegue gerar
aleatoriamente polígonos monótonos em tempo linear.
Parte-se do pressuposto que Sn é um conjunto de n pontos no
plano que estão ordenados segundo a sua abcissa (supõe-se
também que não existem dois pontos com a mesma abcissa).
A ideia do algoritmo é fazer um varrimento da cadeia monótona da
esquerda para a direita (de s1 até sn) e contar o número de
polígonos monótonos possíveis neste conjunto S. Escolher um
número aleatório dentro do intervalo possível e desenhar o
respectivo polígono, desta vez, da direita para a esquerda.
Usando este algoritmo, conseguimos contar o número de
polígonos monótonos existentes, consequentemente, conseguimos
gerar uniformemente polígonos monótonos aleatórios. Este
trabalho é então a solução para o problema da geração aleatória
de polígonos monótonos e não apenas uma heurística.
178
Geração de Polígonos Monótonos
Contagem (O(n) espaço e O(K) tempo)
Seja então Si o subconjunto de S, 1  i  n. Qualquer polígono
monótono pode ser dividido em duas cadeias monótonas: cadeia
superior e a cadeia inferior. É claro que os pontos extremos (s1 e si)
pertencem a ambas as cadeias e são os únicos nestas condições.
s2
s6
s4
s7
s1
s3
s5
A contagem é recursiva, sabemos quantos polígonos existem em Si ,
N(i) através de N(j) , ou seja, do número de polígonos monótonos
que existem em Sj , j<i. Para isto, divide-se o tipo de polígonos
monótonos existentes em dois conjuntos.
179
Geração de Polígonos Monótonos
Contagem (O(n) espaço e O(K) tempo)
Estes dois conjuntos são T(i) e B(i). T(i) é o conjunto de polígonos
monótonos cuja aresta si-1si pertence à cadeira superior (top) e B(i) é
o conjunto onde a mesma aresta pertence à cadeia inferior
(bottom).
s2
s2
s5
s6
s4
s3
s7
s1
s3
s5
 T(7)
s7
s1
s4
s6
 B(7)
Sai então que N(k) = |T(k)| + |B(k)| = T(k) + B(k).
180
Geração de Polígonos Monótonos
Contagem (O(n) espaço e O(K) tempo)
Cada um deles é calculado através de VT(k) e VB(k) . O primeiro é o
conjunto de todos os pontos que sk “vê em cima” e o segundo o
conjunto de pontos que sk “vê em baixo”.
s6
s4
s1
s7
s8
s5
s2
VT(8) = {6}
VB(8) = {3,5}
s3
Basicamente, VT(k) é o conjunto de todos os pontos visíveis para sk
que se encontrem acima da linha sjsk , i < j < k. VB(k) é semelhante
mas os pontos têm que se encontrar abaixo da referida linha.
181
Geração de Polígonos Monótonos
Contagem (O(n) espaço e O(K) tempo)
Daqui sai então que:
| T (k ) | 
| B( j 1) |
jVB ( k )
| B(k ) | 
| T ( j 1) |
jVT ( k )
Cada um destes conjuntos é calculado e guardado sob a forma de
uma árvore binária. Cada conjunto superior é calculado à custa do
inferior e vice-versa, como se pode observar.
182
Geração de Polígonos Monótonos
Geração (O(n) espaço e tempo)
• Escolhe x  [1, N(n)] aleatoriamente
• Acrescenta sn à cadeia superior e à cadeia inferior
• Constrói o polígono da direita para a esquerda:
- se x  T(n) então começa pela cadeira superior (sn-1 pertence à
cadeia superior)
- senão, x = x - T(n) e começa pela cadeia inferior (sn-1 pertence à
cadeia inferior)
• Constrói as cadeias através de dois procedimentos recursivos:
Generate_Top e Generate_Bottom que se chamam mutuamente
• Acrescenta s1 à cadeia por onde começou
183
Geração de Polígonos Monótonos
O algoritmo anterior pode ser modificado para gerar
um polígono monótono dentro de outro polígono
monótono. Neste caso a complexidade sobe para
O(n + |P|), sendo |P| o número de vértices do polígono
monótono exterior.
184
Geração de Polígonos Convexos
No mesmo trabalho é referido um método de
complexidade O(n3) para gerar polígonos convexos.
Este consiste em determinar um subconjunto de
pontos de S que forme um polígono convexo.
185
APLICAÇÕES
186
Aplicações
Avaliação prática de algoritmos relativos à manipulação de
polígonos:
 verificação da sua exactidão
 determinação do tempo de execução
O problema da geração aleatória de polígonos é então
motivado pela necessidade de gerar instâncias de teste para
algoritmos geométricos. Por exemplo, para testar algoritmos
de iluminação, partição ou intersecção de polígonos. A
geração de polígonos monótonos dentro de outros polígonos
monótonos é particularmente relevante para testar
algoritmos relacionados com aspectos geográficos (GIS Geographical Information Systems) .
187
Applet
http://web.informatik.unibonn.de/I/GeomLab/polygon/RandomPolygon.html.en
188