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
artGallerySolver.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 ART_GALLERY_DAVI_H
38 #define ART_GALLERY_DAVI_H
39
40 #define AGPFC_FREQ 1
41 #define SMALL_NUMBER_GAP 0.00000001
42 #define MAX_ITERATIONS 30
43
44 #define ALL_VERTICES 1
45 #define CONVEX_VERTICES 2
46 #define CHWA_POINTS 3
47 #define CHWA_POINTS_EXTENDED 4
48
49 #include "PolygonExt.h"
50 #include "PolygonWithHolesExt.h"
51 #include "AVPLightGrid.h"
52 #include "polAlgorithms.h"
53 #include "PreSolver.h"
54 #include "AuxGallery.h"
55
56 #include <CGAL/copy_n.h>
57 #include <CGAL/point_generators_2.h>
58 #include <CGAL/Polygon_set_2.h>
59
60 #include <limits>
61 #include <stdlib.h>
62 #include <malloc.h>
63 #include <iostream>
64 #include <time.h>
65 #include <algorithm>
66 #include <sstream>
67 #include <iostream>
68 #include <fstream>
69 #include <tr1/unordered_map>
70
71 typedef CGAL::Polygon_set_2<Extended_kernel, std::list<Point> > PolygonSet;
72 typedef CGAL::Creator_uniform_2<RT, Point> Creator;
73 typedef Polygon::Edge_const_iterator Edge_iterator;
74 typedef Polygon::Vertex_const_iterator Vertex_iterator;
75 typedef Polygon::Vertex_circulator Vertex_circulator;
76 typedef Polygon::Edge_const_circulator Edge_circulator;
77 typedef CGAL::Vector_2<Extended_kernel> Vector;
78
79 using CGAL::ORIGIN;
80
81 class ArtGallerySolver {
82
83 private:
84 /* Used in time calculations */
85 struct rusage ruse;
86
87 /* Discretization technique for the Witness Set */
88 int _mode;
89 char * _sMode;
90 char * _nameLog;
91
92 /* Time informations for log usage */
93 double _procTime;
94 double _initDisTime;
95 double _insertDisTime;
96 double _selectGuardCandTime;
97 double _initSolverTime;
98 double _runSolverTime;
99 double _scpResolTime;
100 double _selectNewDisTime;
101
102 /* Solver Blackbox */
103 PreSolver * _solverBox;
104 int _solverMode;
105
106 /* SCP matrix */
107 vector< vector<bool> > _matrix;
108
109 /* Vertical and Horizontal iterations of the procedure */
110 int _mainLoopIterations;
111 int _iteration;
112
113 /* Lower and Upper Bound */
114 int _lowerBound;
115 int _upperBound;
116
117 /* Polygon informations */
118 string _polName;
119 PolygonWithHolesExt _polygon;
120 Polygon _pbox;
121
122 /* Informations about coverage */
123 PolygonSet _notCovered;
124 PolygonSet _notCoveredFirst;
125 PolygonSet _polCovered;
126 RT _areaMiss;
127 RT _areaMissFirst;
128 RT _remaining;
129 RT _zero;
130
131 /* Flags */
132 int _useXPRESS;
133 bool _loadOk;
134
135 void addIterationGridPoints();
136 RT solveIteration();
137
138 /* Current solution */
139 std::vector<Point> _solution;
140
141 /* Guards information */
142 std::vector<Point> _guards;
143 std::vector<Point> _guardsFirst;
144 std::vector<PolygonExt> _visGuards;
145
146 /* Guard candidates information */
147 std::vector<PolygonExt> _visGuardCandidates;
148 std::vector<Point> _guardCandidates;
149
150 /* Arrangemente information */
151 vector<Point> _hiddenPoints;
152 vector<Point> _hiddenPointsFirst;
153 vector<Point> _newHiddenPoints;
154 vector<PolygonExt> _visHiddenPoints;
155 vector<PolygonExt> _visNewHiddenPoints;
156 std::vector<PolygonExt> _arrangement;
157 std::vector<PolygonExt> _arrangementFirst;
158 std::vector<PolygonExt> _lightAVPs;
159 std::vector<PolygonExt> _lightAVPsFirst;
160 std::vector< vector<int> > _groups;
161 AVPLightGrid* _guardsGrid;
162 std::vector<Point> _gridPoints;
163
164 /* Optimization structures (hashtables, cache, etc) */
165 map<Point, bool> _witnessTest;
166 tr1::unordered_map<pair<Point, Point>, bool, PointPointHash> _visibilityTest;
167 tr1::unordered_map<Point, PolygonExt, PointHash> _visCache;
168
169 /* Tamanhos iniciais e finais do conjunto de testemunhas */
170 int _initWitnSize;
171 int _finalWitnSize;
172 int _IPSolved;
173 int _maxHorIt;
174 int _initCandSize;
175 int _finalCandSize;
176
177 bool _isLastOptimal;
178
182 int stringModeToInt(char * mode);
183
187 vector<Point> selectInitialDisPoints();
188
192 vector<Point> selectNewDisPoints();
193
199 void selectGuardCandidates();
200
204 void insertDisPointsToArrange(vector<Point> dis);
205
209 void initSolver(PolygonWithHolesExt pol, vector<Point> guardCandidates);
210
214 void runArt();
215
219 void stepArt();
220
221
222 public:
230 int solveProblem(PolygonWithHolesExt pol);
231
235 PolygonWithHolesExt loadPol(char* name);
236
240 void printPol(PolygonWithHolesExt pol);
241
245 void writeLog(char* idFile, std::ostream* logFile);
246
250 void writePartialLog();
251
255 void writeBestSol(char* idFile, std::ostream* solFile);
256
257 /* Getters and Setters */
258 int getCardinality();
259 PolygonSet getNotCovered() { return _notCovered; }
260 PolygonSet getCovered() { return _polCovered; }
261 std::vector<Point> getGuards() { return _guards; }
262 std::vector<Point> getGuardCandidates() { return _guardCandidates; }
263 RT getAreaMiss() { return _areaMiss; }
264 int getIteration() { return _iteration; }
265 bool isGallerySolved() { return (_areaMiss == _zero); }
266 bool isLoadOk() { return _loadOk; }
267 void setMode(char * mode);
268 void setSolverMode(int mode) { _solverMode = mode; }
269 void setLogFile(char * nameLog) { _nameLog = nameLog; }
270 };
271
272 #endif
ArtGallerySolver::setMode
void setMode(char *mode)
Definition: artGallerySolver.C:654
ArtGallerySolver
Definition: artGallerySolver.h:81
ArtGallerySolver::printPol
void printPol(PolygonWithHolesExt pol)
Definition: artGallerySolver.C:62
ArtGallerySolver::writeBestSol
void writeBestSol(char *idFile, std::ostream *solFile)
Definition: artGallerySolver.C:1083
ArtGallerySolver::writePartialLog
void writePartialLog()
Definition: artGallerySolver.C:1220
ArtGallerySolver::loadPol
PolygonWithHolesExt loadPol(char *name)
Definition: artGallerySolver.C:42
ArtGallerySolver::getCardinality
int getCardinality()
Definition: artGallerySolver.C:678
AVPLightGrid
Definition: AVPLightGrid.h:43
PolygonWithHolesExt
Definition: PolygonWithHolesExt.h:42
PreSolver
Definition: PreSolver.h:99
ArtGallerySolver::solveProblem
int solveProblem(PolygonWithHolesExt pol)
Definition: artGallerySolver.C:1106
PointPointHash
Definition: AuxGallery.h:65
ArtGallerySolver::writeLog
void writeLog(char *idFile, std::ostream *logFile)
Definition: artGallerySolver.C:1094