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
IGrid.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 IGRID_H
38 #define IGRID_H
39
40 #include "PolygonExt.h"
41 #include "PolygonWithHolesExt.h"
42
43 #include <time.h>
44 #include <stdlib.h>
45 #include <malloc.h>
46
47 /* Procedure for measuring runtime. Implemented by Ionut Aaron (Brown,GSIA). */
48 #ifndef __SYSTEM_TIME_H
49 #define __SYSTEM_TIME_H
50
51 /* Ionut Aron, ia@cs.brown.edu (1999-2001)
52 * created: August, 1999
53 * last updated: December 20, 2001
54 */
55
56 #include <sys/resource.h>
57 #include <sys/types.h>
58 #include <time.h>
59
60 extern int getrusage();
61
62 // this macro produces a time equal to the one produced by clock(),
63 // but does not suffer from the wraparound problem of clock()
64
65 #define CPUTIME(ruse) (\
66 getrusage(RUSAGE_SELF,&ruse),\
67 ruse.ru_utime.tv_sec + ruse.ru_stime.tv_sec + \
68 1e-6 * (ruse.ru_utime.tv_usec + ruse.ru_stime.tv_usec)\
69 )
70
71 /* usage of the CPUTIME timing routine:
72 ===================================
73
74 struct rusage ruse;
75 double t0 = CPUTIME(ruse);
76 ...
77 double t1 = CPUTIME(ruse);
78 printf("CPU time: %f secs.\n", t1-t0);
79 */
80
81 // global variable
82 // struct rusage ruseTime;
83
84 #endif
85
86 class IGrid {
87 protected:
88 PolygonWithHolesExt _polygon;
89 std::vector<PolygonExt> _visPol;
90 std::vector<Point> _grid;
91
92 bool _visOk;
93 bool _debug;
94 int _gridMem;
95 double _gridTime;
96
97 std::vector<PolygonExt> _struct1;
98 std::vector<PolygonExt> _struct2;
99
100 public:
104 IGrid() { _visOk = false; _debug = false; _gridMem = 0; }
105 virtual ~IGrid() { }
106
110 void setPolygon(PolygonWithHolesExt polygon);
111
115 void setVisibilityPolygons(std::vector<PolygonExt> visPol);
116
120 virtual void makeGrid() = 0;
121
125 int getGridMem() { return _gridMem; }
126
130 void addGridPoint(Point p);
131
135 std::vector<Point> getGridPoints() { return _grid; }
136
140 std::vector<PolygonExt> getStruct1() { return _struct1; }
141
145 std::vector<PolygonExt> getStruct2() { return _struct2; }
146
147 };
148
149 #endif
150
IGrid
Definition: IGrid.h:86
IGrid::IGrid
IGrid()
Definition: IGrid.h:104
IGrid::getGridMem
int getGridMem()
Definition: IGrid.h:125
IGrid::getStruct2
std::vector< PolygonExt > getStruct2()
Definition: IGrid.h:145
IGrid::setPolygon
void setPolygon(PolygonWithHolesExt polygon)
Definition: IGrid.C:57
PolygonWithHolesExt
Definition: PolygonWithHolesExt.h:42
IGrid::addGridPoint
void addGridPoint(Point p)
Definition: IGrid.C:42
IGrid::getStruct1
std::vector< PolygonExt > getStruct1()
Definition: IGrid.h:140
IGrid::getGridPoints
std::vector< Point > getGridPoints()
Definition: IGrid.h:135
IGrid::makeGrid
virtual void makeGrid()=0
IGrid::setVisibilityPolygons
void setVisibilityPolygons(std::vector< PolygonExt > visPol)
Definition: IGrid.C:49