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
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
MyObserver::after_modify_edge
virtual void after_modify_edge(Halfedge_handle e)
Definition: Arrangement.h:166
MyObserver::MyObserver
MyObserver(Arrangement &arr)
Definition: Arrangement.h:70
MyObserver
Definition: Arrangement.h:57
MyObserver::before_modify_edge
virtual void before_modify_edge(Halfedge_handle e, const X_monotone_curve_2 &s)
Definition: Arrangement.h:143
MyObserver::after_split_edge
virtual void after_split_edge(Halfedge_handle e1, Halfedge_handle e2)
Definition: Arrangement.h:130
MyObserver::setStarterEdge
void setStarterEdge(bool b)
Definition: Arrangement.h:76
MyObserver::setOriginalSeg
void setOriginalSeg(Segment seg)
Definition: Arrangement.h:82
MyObserver::before_split_edge
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
MyObserver::before_create_edge
virtual void before_create_edge(const X_monotone_curve_2 &s, Vertex_handle v1, Vertex_handle v2)
Definition: Arrangement.h:88
MyObserver::after_create_edge
virtual void after_create_edge(Halfedge_handle e)
Definition: Arrangement.h:104