// Copyright (c) 2001 Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $Source: /CVSROOT/CGAL/Packages/Snap_rounding_2/include/CGAL/Snap_rounding_2.h,v $
// $Revision: 1.110 $
// $Name: $
//
// author(s) : Eli Packer <elip@post.tau.ac.il>
#ifndef CGAL_SNAP_ROUNDING_2_H
#define CGAL_SNAP_ROUNDING_2_H
#include <iostream>
#include <CGAL/basic.h>
#include <CGAL/enum.h>
#include <CGAL/predicates_on_points_2.h>
#include <CGAL/intersection_2.h>
#include <CGAL/Sweep_line_2.h>
#include <list>
#include <set>
#include <CGAL/Snap_rounding_kd_2.h>
#include <CGAL/utility.h>
#include <CGAL/Iterator_project.h>
#include <CGAL/function_objects.h>
CGAL_BEGIN_NAMESPACE
enum Direction {SEG_UP_RIGHT,SEG_UP_LEFT,SEG_DOWN_RIGHT,SEG_DOWN_LEFT,
SEG_UP,SEG_DOWN,SEG_LEFT,SEG_RIGHT,SEG_POINT_SEG};
template<class Traits_>
class Segment_data {
private:
typedef Traits_ Traits;
typedef typename Traits::FT NT;
typedef typename Traits::Segment_2 Segment_2;
typedef typename Traits::Point_2 Point_2;
private:
Point_2 p;
Point_2 q;
Traits m_gt;
public:
Segment_data();
Segment_data(const Point_2 & p_inp,const Point_2 & q_inp);
Segment_2 segment() const { return(Segment_2(p, q)); }
Point_2 source() const { return(p); }
Point_2 target() const { return(q); }
inline void set_data(const Point_2 & inp_p,const Point_2 & inp_q);
void determine_direction(Direction & seg_dir);
bool equal(const Segment_2 & s);
Segment_data(const Segment_data & other);
};
/*! */
template<class Traits_>
class Hot_pixel {
private:
typedef Traits_ Traits;
typedef typename Traits::FT NT;
typedef typename Traits::Segment_2 Segment_2;
typedef typename Traits::Point_2 Point_2;
typedef CGAL::Segment_data<Traits> Segment_data;
private:
// p is the center of the hot pixel
Point_2 p;
Point_2 p_left;
Point_2 p_right;
Point_2 p_down;
Point_2 p_up;
Traits_ m_gt;
NT pixel_size;
Segment_2 *right_seg;
Segment_2 *left_seg;
Segment_2 *top_seg;
Segment_2 *bot_seg;
static Direction seg_dir;
public:
Hot_pixel(const Point_2 & inp_point, NT inp_pixel_size);
~Hot_pixel();
inline Point_2 get_center() const;
inline Point_2 get_center(bool int_output) const;
bool intersect_left(const Segment_2 & seg, Direction seg_dir) const;
bool intersect_right(const Segment_2 & seg, Direction seg_dir) const;
bool intersect_bot(const Segment_2 & seg, Direction seg_dir) const;
bool intersect_top(const Segment_2 & seg, Direction seg_dir) const;
bool intersect(Segment_data & seg, Direction seg_dir) const;
void set_direction(Direction inp_seg_dir) { seg_dir = inp_seg_dir; }
Direction get_direction() const { return(seg_dir); }
};
/*! */
template<class Traits_> Direction Hot_pixel<Traits_>::seg_dir;
// a function for compare two hot pixels for the set of hot pixels
template<class Traits_>
struct Hot_pixel_auclidian_cmp {
typedef CGAL::Hot_pixel<Traits_> Hot_pixel;
Traits_ m_gt;
bool operator()(const Hot_pixel * h1, const Hot_pixel * h2) const;
};
// a function for compare two hot pixels for the set of hot pixels a
// certain segment intersect
template<class Traits_>
struct Hot_pixel_dir_cmp {
typedef CGAL::Hot_pixel<Traits_> Hot_pixel;
Traits_ m_gt;
bool operator()(const Hot_pixel * h1, const Hot_pixel * h2);
};
#ifdef CGAL_SR_DEBUG
int number_of_false_hp;
#endif
template<class Traits_,class OutputContainer>
class Snap_rounding_2 {
private:
typedef Traits_ Traits;
typedef typename Traits::FT NT;
typedef typename Traits::X_monotone_curve_2 X_monotone_curve_2;
typedef typename OutputContainer::value_type Polyline_type;
typedef CGAL::Hot_pixel<Traits_> Hot_pixel;
typedef CGAL::Segment_data<Traits> Segment_data;
typedef CGAL::Multiple_kd_tree<Traits,Hot_pixel *> Multiple_kd_tree;
typedef std::list<Segment_data> Segment_data_list;
typedef CGAL::Hot_pixel_dir_cmp<Traits> Hot_pixel_dir_cmp;
typedef std::set<Hot_pixel *, Hot_pixel_dir_cmp> Hot_pixel_set;
public:
// friend class Segment_data<Traits>;
// friend class Hot_pixel<Traits>;
// friend struct Hot_pixel_dir_cmp<Traits>;
typedef typename Traits::Segment_2 Segment_2;
typedef typename Traits::Point_2 Point_2;
typedef std::list<Point_2> Point_list;
void find_hot_pixels_and_create_kd_trees(NT pixel_size,
unsigned int number_of_kd_trees,
Segment_data_list & seg_list,
Multiple_kd_tree ** mul_kd_tree);
void iterate(OutputContainer & output_container,
NT pixel_size, bool int_output, bool do_isr,
Segment_data_list & seg_list,
Multiple_kd_tree * mul_kd_tree);
private:
Traits m_gt;
static const int default_number_of_kd_trees = 1;
void find_intersected_hot_pixels(Segment_data & seg,
Hot_pixel_set &hot_pixels_intersected_set,
int &number_of_intersections,
NT pixel_size,
Multiple_kd_tree * mul_kd_tree);
void reroute_sr(Hot_pixel_set & inp_hot_pixels_intersected_set,
Polyline_type & seg_output,
bool int_output);
void reroute_isr(Hot_pixel_set & inp_hot_pixels_intersected_set,
Polyline_type & seg_output,
int number_of_intersections,
bool first_time,
NT pixel_size,
bool int_output,
Multiple_kd_tree * mul_kd_tree);
};
/*! Constructor */
template<class Traits_>
Segment_data<Traits_>::Segment_data() {}
/*! Constructor */
template<class Traits_>
Segment_data<Traits_>::Segment_data(const Point_2 & p_inp,
const Point_2 & q_inp) :
p(p_inp), q(q_inp) {}
/*! Constructor */
template<class Traits_>
Segment_data<Traits_>::Segment_data(const Segment_data & other)
{
p = other.p;
q = other.q;
}
/*! */
template<class Traits_>
inline void Segment_data<Traits_>::set_data(const Point_2 & inp_p,
const Point_2 & inp_q)
{
p = inp_p;
q = inp_q;
}
/*! */
template<class Traits_>
bool Segment_data<Traits_>::equal(const Segment_2 & s)
{
typedef typename Traits_::Construct_vertex_2 Construct_vertex_2;
Construct_vertex_2 construct_vertex = m_gt.construct_vertex_2_object();
return(construct_vertex(s, 0) == p && construct_vertex(s, 1) == q);
}
/*! */
template<class Traits_>
void Segment_data<Traits_>::determine_direction(Direction & seg_dir)
{
typedef typename Traits_::Compare_y_2 Compare_y_2;
typedef typename Traits_::Compare_x_2 Compare_x_2;
Compare_x_2 compare_x = m_gt.compare_x_2_object();
Compare_y_2 compare_y = m_gt.compare_y_2_object();
Comparison_result cx = compare_x(p, q);
Comparison_result cy = compare_y(p, q);
if (cx == SMALLER) {
if (cy == SMALLER) seg_dir = SEG_UP_RIGHT;
else if (cy == EQUAL) seg_dir = SEG_RIGHT;
else seg_dir = SEG_DOWN_RIGHT;
} else if (cx == EQUAL) {
if (cy == SMALLER) seg_dir = SEG_UP;
else if (cy == EQUAL) seg_dir = SEG_POINT_SEG;
else seg_dir = SEG_DOWN;
} else {
if (cy == SMALLER) seg_dir = SEG_UP_LEFT;
else if (cy == EQUAL) seg_dir = SEG_LEFT;
else seg_dir = SEG_DOWN_LEFT;
}
}
// intersection pixel
template<class Traits_>
Hot_pixel<Traits_>::Hot_pixel(const Point_2 & inp_point, NT inp_pixel_size) :
pixel_size(inp_pixel_size)
{
NT x,y;
m_gt.snap_2_object()(inp_point, pixel_size, x, y);
NT left_coord = x - pixel_size / NT(2.0);
NT right_coord = x + pixel_size / NT(2.0);
NT bottom_coord = y - pixel_size / NT(2.0);
NT top_coord = y + pixel_size / NT(2.0);
p = Point_2(x, y);
p_left = Point_2(left_coord, y);
p_right = Point_2(right_coord, y);
p_down = Point_2(x, bottom_coord);
p_up = Point_2(x, top_coord);
typedef typename Traits::Construct_segment_2 Construct_segment_2;
Construct_segment_2 construct_seg = m_gt.construct_segment_2_object();
Point_2 lb(left_coord, bottom_coord);
Point_2 rb(right_coord, bottom_coord);
Point_2 lt(left_coord, top_coord);
Point_2 rt(right_coord, top_coord);
right_seg = new Segment_2(construct_seg(rb, rt));
left_seg = new Segment_2(construct_seg(lb, lt));
top_seg = new Segment_2(construct_seg(lt, rt));
bot_seg = new Segment_2(construct_seg(lb, rb));
}
/*! */
template<class Traits_>
Hot_pixel<Traits_>::~Hot_pixel()
{
delete(right_seg);
delete(left_seg);
delete(top_seg);
delete(bot_seg);
}
/*! */
template<class Traits_>
inline typename Hot_pixel<Traits_>::Point_2
Hot_pixel<Traits_>::get_center() const
{
return(p);
}
/*! */
template<class Traits_>
inline typename Hot_pixel<Traits_>::Point_2
Hot_pixel<Traits_>::get_center(bool int_output) const
{
if (int_output) {
Point_2 out_p = m_gt.integer_grid_point_2_object()(p,pixel_size);
return(out_p);
} else
return(p);
}
/*! */
template<class Traits_>
bool Hot_pixel<Traits_>::intersect_left(const Segment_2 & seg,
Direction seg_dir) const
{
typedef typename Traits_::Compare_y_2 Compare_y_2;
typedef typename Traits_::Construct_vertex_2 Construct_vertex_2;
Object result;
Point_2 p;
Segment_2 s;
result = intersection(seg, *left_seg);
if (assign(p, result)) {
Compare_y_2 compare_y = m_gt.compare_y_2_object();
Construct_vertex_2 construct_vertex = m_gt.construct_vertex_2_object();
Comparison_result c_p = compare_y(p, p_up);
Comparison_result c_target = compare_y(construct_vertex(seg, 1), p_up);
Comparison_result c_source = compare_y(construct_vertex(seg, 0), p_up);
return(c_p != EQUAL || seg_dir == SEG_UP_LEFT && c_source != EQUAL ||
seg_dir == SEG_DOWN_RIGHT && c_target != EQUAL);
} else if (assign(s,result))
return(true);
else
return(false);
}
/*! */
template<class Traits_>
bool Hot_pixel<Traits_>::intersect_right(const Segment_2 & seg,
Direction seg_dir) const
{
typedef typename Traits_::Compare_y_2 Compare_y_2;
typedef typename Traits_::Compare_x_2 Compare_x_2;
typedef typename Traits_::Construct_vertex_2 Construct_vertex_2;
Object result;
Point_2 p;
Segment_2 s;
result = intersection(seg, *right_seg);
if (assign(p,result)) {
// bottom right point was checked in intersect_bot
Compare_y_2 compare_y = m_gt.compare_y_2_object();
Construct_vertex_2 construct_vertex = m_gt.construct_vertex_2_object();
Comparison_result c1 = compare_y(p, p_up);
Comparison_result c2 = compare_y(p, p_down);
Point_2 src = construct_vertex(seg, 0);
Point_2 trg = construct_vertex(seg, 1);
Comparison_result c3 = compare_y(src, p_up);
Comparison_result c4 = compare_y(trg, p_up);
if (c1 == EQUAL)
return(seg_dir == SEG_UP_RIGHT && c3 != EQUAL ||
seg_dir == SEG_DOWN_LEFT && c4 != EQUAL);
else if (c2 == EQUAL)
return(false);// was checked
else {
Compare_x_2 compare_x = m_gt.compare_x_2_object();
Comparison_result c_target = compare_x(p_right, trg);
Comparison_result c_source = compare_x(p_right, src);
return((seg_dir == SEG_LEFT || seg_dir == SEG_DOWN_LEFT ||
seg_dir == SEG_UP_LEFT) && c_target != EQUAL ||
(seg_dir == SEG_RIGHT || seg_dir == SEG_DOWN_RIGHT ||
seg_dir == SEG_UP_RIGHT) && c_source != EQUAL);
}
} else
return(false);
}
/*! */
template<class Traits_>
bool Hot_pixel<Traits_>::intersect_bot(const Segment_2 & seg,
Direction seg_dir) const
{
typedef typename Traits_::Compare_x_2 Compare_x_2;
typedef typename Traits_::Construct_vertex_2 Construct_vertex_2;
Object result;
Point_2 p;
Segment_2 s;
result = intersection(seg,*bot_seg);
if (assign(p,result)) {
Compare_x_2 compare_x = m_gt.compare_x_2_object();
Construct_vertex_2 construct_vertex = m_gt.construct_vertex_2_object();
Comparison_result c_p = compare_x(p, p_right);
Comparison_result c_target = compare_x(construct_vertex(seg, 1), p_right);
Comparison_result c_source = compare_x(construct_vertex(seg, 0), p_right);
return(c_p != EQUAL || seg_dir == SEG_UP_LEFT &&
c_target != EQUAL || seg_dir == SEG_DOWN_RIGHT &&
c_source != EQUAL);
} else if (assign(s,result))
return(true);
else
return(false);
}
/*! */
template<class Traits_>
bool Hot_pixel<Traits_>::intersect_top(const Segment_2 & seg,
Direction seg_dir) const
{
typedef typename Traits_::Compare_x_2 Compare_x_2;
typedef typename Traits_::Compare_y_2 Compare_y_2;
typedef typename Traits_::Construct_vertex_2 Construct_vertex_2;
Object result;
Point_2 p;
Segment_2 s;
result = intersection(seg, *top_seg);
if (assign(p,result)) {
Compare_x_2 compare_x = m_gt.compare_x_2_object();
Compare_y_2 compare_y = m_gt.compare_y_2_object();
Construct_vertex_2 construct_vertex = m_gt.construct_vertex_2_object();
// corner points was checked in intersect_bot
Comparison_result c1 = compare_x(p, p_left);
Comparison_result c2 = compare_x(p, p_right);
Comparison_result c3 = compare_y(construct_vertex(seg, 1), p_up);
Comparison_result c4 = compare_y(construct_vertex(seg, 0), p_up);
if (c1 == EQUAL || c2 == EQUAL)
return(false);// were checked
else
return((seg_dir == SEG_DOWN || seg_dir == SEG_DOWN_LEFT ||
seg_dir == SEG_DOWN_RIGHT) && c3 != EQUAL ||
(seg_dir == SEG_UP || seg_dir == SEG_UP_LEFT ||
seg_dir == SEG_UP_RIGHT) && c4 != EQUAL);
} else
return(false);
}
/*! */
template<class Traits_>
bool
Hot_pixel<Traits_>::intersect(Segment_data & seg, Direction my_seg_dir) const
{
Segment_2 s = seg.segment();
return(intersect_bot(s,my_seg_dir) || intersect_left(s, my_seg_dir) ||
intersect_right(s, my_seg_dir) || intersect_top(s, my_seg_dir));
}
// a function for compare two hot pixels for the set of hot pixels
template<class Traits_>
bool Hot_pixel_auclidian_cmp<Traits_>::
operator()(const Hot_pixel * h1, const Hot_pixel * h2) const
{
typedef typename Traits_::Compare_x_2 Compare_x_2;
typedef typename Traits_::Compare_y_2 Compare_y_2;
Compare_x_2 compare_x = m_gt.compare_x_2_object();
Compare_y_2 compare_y = m_gt.compare_y_2_object();
Comparison_result cx = compare_x(h1.get_center(), h2.get_center());
Comparison_result cy = compare_y(h1.get_center(), h2.get_center());
return(cx == SMALLER || cx == EQUAL && cy == SMALLER);
}
// a function for compare two hot pixels for the set of hot pixels a certain
// segment intersect
template<class Traits_>
bool Hot_pixel_dir_cmp<Traits_>::operator ()(const Hot_pixel * h1,
const Hot_pixel * h2)
{
typedef typename Traits_::Compare_x_2 Compare_x_2;
typedef typename Traits_::Compare_y_2 Compare_y_2;
Compare_x_2 compare_x = m_gt.compare_x_2_object();
Compare_y_2 compare_y = m_gt.compare_y_2_object();
Comparison_result cx = compare_x(h1->get_center(), h2->get_center());
Comparison_result cy = compare_y(h1->get_center(), h2->get_center());
Direction seg_dir = h1->get_direction();
// Point segment intersects only one pixel, thus ignored
return(seg_dir == SEG_UP_RIGHT &&
(cx == SMALLER || cx == EQUAL &&
cy == SMALLER) || seg_dir == SEG_UP_LEFT &&
(cx == LARGER ||
cx == EQUAL && cy == SMALLER) || seg_dir == SEG_DOWN_RIGHT &&
(cx == SMALLER || cx == EQUAL && cy == LARGER) ||
seg_dir == SEG_DOWN_LEFT &&
(cx == LARGER || cx == EQUAL &&
cy == LARGER) || seg_dir == SEG_UP && cy == SMALLER ||
seg_dir == SEG_DOWN && cy == LARGER || seg_dir == SEG_LEFT &&
cx == LARGER || seg_dir == SEG_RIGHT && cx == SMALLER);
}
/*! */
template<class Traits,class OutputContainer>
void Snap_rounding_2<Traits,OutputContainer>::
find_hot_pixels_and_create_kd_trees(NT pixel_size,
unsigned int number_of_kd_trees,
std::list<Segment_data> & seg_list,
Multiple_kd_tree ** mul_kd_tree)
{
typedef std::pair<Point_2, Hot_pixel *> Point_hot_pixel_pair;
typedef typename std::list<Segment_data>::iterator Segment_data_iter;
typedef std::list<Segment_2> Segment_list;
typedef typename Segment_list::iterator Segment_iter;
typedef typename std::list<Point_2>::const_iterator Point_const_iter;
typedef typename Traits::Construct_segment_2 Construct_segment_2;
Construct_segment_2 construct_seg = m_gt.construct_segment_2_object();
Hot_pixel * hp;
Segment_data_iter iter1;
Object result;
Point_2 p;
std::list<Point_hot_pixel_pair> hot_pixels_list;
Segment_list segments;
if (seg_list.empty()) return;
for (iter1 = seg_list.begin(); iter1 != seg_list.end(); ++iter1) {
segments.push_back(construct_seg(iter1->source(), iter1->target()));
}
// get intersection points (with endpoints)
Point_list mypointlist;
Sweep_line_2<Segment_iter, Traits> sl;
sl.get_intersection_points(segments.begin(), segments.end(),
std::back_inserter(mypointlist));
for (Point_const_iter v_iter = mypointlist.begin();
v_iter != mypointlist.end(); ++v_iter)
{
hp = new Hot_pixel(*v_iter, pixel_size);
hot_pixels_list.push_back(Point_hot_pixel_pair(hp->get_center(), hp));
}
// create kd multiple tree
// create simple_list from seg_list
Segment_list simple_seg_list;
for (Segment_data_iter iter = seg_list.begin(); iter != seg_list.end();
++iter)
{
simple_seg_list.push_back(construct_seg(iter->source(), iter->target()));
}
*mul_kd_tree = new Multiple_kd_tree(hot_pixels_list, number_of_kd_trees,
simple_seg_list);
}
/*! */
template<class Traits_,class OutputContainer>
void Snap_rounding_2<Traits_,OutputContainer>::
find_intersected_hot_pixels(Segment_data & seg,
std::set<Hot_pixel *,
Hot_pixel_dir_cmp> & hot_pixels_intersected_set,
int &number_of_intersections,
NT pixel_size,
Multiple_kd_tree * mul_kd_tree)
{
typedef typename std::list<Hot_pixel *>::iterator Hot_pixel_iter;
Hot_pixel_iter iter;
Direction seg_dir;
hot_pixels_intersected_set.clear();
seg.determine_direction(seg_dir);
number_of_intersections = 0;
std::list<Hot_pixel *> hot_pixels_list;
mul_kd_tree->get_intersecting_points(hot_pixels_list,
Segment_2(seg.segment()), pixel_size);
for (iter = hot_pixels_list.begin();iter != hot_pixels_list.end();++iter) {
if ((*iter)->intersect(seg,seg_dir)) {
(*iter)->set_direction(seg_dir);
hot_pixels_intersected_set.insert(*iter);
}
#ifdef CGAL_SR_DEBUG
else
++number_of_false_hp;
#endif
}
number_of_intersections = hot_pixels_intersected_set.size();
}
/*! */
template<class Traits_,class OutputContainer>
void Snap_rounding_2<Traits_,OutputContainer>::
reroute_sr(std::set<Hot_pixel *, Hot_pixel_dir_cmp>
& inp_hot_pixels_intersected_set,
Polyline_type & seg_output,
bool int_output)
{
typedef typename std::set<Hot_pixel *, Hot_pixel_dir_cmp>::iterator
Hot_pixel_iter;
Hot_pixel_iter hot_pixel_iter = inp_hot_pixels_intersected_set.begin();
++hot_pixel_iter;
while (hot_pixel_iter != inp_hot_pixels_intersected_set.end()) {
seg_output.push_back((*hot_pixel_iter)->get_center(int_output));
++hot_pixel_iter;
}
}
/*! */
template<class Traits_,class OutputContainer>
void Snap_rounding_2<Traits_,OutputContainer>::
reroute_isr(std::set<Hot_pixel *, Hot_pixel_dir_cmp>
& inp_hot_pixels_intersected_set,
Polyline_type & seg_output,
int number_of_intersections,
bool first_time,
NT pixel_size,
bool int_output,
Multiple_kd_tree * mul_kd_tree)
{
typedef std::set<Hot_pixel *, Hot_pixel_dir_cmp> Hot_pixel_set;
typedef typename std::set<Hot_pixel *, Hot_pixel_dir_cmp>::iterator
Hot_pixel_iter;
Hot_pixel_iter hot_pixel_iter, next_hot_pixel_iter,
before_last_hot_pixel_iter;
Segment_data seg;
Hot_pixel_set hot_pixels_intersected_set;
Direction seg_dir;
if (number_of_intersections > 2 || first_time) {
before_last_hot_pixel_iter = inp_hot_pixels_intersected_set.end();
--before_last_hot_pixel_iter;
for (hot_pixel_iter = inp_hot_pixels_intersected_set.begin();
hot_pixel_iter != before_last_hot_pixel_iter; ++hot_pixel_iter)
{
next_hot_pixel_iter = hot_pixel_iter;
++next_hot_pixel_iter;
seg.set_data((*hot_pixel_iter)->get_center(),
(*next_hot_pixel_iter)->get_center());
seg.determine_direction(seg_dir);
find_intersected_hot_pixels(seg, hot_pixels_intersected_set,
number_of_intersections, pixel_size,
mul_kd_tree);
reroute_isr(hot_pixels_intersected_set, seg_output,
number_of_intersections,false, pixel_size,
int_output, mul_kd_tree);
}
} else {
// insert second hot pixel
hot_pixel_iter = inp_hot_pixels_intersected_set.begin();
++hot_pixel_iter;
seg_output.push_back((*hot_pixel_iter)->get_center(int_output));
}
}
/*! */
template<class Traits_, class OutputContainer>
void Snap_rounding_2<Traits_,OutputContainer>::
iterate(OutputContainer & output_container,
NT pixel_size,
bool int_output, bool do_isr,
std::list<Segment_data> & seg_list,
Multiple_kd_tree * mul_kd_tree)
{
typedef std::set<Hot_pixel *, Hot_pixel_dir_cmp> Hot_pixel_set;
typedef typename std::set<Hot_pixel *, Hot_pixel_dir_cmp>::iterator
Hot_pixel_iter;
typedef typename std::list<Segment_data>::iterator Segment_data_iter;
Polyline_type seg_output;
Hot_pixel_set hot_pixels_intersected_set;
Hot_pixel_iter hot_pixel_iter;
int number_of_intersections;
Hot_pixel * hp;
Direction seg_dir;
for (Segment_data_iter iter = seg_list.begin(); iter != seg_list.end();
++iter)
{
seg_output.clear();
iter->determine_direction(seg_dir);
find_intersected_hot_pixels(*iter, hot_pixels_intersected_set,
number_of_intersections, pixel_size,
mul_kd_tree);
// hot_pixels_intersected_set must have at least two hot pixels when the
// segment is not in entirely inside a hot pixel enter first hot pixel
hot_pixel_iter = hot_pixels_intersected_set.begin();
if (hot_pixel_iter == hot_pixels_intersected_set.end()) {
// segment entirely inside a pixel
hp = new Hot_pixel(iter->source(), pixel_size);
seg_output.push_back(hp->get_center(int_output));
delete(hp);
} else {
seg_output.push_back((*hot_pixel_iter)->get_center(int_output));
if (number_of_intersections > 1) {
// segments that have at most one intersecting hot pixel are
// done(it was inserted)
if (do_isr)
reroute_isr(hot_pixels_intersected_set, seg_output,
number_of_intersections, true,pixel_size,
int_output, mul_kd_tree);
else
reroute_sr(hot_pixels_intersected_set, seg_output, int_output);
}
}
output_container.push_back(seg_output);
}
}
/*! */
template<class Traits, class InputIterator, class OutputContainer>
void snap_rounding_2(InputIterator begin,
InputIterator end,
OutputContainer & output_container,
typename Traits::FT pixel_size,
bool do_isr = true,
bool int_output = true,
unsigned int number_of_kd_trees = 1)
{
#ifdef CGAL_SR_DEBUG
number_of_false_hp = 0;
#endif
typedef CGAL::Hot_pixel<Traits> Hot_pixel;
typedef CGAL::Segment_data<Traits> Segment_data;
typedef CGAL::Multiple_kd_tree<Traits,Hot_pixel *> Multiple_kd_tree;
typedef std::list<Segment_data> Segment_data_list;
Segment_data_list seg_list;
Multiple_kd_tree * mul_kd_tree;
output_container.clear();
// copy segments list
while (begin != end) {
seg_list.push_back(Segment_data(begin->source(), begin->target()));
++begin;
}
Snap_rounding_2<Traits,OutputContainer> s;
s.find_hot_pixels_and_create_kd_trees(pixel_size, number_of_kd_trees,
seg_list, &mul_kd_tree);
s.iterate(output_container, pixel_size, int_output, do_isr,seg_list,
mul_kd_tree);
#ifdef CGAL_SR_DEBUG
std::cout << "Overall number of false hot pixels in all the queries : "
<< number_of_false_hp << std::endl;
#endif
}
CGAL_END_NAMESPACE
#endif
syntax highlighted by Code2HTML, v. 0.9.1