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

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

+1 voto
39 visitas
perguntada Nov 18, 2020 em Outros por Luiz Filippe (21 pontos)  
editado Nov 23, 2020 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

+1 voto
respondida Nov 18, 2020 por Luiz Filippe (21 pontos)  
editado Nov 22, 2020 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.

comentou Dez 19, 2020 por Arthur Quintão (11 pontos)  

Excelente resposta, Luiz!

Somente uma consideração sobre seu código.
Acho que seria mais interessante definir uma matriz como variável ao invés das coordenadas de forma isolada.
Considerando tal sugestão, seria possível utilizar uma compression list no lugar do 2º for loop.

for triangulo in triangulos:
    for i, pt enumerate (triangulo):
        matriz=np.append(matriz,[pt[j],triangulo[(i + 1) % 3][3*j] for j in range (2)])
...