  |
 |
Computação Gráfica
Geometria Computacional - Contagem Geométrica
|
|
Computação Gráfica
Geometria Computacional - Contagem Geométrica
Pergunta: Dada uma malha de pontos, quantos destes pontos estão dentro de um dado retângulo marcado sobre a malha ?
A solução tradicional é
contador = 0
Para cada ponto(xi,yi) da malha
se (xi >= XMin) e (xi <=Xmax) e
(yi >= YMin) e (yi <=YMax)
então contador++
Mas e se o número de pontos for muito grande ?
Algoritmo de Dominância
A Dominância de um ponto corresponde ao número de pontos dominados por ele dentro de um plano.
Um ponto P1(x1,y1) domina um ponto P2(x2,y2) se e somente se:
(x1 >= x2) e (y1 >=y2)
A idéia é cria uma malha sobre os pontos do problema. Em cada ponto se passa uma linha horizontal e outra vertical. Os pontos não precisam estar espaçados de forma regular.
Nesta malha, em cada célula, todos os pontos internos tem a mesma dominância do ponto superior direito
Preenche-se a malha com a dominância em cada célula.
Para saber quantos pontos estão em um retângulo marcado sobre a malha calcula-se a dominância em cada vértice do retângulo.
Q(p) = dominância de P
Nro de Ptos dentro do retângulo: Q(C) - Q(B) - Q(D) + Q(A)
Exemplo:
Q(A) = 0, Q(B)= 1, Q(C)= 3, Q(D)= 0
Nro. de pontos = 3 - 1 - 1 + 0 = 1 ponto
FIM.