O problema da galeria de arte é um dos problemas mais conhecidos da geometria computacional. Ele busca responder à seguinte pergunta: dada a planta (vértices de um polígono) de uma galeria de arte, qual é o número mínimo de câmeras com visão de 360º necessárias para vigiar todos os cômodos da galeria?
Existem várias versões desse problema. Algumas, como a versão em que a localização das câmeras é restrita aos vértices do polígono, são classificadas como NP-completas. Não abordaremos a demonstração disso aqui.
Contudo, podemos observar que um polígono convexo pode ser vigiado por inteiro com uma câmera localizada em um dos seus vértices. Com base no teorema que afirma que todo polígono simples possui pelo menos uma triangulação com n-2 triângulos, podemos chegar a uma solução interessante. Pelo teorema de Chvátal, sabemos que piso de n/3 vértices são sempre suficientes para cobrir todo o polígono. Isso é provado por Fisk, que demonstrou que é possível realizar uma 3-coloração do grafo resultante da triangulação.
Portanto, para obtermos uma solução aproximada para o problema da galeria de arte, basta triangular o polígono e, em seguida, realizar uma 3-coloração, onde cada cor representa uma distribuição de câmeras suficiente para vigiar toda a galeria.
Para obter a triangulação, podemos utilizar o algoritmo de Ear-Clipping (corte de orelhas), que possui complexidade quadrática, embora existam outras implementações mais eficientes que rodam em tempo O(nlog(n)).
O algoritmo de Ear-Clipping baseia-se no Teorema das Duas Orelhas, que afirma que todo polígono simples com pelo menos 4 vértices possui pelo menos 2 orelhas (triângulos com dois lados sendo arestas do polígono e um terceiro lado completamente interior ao polígono). O algoritmo consiste em:
def earclip(points: list[tuple[int, int]]):
# Calculamos todos os vértices que formam uma ponta de orelha
ears = {i for i in range(len(points)) if check_ear(i, points)}
to_remove = list(range(len(points)))
trimmed_polygon = deepcopy(points)
triangles = []
while len(to_remove) > 3:
# Removemos uma ponta de orelha
curr_ear = ears.pop()
idx = to_remove.index(curr_ear)
# Adicionamos a orelha removida à lista de triângulos
n = len(to_remove)
triangles.append((to_remove[(idx-1) % n], to_remove[idx], to_remove[(idx+1) % n]))
# Removemos a ponta de orelha atual da lista de vértices
to_remove.remove(curr_ear)
del trimmed_polygon[idx]
# Atualizamos o status dos vértices adjacentes
for cand in [(idx - 1) % len(to_remove), idx % len(to_remove)]:
if check_ear(cand, trimmed_polygon):
ears.add(to_remove[cand])
elif to_remove[cand] in ears:
ears.remove(to_remove[cand])
# Adicionamos o triângulo formado pelos três vértices restantes à lista de triângulos
triangles.append(tuple(to_remove))
return triangles
A função auxiliar check_ear utilizada acima, pode ser facilmente implementada utilizando orientação relativa de segmentos de reta:
def check_ear(idx: int, points: list[tuple[int, int]]) -> bool:
# Checa se o vértice idx é uma ponta de orelha
n = len(points)
t = [points[(idx-1)%n], points[idx], points[(idx+1)%n]]
return signal(t[1], t[2], t[0]) > 0 and not any_point_in_triangle(*t, points)
def signal(p0, p1, p2) -> float:
# Retorna o produto vetorial entre p0p2 e p1p2
return (p0[0]-p2[0]) * (p1[1]-p2[1]) - (p1[0]-p2[0]) * (p0[1]-p2[1])
def point_in_triangle(p0: tuple[int, int], p1: tuple[int, int],
p2: tuple[int, int], checked_point: tuple[int, int]) -> bool:
# Checa se o ponto checked_point está dentro do triângulo formado por p0, p1 e p2
d1 = signal(checked_point, p0, p1)
d2 = signal(checked_point, p1, p2)
d3 = signal(checked_point, p2, p0)
has_neg = d1 < 0 or d2 < 0 or d3 < 0
has_pos = d1 > 0 or d2 > 0 or d3 > 0
return not(has_neg and has_pos)
def any_point_in_triangle(p0: tuple[int, int], p1: tuple[int, int],
p2: tuple[int, int], points: list[tuple[int, int]]) -> bool:
# Checa se algum dos vértices restantes está contido no triângulo formado por p0, p1 e p2
for p_check in points:
if p_check != p0 and p_check != p1 and p_check != p2 and point_in_triangle(p0, p1, p2, p_check):
return True
return False
Podemos então, encontrar uma 3-coloração para a triangulação do polígono da seguinte maneira: iniciamos colorindo um triângulo com uma cor para cada vértice e, em seguida, propagamos as cores pelos demais triângulos utilizando uma busca em profundidade.
def tri_color_graph(graph: list[list[int]], triangles: list[tuple[int, int, int]],
num_points: int) -> list[int]:
# Designamos 0, 1 ou 2 para cada vértice, representando sua cor (-1 significa que não foi colorido ainda)
colors = [-1] * num_points
# Colorimos o primeiro triângulo
v1, v2, v3 = triangles[0]
colors[v1] = 0
colors[v2] = 1
# Fazemos uma busca em profundidade sobre as arestas do grafo
visited = [False] * len(graph)
dfs_color(graph, triangles, 0, visited, colors)
return colors
def dfs_color(graph: list[list[int]], triangles: list[tuple[int, int, int]],
vertice: int, visited: list[bool], colors: list[int]) -> None:
# Marcamos o vértice atual como visitado
visited[vertice] = True
# Dois vértices do triângulo atual já devem estar coloridos, então encontramos a cor do próximo
curr_colors = [colors[v] for v in triangles[vertice]]
remaining_color = ({0,1,2,-1} - set(curr_colors)).pop()
colors[triangles[vertice][curr_colors.index(-1)]] = remaining_color
# Visitamos os vértices adjacentes
for neighbor in graph[vertice]:
if not visited[neighbor]:
dfs_color(graph, triangles, neighbor, visited, colors)
Abaixo, você encontra uma animação exemplificando a execução desse problema, que poderá ajudar na visualização e compreensão dos passos descritos.
Este projeto foi realizado pelos seguintes alunos da disciplina Algoritmos II: