CGAL users discussion list

[Jakob van Bethlehem <>]

Hello,

Following up on my question earlier today, I created patches the allow insertion of vertices with info into a Periodic_3_Delaunay_triangulation_3 from eg a vector of such vertices. I'm not sure what 
is the custom when posting patches, but I created a separate patch for both files involved: Periodic_3_triangulation_3.h and Periodic_3_Delaunay_triangulation_3.h. Also it is not purely a patch that 
adds the new functionality:

 * there was a minor issue in the normal insert(InputIterator, InputIterator) routine in Periodic_3_Delaunay_triangulation_3: points already inserted from the 'points' vector during an initial 
insertion were re-inserted during the insert_in_conflict() call.
 * the special 'is_large_point_set' value, IMHO, should also be present in 
the constructor, passing that value on to the call to insert()
 * the new functionality of inserting points with info: I followed the same 
procedure as in Delaunay_triangulation_3.h and didn't have to invent anything 
'new'.

Some other thoughts that came up while working on this:
 - Why is this 'insert-with-info' routine only defined in the Delaunay-classes? I wasn't able to find any reason why the exact same function wouldn't work in the respective parent classes 
Triangulation_3 and Periodic_3_triangulation_3
 - When the insert_with_info() routines get presented with the (unfortunate) situation that 'is_large_point_set==true', but the input set is actually small, it will result in a SegmentationFault 
somehow. I haven't been able to figure out why this happens, but it seems to me that this is not the wanted outcome :P I may have some time later to have a look at this, but since in my application 
this situation will not occur, unfortunately it will probably end up pretty low on my priority list.

Sincerely,
Jakob van Bethlehem




