#ifndef CGAL_CONVEX_EXPANSION_VISIBILITY_2_H
#define CGAL_CONVEX_EXPANSION_VISIBILITY_2_H
#include <CGAL/license/Visibility_2.h>
#include <boost/shared_ptr.hpp>
#include <CGAL/boost/iterator/transform_iterator.hpp>
#include <CGAL/Arr_observer.h>
#include <CGAL/assertions.h>
#include <cassert>
#include <CGAL/use.h>
#include <vector>
#include <list>
#include <CGAL/Polygon_2.h>
#include <CGAL/Partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
namespace CGAL {
template<class Arrangement_2_, class RegularizationCategory = CGAL::Tag_true >
class Convex_expansion_visibility_2 {
typedef typename Arrangement_2_::Geometry_traits_2 Geometry_traits_2;
typedef typename Geometry_traits_2::Kernel K;
typedef Convex_expansion_visibility_2<
Arrangement_2_, RegularizationCategory> Self;
public:
typedef Arrangement_2_ Arrangement_2;
typedef typename Arrangement_2::Traits_2 Traits_2;
typedef typename Arrangement_2::Halfedge Halfedge;
typedef typename Arrangement_2::Halfedge_const_handle Halfedge_const_handle;
typedef typename Arrangement_2::Halfedge_handle Halfedge_handle;
typedef typename Arrangement_2::Edge_const_iterator Edge_const_iterator;
typedef typename Arrangement_2::Ccb_halfedge_const_circulator
Ccb_halfedge_const_circulator;
typedef typename Arrangement_2::Ccb_halfedge_circulator
Ccb_halfedge_circulator;
typedef typename Arrangement_2::Face_const_handle Face_const_handle;
typedef typename Arrangement_2::Face_handle Face_handle;
typedef typename Arrangement_2::Vertex_const_handle Vertex_const_handle;
typedef typename Arrangement_2::Vertex_handle Vertex_handle;
typedef typename K::Point_2 Point_2;
typedef typename Geometry_traits_2::Ray_2 Ray_2;
typedef typename Geometry_traits_2::Segment_2 Segment_2;
typedef typename Geometry_traits_2::Line_2 Line_2;
typedef typename Geometry_traits_2::Vector_2 Vector_2;
typedef typename Geometry_traits_2::Direction_2 Direction_2;
typedef typename Geometry_traits_2::FT Number_type;
typedef typename Geometry_traits_2::Object_2 Object_2;
typedef RegularizationCategory Regularization_category;
typedef CGAL::Tag_true Supports_general_polygon_category;
typedef CGAL::Tag_true Supports_simple_polygon_category;
private:
// Observer to track any changes of the attached arrangement.
class Observer : public Arr_observer<Arrangement_2>
{
typedef Arr_observer<Arrangement_2> Base;
typedef Observer Self;
public:
bool has_changed;
Observer() : Base(), has_changed(false)
{}
Observer(const Arrangement_2& arr)
: Base(const_cast<Arrangement_2&>(arr)), has_changed(false)
{}
// Arr_observer interface
void after_attach() { has_changed = false; }
void after_global_change() { has_changed = true; }
void after_create_vertex(Vertex_handle) { has_changed = true; }
void after_create_boundary_vertex(Vertex_handle) { has_changed = true; }
void after_create_edge(Halfedge_handle) { has_changed = true; }
void after_modify_vertex(Vertex_handle) { has_changed = true; }
void after_modify_edge(Halfedge_handle) { has_changed = true; }
void after_split_edge(Halfedge_handle, Halfedge_handle) {
has_changed = true;
}
void after_split_fictitious_edge(Halfedge_handle, Halfedge_handle) {
has_changed = true;
}
void after_split_face(Face_handle, Face_handle, bool) {
has_changed = true;
}
void after_split_outer_ccb(Face_handle, Ccb_halfedge_circulator,
Ccb_halfedge_circulator) {
has_changed = true;
}
void after_split_inner_ccb(Face_handle, Ccb_halfedge_circulator,
Ccb_halfedge_circulator) {
has_changed = true;
}
void after_add_outer_ccb(Ccb_halfedge_circulator) { has_changed = true; }
void after_add_inner_ccb(Ccb_halfedge_circulator) { has_changed = true; }
void after_add_isolated_vertex(Vertex_handle) { has_changed = true; }
void after_merge_edge(Halfedge_handle) { has_changed = true; }
void after_merge_fictitious_edge(Halfedge_handle) { has_changed = true; }
void after_merge_face(Face_handle) { has_changed = true; }
void after_merge_outer_ccb(Face_handle, Ccb_halfedge_circulator) {
has_changed = true;
}
void after_merge_inner_ccb(Face_handle, Ccb_halfedge_circulator) {
has_changed = true;
}
void after_move_outer_ccb(Ccb_halfedge_circulator) { has_changed = true; }
void after_move_inner_ccb(Ccb_halfedge_circulator) { has_changed = true; }
void after_move_isolated_vertex(Vertex_handle) { has_changed = true; }
void after_remove_vertex() { has_changed = true; }
void after_remove_edge() { has_changed = true; }
void after_remove_outer_ccb(Face_handle) { has_changed = true; }
void after_remove_inner_ccb(Face_handle) { has_changed = true; }
};
private:
const Arrangement_2* p_arr;
// May change during visibility computation
mutable Observer observer;
// mutable boost::shared_ptr<CDT> p_cdt;
mutable std::vector<Segment_2> needles;
// Copy constructor and assignment not supported
Convex_expansion_visibility_2(const Self&);
Self& operator= (const Self&);
public:
Arrangement_2 convex_partition;
Convex_expansion_visibility_2() : p_arr(NULL) {}
/*! Constructor given an arrangement. */
Convex_expansion_visibility_2(const Arrangement_2& arr)
: p_arr(&arr), observer(arr)
{
init_partition();
}
//const std::string name() const { return std::string("T_visibility_2"); }
bool is_attached() const {
return (p_arr != NULL);
}
void attach(const Arrangement_2& arr) {
if (p_arr != &arr) {
p_arr = &arr;
observer.detach();
observer.attach(const_cast<Arrangement_2&>(arr));
init_partition();
}
//std::cout << "attach done" << std::endl;
}
void detach() {
//std::cout << "detach" << std::endl;
observer.detach();
p_arr = NULL;
convex_partition.clear();
}
const Arrangement_2& arrangement_2() const {
return *p_arr;
}
template <typename VARR>
typename VARR::Face_handle
compute_visibility(const std::vector<Point_2>& q,
VARR& out_arr)
const {
if (observer.has_changed) {
//recompute convex decomposition
init_partition();
}
out_arr.clear();
needles.clear();
std::vector<Point_2> raw_output;
return output(raw_output, out_arr);
}
private:
template <typename VARR>
typename VARR::Face_handle
output(std::vector<Point_2>& raw_output, VARR& out_arr) const {
if (!needles.empty()) {
std::vector<Segment_2> segments(needles.begin(), needles.end());
for (unsigned int i = 0; i < raw_output.size(); i++) {
// //std::cout << raw_output[i] << " -- "
// << raw_output[(i+1)%raw_output.size()] << std::endl;
segments.push_back(Segment_2(raw_output[i],
raw_output[(i + 1) % raw_output.size()]));
}
CGAL::insert_non_intersecting_curves(out_arr,
segments.begin(),
segments.end());
}
else {
typename VARR::Vertex_handle v_last, v_first;
v_last = v_first =
out_arr.insert_in_face_interior(raw_output[0], out_arr.unbounded_face());
for (unsigned int i = 0; i < raw_output.size() - 1; i++) {
// std::cout << raw_output[i] << " -- "
// << raw_output[(i+1)%raw_output.size()] << std::endl;
if (raw_output[i] < raw_output[(i + 1)]) {
v_last = out_arr.insert_from_left_vertex(
Segment_2(raw_output[i], raw_output[i + 1]), v_last
)->target();
}
else {
v_last = out_arr.insert_from_right_vertex(
Segment_2(raw_output[i], raw_output[i + 1]), v_last
)->target();
}
}
out_arr.insert_at_vertices(
Segment_2(raw_output.front(), raw_output.back()),
v_last, v_first
);
}
CGAL_assertion(out_arr.number_of_faces() == 2);
if (out_arr.faces_begin()->is_unbounded())
return ++out_arr.faces_begin();
else
return out_arr.faces_begin();
}
void init_partition() {
std::list<CGAL::Polygon_2<K>> partition_polys;
std::vector<Point_2> vertices;
//Construct vertex list
auto eit = p_arr->unbounded_face()->inner_ccbs_begin();
do {
vertices.push_back((*eit)->source()->point());
} while (++eit != p_arr->unbounded_face()->inner_ccbs_begin());
//Create the partition
CGAL::optimal_convex_partition_2(vertices.begin(),
vertices.end(),
std::back_inserter(partition_polys));
//Verify the partition
assert(CGAL::partition_is_valid_2(vertices.begin(),
vertices.end(),
partition_polys.begin(),
partition_polys.end()));
std::vector<Segment_2> segments;
for (auto it = partition_polys.begin(); it != partition_polys.end(); it++) {
for (auto eit = (*it).edges_begin(); eit != (*it).edges_end(); eit++) {
insert(convex_partition, Segment_2(eit->source(), eit->target()));
}
}
}
};
} // namespace CGAL
#endif // CGAL_TRIANGULAR_EXPANSION_VISIBILITY_2_H
