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
Arrangement.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 MYARRANGEMENT_H
38 #define MYARRANGEMENT_H
39 
40 #include "IGrid.h"
41 
42 #include <CGAL/Arr_segment_traits_2.h>
43 #include <CGAL/Arrangement_2.h>
44 #include <CGAL/Arr_extended_dcel.h>
45 #include <CGAL/Arr_observer.h>
46 
47 typedef CGAL::Arr_segment_traits_2<Extended_kernel> ArrTraits;
48 typedef CGAL::Arr_extended_dcel<ArrTraits, bool, short, bool> DCEL; // Vertex, HE, Face
49 typedef CGAL::Arrangement_2<ArrTraits, DCEL> Arrangement;
50 
57 class MyObserver : public CGAL::Arr_observer<Arrangement> {
58  private:
59  short _nextVal;
60  short _nextValTwin;
61  bool _nextBool;
62  bool _starterEdge;
63  Segment _originalSeg;
64 
65  public:
70  MyObserver(Arrangement& arr) : CGAL::Arr_observer<Arrangement>(arr) { _starterEdge = true; }
71 
76  void setStarterEdge(bool b) { _starterEdge = b; }
77 
82  void setOriginalSeg(Segment seg) { _originalSeg = seg; }
83 
88  virtual void before_create_edge (const X_monotone_curve_2& s, Vertex_handle v1, Vertex_handle v2) {
89  if (_starterEdge) return;
90  Segment sIni = (Segment) s;
91  if (Segment(v1->point(), v2->point()).direction() != sIni.direction()) {
92  _nextVal = 1;
93  _nextValTwin = 0;
94  } else {
95  _nextVal = 0;
96  _nextValTwin = 1;
97  }
98  }
99 
104  virtual void after_create_edge (Halfedge_handle e) {
105  if (!_starterEdge) {
106  e->set_data(_nextVal);
107  e->twin()->set_data(_nextValTwin);
108  } else {
109  // polygon edges must have -1!!!!
110  e->set_data(-1);
111  e->twin()->set_data(-1);
112  }
113  }
114 
119  virtual void before_split_edge (Halfedge_handle e, Vertex_handle v, const X_monotone_curve_2& s1, const X_monotone_curve_2& s2){
120  _nextVal = e->data();
121  _nextValTwin = e->twin()->data();
122  }
123 
130  virtual void after_split_edge (Halfedge_handle e1, Halfedge_handle e2) {
131  e1->set_data(_nextVal);
132  e2->set_data(_nextVal);
133  e1->twin()->set_data(_nextValTwin);
134  e2->twin()->set_data(_nextValTwin);
135  }
136 
143  virtual void before_modify_edge (Halfedge_handle e, const X_monotone_curve_2& s) {
144  // especial edges (those who are light and shadow) also have -1
145  _nextBool = false;
146  if (Segment(e->source()->point(), e->target()->point()).direction() != _originalSeg.direction()) {
147  if (e->data() == 0) {
148  _nextBool = true;
149  _nextVal = -1;
150  _nextValTwin = -1;
151  }
152  } else {
153  if (e->data() == 1) {
154  _nextBool = true;
155  _nextVal = -1;
156  _nextValTwin = -1;
157  }
158  }
159  }
160 
166  virtual void after_modify_edge (Halfedge_handle e) {
167  if (_nextBool) {
168  e->set_data(_nextVal);
169  e->twin()->set_data(_nextValTwin);
170  }
171  }
172 };
173 
174 #endif
virtual void after_modify_edge(Halfedge_handle e)
Definition: Arrangement.h:166
MyObserver(Arrangement &arr)
Definition: Arrangement.h:70
Definition: Arrangement.h:57
virtual void before_modify_edge(Halfedge_handle e, const X_monotone_curve_2 &s)
Definition: Arrangement.h:143
virtual void after_split_edge(Halfedge_handle e1, Halfedge_handle e2)
Definition: Arrangement.h:130
void setStarterEdge(bool b)
Definition: Arrangement.h:76
void setOriginalSeg(Segment seg)
Definition: Arrangement.h:82
virtual void before_split_edge(Halfedge_handle e, Vertex_handle v, const X_monotone_curve_2 &s1, const X_monotone_curve_2 &s2)
Definition: Arrangement.h:119
virtual void before_create_edge(const X_monotone_curve_2 &s, Vertex_handle v1, Vertex_handle v2)
Definition: Arrangement.h:88
virtual void after_create_edge(Halfedge_handle e)
Definition: Arrangement.h:104