AGSol (Art Gallery Solver) 1.0.2 This package contains a software capable of optimally solving the Art Gallery Problem (AGP), one interesting NP-hard problem from the Computational Geometry field. The algorithm implemented in this solution, which can be today considered the state-of-the-art technique on the AGP, can be found in details in the following paper: Davi C. Tozoni, Pedro J. de Rezende, Cid C. de Souza. A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

- Main Page
- Classes
- Files

- File List

All Classes Functions
AuxGallery.h
1 /*****************************************************************************
2 * This code is part of Art Gallery Solver (AGSol) Package, which aims the
3 * resolution of the Art Gallery Problem With Point Guards.
4 *
5 * This software version (1.0.2) has been tested under and is compatible with
6 * CGAL 3.9 and GLPK 4.52.
7 *
8 * Authors:
9 * Davi Colli Tozoni - davi.tozoni@gmail.com
10 * Marcelo Castilho Couto - coutomarcelo@gmail.com
11 *
12 * AGSol Concept and Design:
13 * Davi Colli Tozoni, Marcelo Castilho Couto, Pedro Jussieu de Rezende & Cid
14 * Carvalho de Souza.
15 *
16 * Other information can be found at:
17 * http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/index.html
18 *
19 * --
20 *
21 * This program is free software: you can redistribute it and/or modify it
22 * under the terms of the GNU General Public License as published by the Free
23 * Software Foundation, either version 3 of the License, or (at your option)
24 * any later version.
25 *
26 * This program is distributed in the hope that it will be useful, but
27 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
28 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
29 * for more details.
30 *
31 * You should have received a copy of the GNU General Public License along
32 * with this program. If not, see <http://www.gnu.org/licenses/>.
33 *
34 ****************************************************************************/
35
36
37 #ifndef AUX_GALLERY_H
38 #define AUX_GALLERY_H
39
40 #include "PolygonExt.h"
41 #include "PolygonWithHolesExt.h"
42
43 #include <CGAL/copy_n.h>
44 #include <CGAL/point_generators_2.h>
45 #include <CGAL/Polygon_set_2.h>
46
47 #include <limits>
48 #include <stdlib.h>
49 #include <malloc.h>
50 #include <iostream>
51 #include <time.h>
52 #include <algorithm>
53 #include <sstream>
54 #include <iostream>
55 #include <fstream>
56 #include <tr1/unordered_map>
57
58 typedef Polygon::Vertex_const_iterator Vertex_iterator;
59
60 using namespace std;
61
65 typedef struct
66 {
67 long operator() (const pair<Point, Point> &k) const {
68 std::stringstream out;
69 out << k.first << ":" << k.second;
70 return std::tr1::hash<std::string>()(out.str());
71 }
72 } PointPointHash;
73
77 typedef struct
78 {
79 long operator() (const Point &k) const {
80 std::stringstream out;
81 out << k;
82 return std::tr1::hash<std::string>()(out.str());
83 }
84 } PointHash;
85
89 vector<PolygonExt> splitNonSimple(PolygonExt pol);
90
94 string getFileName(string polFileName);
95
99 int fractionSize(RT x);
100
104 Point internalPoint(PolygonWithHoles polWHoles);
105
109 Point internalPoint(Polygon pol);
110
114 Point findSimplerInteriorPoint(PolygonWithHoles polWHoles, Point p);
115
119 Point findSimplerInteriorPoint(Polygon pol, Point p);
120
124 RT * truncateFraction(string num, string den, int size);
125
126 #endif
PointHash
Definition: AuxGallery.h:77
PolygonExt
Definition: PolygonExt.h:62
PointPointHash
Definition: AuxGallery.h:65