163a164
>       bool is_large_point_set = false,
167c168
<     insert(first, last);
---
>     insert(first, last, is_large_point_set);
184a186,194
> #ifndef CGAL_TRIANGULATION_3_DONT_INSERT_RANGE_OF_POINTS_WITH_INFO
>   template <class InputIterator>
>   std::ptrdiff_t
>   insert(InputIterator first, InputIterator last, bool is_large_point_set = 
> false,
>          typename boost::enable_if<
>            boost::is_base_of<Point, typename 
> std::iterator_traits<InputIterator>::value_type>
>          >::type * = 0
>          )
> #else
187c197,199
<       bool is_large_point_set = false) {
---
>       bool is_large_point_set = false)
> #endif
>   {
196a209
>     Vertex_handle new_vx;
202c215,216
<       insert(*pbegin);
---
>   new_vx = insert(*pbegin);
>   hint = new_vx->cell();
234c248,358
<   //@}
---
> #ifndef CGAL_TRIANGULATION_3_DONT_INSERT_RANGE_OF_POINTS_WITH_INFO
> private:
>   //top stands for tuple-or-pair
>   template <class Info>
>   const Point& top_get_first(const std::pair<Point,Info>& pair) const { 
> return pair.first; }
>   template <class Info>
>   const Info& top_get_second(const std::pair<Point,Info>& pair) const { 
> return pair.second; }
>   template <class Info>
>   const Point& top_get_first(const boost::tuple<Point,Info>& tuple) const { 
> return boost::get<0>(tuple); }
>   template <class Info>
>   const Info& top_get_second(const boost::tuple<Point,Info>& tuple) const { 
> return boost::get<1>(tuple); }
> 
>   template <class Tuple_or_pair, class InputIterator>
>   std::ptrdiff_t insert_with_info(InputIterator first, InputIterator last, 
> bool is_large_point_set)
>   {
>     if (first == last)  return 0;
>     size_type n = number_of_vertices();
>     // only apply special insertion for empty triangulations:
>     if (n > 0) is_large_point_set = false;
> 
>     typedef typename Triangulation_data_structure::Vertex::Info Info;
>     typedef typename std::vector<std::ptrdiff_t>::iterator Index_handle;
> 
>     std::vector<std::ptrdiff_t> indices;
>     std::vector<Point> points;
>     std::vector<Info> infos;
>     for (InputIterator it = first; it != last; ++it)
>     {
>       Tuple_or_pair value = *it;
>       indices.push_back(points.size());
>       points.push_back( top_get_first(value)  );
>       infos.push_back ( top_get_second(value) );
>     }
> 
>     std::random_shuffle(indices.begin(), indices.end());
>     Vertex_handle new_vx;
>     Cell_handle hint;
>     std::vector<Vertex_handle> dummy_points;
>     Index_handle idx_it = indices.begin(), idx_end = indices.end();
>     if (is_large_point_set)
>       dummy_points = insert_dummy_points();
>     else
>       while (!is_1_cover())
>       {
>         new_vx = insert(points[*idx_it]);
>         if (new_vx != Vertex_handle())
>         {
>           new_vx->info() = infos[*idx_it];
>           hint = new_vx->cell();
>         }
>         ++idx_it;
>         if (idx_it == idx_end) return number_of_vertices() - n; // all 
> points are already in
>       }
>     // if (is_large_point_set)
> 
>     // add remaining points //
>     typedef Spatial_sort_traits_adapter_3<Geom_traits, Point *> 
> Search_traits;
>     spatial_sort(idx_it, idx_end, Search_traits(&(points[0]), 
> geom_traits()));
> 
>     Conflict_tester tester(points[*idx_it], this);
>     Point_hider hider;
>     std::vector<Vertex_handle> double_vertices =
>         Base::insert_in_conflict_with_info(idx_it, idx_end, points, infos, 
> hint, tester, hider);
> 
>     if (is_large_point_set)
>     {
>       typedef CGAL::Periodic_3_triangulation_remove_traits_3< Gt > 
> P3removeT;
>       typedef CGAL::Delaunay_triangulation_3< P3removeT > DT;
>       typedef Vertex_remover< DT > Remover;
>       P3removeT remove_traits(domain());
>       DT dt(remove_traits);
>       Remover remover(this,dt);
>       Conflict_tester t(this);
>       for (unsigned int i=0; i<dummy_points.size(); i++)
>         if (std::find(double_vertices.begin(), double_vertices.end(),
>                       dummy_points[i]) == double_vertices.end())
>           Base::remove(dummy_points[i],remover,t);
>     }
> 
>     return number_of_vertices() - n;
>   }
> 
> public:
>   template<class InputIterator>
>   std::ptrdiff_t
>   insert(InputIterator first, InputIterator last, bool is_large_point_set = 
> false,
>          typename boost::enable_if<
>                         boost::is_same<typename 
> std::iterator_traits<InputIterator>::value_type,
>                                        std::pair<Point, typename 
> internal::Info_check<typename Triangulation_data_structure::Vertex>::type>
>                                       >
>                                   >::type* = 0)
>   {
>     return insert_with_info<std::pair<Point, typename 
> internal::Info_check<typename Triangulation_data_structure::Vertex>::type> 
> >(first, last, is_large_point_set);
>   }
> 
>   template <class  InputIterator_1,class InputIterator_2>
>   std::ptrdiff_t
>   insert( boost::zip_iterator< 
> boost::tuple<InputIterator_1,InputIterator_2> > first,
>           boost::zip_iterator< 
> boost::tuple<InputIterator_1,InputIterator_2> > last, bool 
> is_large_point_set = false,
>           typename boost::enable_if<
>             boost::mpl::and_<
>               boost::is_same< typename 
> std::iterator_traits<InputIterator_1>::value_type, Point >,
>               boost::is_same< typename 
> std::iterator_traits<InputIterator_2>::value_type, typename 
> internal::Info_check<typename Triangulation_data_structure::Vertex>::type >
>             >
>           >::type* = 0
>   )
>   {
>     return insert_with_info< boost::tuple<Point,typename 
> internal::Info_check<typename Triangulation_data_structure::Vertex>::type> 
> >(first, last, is_large_point_set);
>   }
> 
> #endif //CGAL_TRIANGULATION_3_DONT_INSERT_RANGE_OF_POINTS_WITH_INFO
235a360
>   // @}
868,872c868,874
<   template < class InputIterator, class Conflict_tester,
<       class Point_hider>
<   std::vector<Vertex_handle> insert_in_conflict(
<       InputIterator begin, InputIterator end, Cell_handle start,
<       Conflict_tester &tester, Point_hider &hider) {
---
>   template < class InputIterator, class Conflict_tester, class Point_hider>
>   std::vector<Vertex_handle>
>   insert_in_conflict(InputIterator begin, InputIterator end,
>                      Cell_handle start,
>                      Conflict_tester &tester,
>                      Point_hider &hider)
>   {
887,889c889,891
<       CGAL_triangulation_assertion(lta == lt);
<       CGAL_triangulation_assertion(ia == li);
<       CGAL_triangulation_assertion(ja == lj);
---
>       CGAL_triangulation_assertion(lta == lt);
>       CGAL_triangulation_assertion(ia == li);
>       CGAL_triangulation_assertion(ja == lj);
898a901,943
> 
> #ifndef CGAL_TRIANGULATION_3_DONT_INSERT_RANGE_OF_POINTS_WITH_INFO
>   template <class IndexIterator, class InfoType, class Conflict_tester, 
> class Point_hider>
>   std::vector<Vertex_handle>
>   insert_in_conflict_with_info(IndexIterator begin,
>                                IndexIterator end,
>                                std::vector<Point> const &points,
>                                std::vector<InfoType> const &info,
>                                Cell_handle start,
>                                Conflict_tester &tester, Point_hider &hider)
>   {
>     Vertex_handle new_vertex;
>     Cell_handle hint;
>     std::vector<Vertex_handle> double_vertices;
>     Locate_type lt = Locate_type();
>     int li=0, lj=0;
>     CGAL_triangulation_assertion_code( Locate_type lta = Locate_type(); )
>     CGAL_triangulation_assertion_code( int ia = 0; )
>     CGAL_triangulation_assertion_code( int ja = 0; )
>     while (begin != end)
>     {
>       tester.set_point(points[*begin]);
>       hint = periodic_locate(points[*begin], Offset(), lt, li, lj, start);
>       CGAL_triangulation_assertion_code( if (number_of_vertices() != 0) { );
>       CGAL_triangulation_assertion(
>             side_of_cell(points[*begin], Offset(), hint, lta, ia, ja) != 
> ON_UNBOUNDED_SIDE);
>       CGAL_triangulation_assertion(lta == lt);
>       CGAL_triangulation_assertion(ia == li);
>       CGAL_triangulation_assertion(ja == lj);
>       CGAL_triangulation_assertion_code( });
> 
>       new_vertex = insert_in_conflict(points[*begin], lt, hint, li, lj, 
> tester, hider);
>       if (lt == VERTEX) double_vertices.push_back(new_vertex);
>       else
>         if (new_vertex != Vertex_handle())
>           new_vertex->info() = info[*begin];
>       start = new_vertex->cell();
>       ++begin;
>     }
>     return double_vertices;
>   }
> 
> #endif