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
 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 
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:
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
void setMode(char *mode)
Definition: artGallerySolver.C:654
Definition: artGallerySolver.h:81
void printPol(PolygonWithHolesExt pol)
Definition: artGallerySolver.C:62
void writeBestSol(char *idFile, std::ostream *solFile)
Definition: artGallerySolver.C:1083
void writePartialLog()
Definition: artGallerySolver.C:1220
PolygonWithHolesExt loadPol(char *name)
Definition: artGallerySolver.C:42
int getCardinality()
Definition: artGallerySolver.C:678
Definition: AVPLightGrid.h:43
Definition: PolygonWithHolesExt.h:42
Definition: PreSolver.h:99
int solveProblem(PolygonWithHolesExt pol)
Definition: artGallerySolver.C:1106
Definition: AuxGallery.h:65
void writeLog(char *idFile, std::ostream *logFile)
Definition: artGallerySolver.C:1094