## Introduction

From Wikipedia

The **art gallery problem** or **museum problem** is a well-studied visibility problem in computational geometry. The motivation for the problem is the real-world problem of guarding an art gallery with the minimum number of security cameras that can each rotate to obtain a full field of vision. In the computational geometry version of the problem the layout of the art gallery is represented by a simple polygon and each security camera is represented by a point in the polygon. A set *S* of points is said to guard a polygon if, for every point *p* in the polygon, there is some such that the line segment between *p* and *q* does not leave the polygon.

As in my computational-graphics course, I was requested to implement a solution program to the **art gallery problem** stated above. So using cut-ear triangulation and 3-coloring algorithms, I did implement the above program in screenshot.

## Background

The reader needs to have basic knowledge of computational-geometry (polygons, points, etc..)

## Theory

### Two-Ears

A principal vertex pi of a simple polygon P is called a ear if the diagonal (pi-1, pi+1) that bridges pi lies entirely in P. We say that two ears pi and pj are non-overlapping if the interior of triangle (pi-1, pi, pi+1) does not intersect the interior of triangle (pj-1, pj, pj+1)

Note: The program code uses 'Polygon Triangulation in C#' of fgshen (http://www.codeproject.com/csharp/cspolygontriangulation.asp) as skeleton triangulation code. For more info about the triangulation and two-ears theorem, please check the page.

### 3-coloring

Graph 3-coloring is the task of coloring each node of the graph either red, green, or blue with the constraint that the two endpoints of any edge must get different colors.

## Using the code

Basically the code is developed with Visual Studio 2005 using C#. The code uses the

`System.Drawing `

library for most drawing and computational-geometry.

Here's a class list for the code.

### Triangulation - triangulate()*

Handles the two-ears theorem triangulation algorithm.

public void triangulate()
{
mPolygon poly = new mPolygon(updated_vertices);
Boolean finished = false;
if (updated_vertices.Length == 3)
finished = true;
Point p = new Point();
while (finished == false)
{
int i = 0;
Boolean not_found = true;
while (not_found && (i < updated_vertices.Length))
{
p = updated_vertices[i];
if (is_ear(p))
not_found = false;
else
i++;
}
update_vertices(p);
poly = new mPolygon(updated_vertices);
if (updated_vertices.Length == 3)
finished = true;
}
polygons = new Point[ears.Count + 1][];
for (int i = 0; i < ears.Count; i++)
{
Point[] points = (Point[])ears[i];
polygons[i] = new Point[3];
polygons[i][0] = points[0];
polygons[i][1] = points[1];
polygons[i][2] = points[2];
}
polygons[ears.Count] = new Point[updated_vertices.Length];
for (int i = 0; i < updated_vertices.Length; i++)
{
polygons[ears.Count][i] = updated_vertices[i];
}
}

### Triangulation - is_ear()*

Check if given point is in a valid ear.

private Boolean is_ear(Point p)
{
mPolygon m = new mPolygon(updated_vertices);
if (m.is_vertex(p) == true)
{
if (m.vertex_type(p) == VertexType.ConvexPoint)
{
Point curr_point = p;
Point prev_point = m.get_prev_point(p);
Point next_point = m.get_next_point(p);
for (int i = updated_vertices.GetLowerBound(0);
i < updated_vertices.GetUpperBound(0); i++)
{
Point pt = updated_vertices[i];
if (!(is_points_equal(pt, curr_point) ||
is_points_equal(pt, prev_point) ||
is_points_equal(pt, next_point)))
{
if (is_point_in_triangle(new Point[]
{ prev_point, curr_point, next_point }, pt))
return false;
}
}
}
else
return false;
return true;
}
return false;
}

### 3-Coloring - traverse()

Start point for 3-coloring algorithm. Colors the last processed polygon and calls the deep-first coloring algorithm

public void traverse()
{
int last_poly = polygons.Length - 1;
lb.Items.Add("[p" + last_poly + "] Last Polygon: \t" +
polygons[last_poly][0] + polygons[last_poly][1] +
polygons[last_poly][2]);
vertex_colors[get_index(polygons[last_poly][0])] = vertex_color.Red;
vertex_colors[get_index(polygons[last_poly][1])] = vertex_color.Blue;
vertex_colors[get_index(polygons[last_poly][2])] = vertex_color.Green;
colorize(0);
}

### 3-Coloring - colorize()

Deep-first algorithm to assign colors for vertexes.

public void colorize(int i)
{
int next = i + 1;
if (next < input_vertices.Length)
{
colorize(next);
}
find_polygons(input_vertices[i]);
}

### 3-Coloring - find_polygons()

Find polygons related for a given point. Used in 3-coloring algorithm for finding a given points related polygons and if there's non-color assigned vertex in that found polygon, the code assigns it a color.

public void find_polygons(Point p)
{
int v0_index, v1_index, v2_index;
for (int i = polygons.Length - 1; i > -1; i--)
{
if ((p == polygons[i][0]) || (p == polygons[i][1]) ||
(p == polygons[i][2]))
{
for (int j = 0; j < 3; j++)
{
v0_index = get_index(polygons[i][j]);
v1_index = get_index(polygons[i][(j + 1) % 3]);
v2_index = get_index(polygons[i][(j + 2) % 3]);
if (vertex_colors[v0_index] == vertex_color.Empty)
{
vertex_colors[v0_index] =
find_color(vertex_colors[v1_index],
vertex_colors[v2_index]);
lb.Items.Add("[s" + v0_index + "]
Assigned color: \t" + str_color
(vertex_colors[v0_index]) + " {" +
str_color(vertex_colors[v1_index]) +
" ," + str_color(vertex_colors[v2_index]) +
"} " + polygons[i][j]);
}
}
}
}
}

## Running the program

### Drawing a polygon

Using the left mouse button, mark the vertices of the polygon.

Use the right mouse button to let program finalize the polygon.

### Triangulate

Use the `Triangulate `

button to let program run triangulation algorithm.

### 3-Color

Use the 3-Color button to let program 3-color the vertices.

### Animation

The program can animate the 3-coloring algorithm both using the `animate `

button or by clicking a step in `listbox`

.

### Guard-Scanning

The program can scan selected guards view area by the scan buttons.

## History

- 04.05.2007 - Initial post

## References

* Triangulation code mostly based on http://www.codeproject.com/csharp/cspolygontriangulation.asp