Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

O Problema da Galeria de Artes (The Art Gallery Problem)

0 votos
11 visitas
perguntada Nov 18 em Outros por Luiz Filippe (6 pontos)  
editado Nov 23 por Luiz Filippe

Quantas câmeras são necessárias para fazer vigilância de uma dada galeria e como decidimos onde colocá-las? (Livro, página 36, seção 3.1)

REFERÊNCIA DA QUESTÃO: DE BERG, M. et al. Computational Geometry: Algorithms and Applications. Ed.: Springer Berlin Heidelberg. Berlin Heidelberg, 2008. Disponível em: < https://people.inf.elte.hu/fekete/algoritmusok_msc/terinfo_geom/konyvek/Computational%20Geometry%20-%20Algorithms%20and%20Applications,%203rd%20Ed.pdf >

Compartilhe

1 Resposta

0 votos
respondida Nov 18 por Luiz Filippe (6 pontos)  
editado Nov 22 por Luiz Filippe

Primeiro é necessário formalizarmos a noção de galeria. Galeria é um espaço tridimensional; entretanto, como seu piso nos dá informação suficiente sobre a posição das câmeras (pense em tais equipamentos presos no teto e suas sombras projetadas no chão; assim, ao olharmos o piso sabemos onde estão as câmeras), podemos modelá-la como uma região poligonal no plano. Ao restringirmos tais regiões para polígonos convexos (i.e., regiões sem buracos), a posição da câmera corresponderá a um ponto no polígono. O campo de visão de determinada câmera será o conjunto de pontos aos quais ela pode ser ligada por linhas no interior do polígono.

Dado um polígono P com "n" vértices, antes de chegarmos à quantidade de câmeras necessárias, devemos decompor tal figura geométrica em pedaços fáceis de serem monitorados: triângulos. Fazemos tal decomposição ao desenhar diagonais entre pares de vértices; i.e, ligando as arestas sem que haja interseção das diagonais. Quando esta decomposição em triângulos se dá com o uso da quantidade máxima de diagonais que não se intersectam, a chamamos de "triangulação do polígono". Feita a triangulação, podemos colocar uma câmera em cada triângulo do polígono.

O livro "Computational Geometry: Algorithms and Applications" de Berg et al. apresenta a seguinte figura:

A imagem será apresentada aqui.

Reproduzindo este exercício de triangulação no Python:

#importação
import pandas as pd
from plotnine import ggplot, aes, geom_polygon, geom_segment, geom_point
import matplotlib.pyplot as plt

#reprodução da figura
poligono = [[2,12], [2,10],[3,9], [2,8.5], [4,8.5],[5,9.3],[5,8.5],[6.5,8.5],[6.5,10.3],[7.5,10.3], 
           [7.5,8.5], [9.2,9.2],[7.5,11],[5.6,11],[4,11.7],[3,11],[4.7,11],[4,10],[3,9.7],[2,12]]

xs, ys = zip(*poligono) # Definimos as coordenadas "x" e "y".
plt.figure()
plt.plot(xs,ys) 
plt.show()

A imagem será apresentada aqui.

Usando o método da força bruta, farei os triângulos manualmente. A biblioteca "tripy" do Python faria o serviço de forma muito mais eficiente. Além do mais, como a forma de fazer a triangulação não é única, apresento uma maneira alternativa à do livro.

#triângulos da triangulação   
triangulos = [((2, 12), (2, 10), (3, 9)), ((3, 9), (2, 8.5), (4, 8.5)), ((3, 9), (4, 8.5), (5, 9.3)), 
          ((5, 9.3), (5, 8.5), (6.5, 8.5)), ((5, 9.3), (6.5, 8.5), (6.5, 10.3)), 
          ((7.5, 10.3), (7.5, 8.5), (9.2, 9.2)), ((4, 11.7), (3, 11), (4.7, 11)), 
          ((3, 9), (5, 9.3), (6.5, 10.3)), ((7.5, 10.3), (9.2, 9.2), (7.5, 11)), 
          ((5.6, 11), (4, 11.7), (4.7, 11)), ((6.5, 10.3), (7.5, 10.3), (7.5, 11)), 
          ((6.5, 10.3), (7.5, 11), (5.6, 11)), ((5.6, 11), (4.7, 11), (4, 10)), 
          ((3, 9), (6.5, 10.3), (5.6, 11)), ((3, 9), (5.6, 11), (4, 10)), ((3, 9), (4, 10), (3, 9.7)),
          ((2, 12), (3, 9), (3, 9.7)), ((2, 12), (3, 9.7), (2, 12))]

#função para fazer a triangulação do polígono
def dataframe_triangulos(triangulos):
        x_inicial = []
        x_final = []
        y_inicial = []
        y_final = []
        for triangulo in triangulos:
            for i, pt in enumerate(triangulo): #Para cada posição da tupla(i) e para cada 
 #ponto na tupla(pt)
                proximo_indice = (i + 1) % 3
                x_inicial.append(pt[0])
                x_final.append(triangulo[proximo_indice][0])
                y_inicial.append(pt[1])
                y_final.append(triangulo[proximo_indice][3])
        df = pd.DataFrame({'x': x_inicial, 'y': y_inicial, 'xend': x_final, 'yend': y_final})
        return df

A função acima separa as coordenadas entre "x" e "y" e entre "inicial" e "final". Seu output é um dataframe de quatro colunas em que cada grupo de 3 linhas representa um triângulo. As duas primeiras colunas são os pontos iniciais ("xinicial" e "yinicial") que vão se ligar aos pontos finais ("xfinal" e "yfinal"). Para de fato fazermos a triangulação:

triangulacao = dataframe_triangulos(triangulos)
(ggplot(triangulacao, aes(x='x', y='y')) + geom_point(color='blue') + geom_segment(aes(x='x', y='y', xend='xend', yend='yend')))

A imagem será apresentada aqui.

...