CGAL users discussion list

[Andreas Fabri <>]

Hello,

I wrapped the snaprounding code in a header file.
The API is rather adhoc. You pass the sequence
of segments, and get a sequence of segments back,
snapped at the precision given by a fraction.

Note that not only points close to other segments
get changed, but even segment endpoints far from
anything.  It should be doable to filter those out.

Best,

Andreas


On 27/08/2014 15:17, Andreas Fabri wrote:
> Hello,
>
> I just have a look at your data.
> You have two slanted rectangles that have an almost overlapping edge.
> Even if this works with an exact number type, it would make
> no sense to run the Delaunay conforming algorithm with these
> close segments, as the algorithm would produce many many triangles
> between the close segments.
>
> I am looking if the nap rounding package is the solution
> for this problem. The idea is to snap segment endpoints
> which are almost on another segment to the segment.
> This also avoids the case that you have a segment that
> intersects another segment, and gets split in two segments
> with one of them having length almost zero.
>
> Best,
>
> Andreas
>
> On 27/08/2014 15:09, HuyLe wrote:
> > I have isolated further the issue, my guess is that two constraints
> > (#56 and
> > 69 in the attachment conforming.cpp
> > <http://cgal-discuss.949826.n4.nabble.com/file/n4659749/conforming.cpp>
> > )
> > overlap each other, or are very close. In the example there are many
> > constraints that overlap which doesn't cause issue. Is there a way to
> > configure the algorithm to take care of such situation?
> >
> >
> >
> > --
> > View this message in context:
> > http://cgal-discuss.949826.n4.nabble.com/assert-in-refine-edges-h-tp4659748p4659749.html
> >
> > Sent from the cgal-discuss mailing list archive at Nabble.com.

--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_conformer_2.h>
#include <CGAL/snap_segments.h>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;
typedef CGAL::Constrained_Delaunay_triangulation_2<K> CDT;

typedef CDT::Vertex_handle Vertex_handle;


int main()
{
   CDT cdt;
   Point_2
      v0(0.0000000000000000, 6.0000000000000000),
      v1(0.0000000000000000, 0.0000000000000000),
      v2(1.0000000000000000, 0.0000000000000000),
      v3(1.0000000000000000, 6.0000000000000000),
      v4(16.0000000000000000, 16.0000000000000000),
      v5(11.0000000000000000, 16.0000000000000000),
      v6(11.0000000000000000, 15.0000000000000000),
      v7(14.0000000000000000, 15.0000000000000000),
      v8(15.0000000000000000, 15.0000000000000000),
      v9(15.0000000000000000, 5.0000000000000000),
      v10(13.0000000000000000, 5.0000000000000000),
      v11(9.0000000000000000, 5.0000000000000000),
      v12(9.0000000000000000, 0.0000000000000000),
      v13(16.0000000000000000, 0.0000000000000000),
      v14(1.0000000000000000, 16.0000000000000000),
      v15(1.0000000000000000, 14.0000000000000000),
      v16(0.0000000000000000, 14.0000000000000000),
      v17(0.0000000000000000, 13.0000000000000000),
      v18(3.0000000000000000, 13.0000000000000000),
      v19(6.0000000000000000, 13.0000000000000000),
      v20(6.0000000000000000, 16.0000000000000000),
      v21(7.0000000000000000, 8.0000000000000000),
      v22(7.0000000000000000, 7.0000000000000000),
      v23(4.0000000000000000, 7.0000000000000000),
      v24(4.0000000000000000, 6.0000000000000000),
      v25(8.0000000000000000, 6.0000000000000000),
      v26(8.0000000000000000, 8.0000000000000000),
      v27(14.0000000000000000, 6.0000000000000000),
      v28(13.0000000000000000, 6.0000000000000000),
      v29(7.0000000000000000, 15.0000000000000000),

      v30(7.0000000000000000, 13.0000000000000000),
      v31(8.0000000000000000, 13.0000000000000000),
      v32(8.0000000000000000, 15.0000000000000000),
      v33(8.0000000000000000, 5.0000000000000000),
      v34(8.0000000000000000, 0.0000000000000000),
      v35(0.0000000000000000, 12.0000000000000000),
      v36(3.0000000000000000, 12.0000000000000000),
      v37(2.0000000000000000, 0.0000000000000000),
      v38(2.0000000000000000, 6.0000000000000000),
      v39(0.0000000000000000, 16.0000000000000000),
     
     v40(8.8541629266471915, 13.0245767861329420),
     v41(8.3066572660502267, 12.9328699466773390),
     v42(8.6502551399969541, 10.9449291613017810),
     v43(9.1977608005939171, 11.0366360007573830),
     v44(2.5417150003569482, 11.6628607681877820),
     v45(0.3533522663593087, 11.0838445121955010),
     v46(1.4481046175850272, 7.0741569900028498),
     v47(3.6364673515826667, 7.6531732459951307),
     v48(5.1624802263187526, 11.8863167127519760),
     v49(2.9741174923211133, 11.3073004567596950),

     v50(4.0688698435468318, 7.2976129345670433),
     v51(6.2572325775444710, 7.8766291905593242),
      v52(12.5267359689079070, 13.8900007338527500),
      v53(8.8121230085508877, 13.2678054965947820),
      v54(9.9822767510084347, 6.4976927392851493),
     v55(13.6968897113654540, 7.1198879765431151),
     v56(9.0000000000000000, 8.0000000000000000),
     v57(9.0000000000000000, 6.0000000000000000),
     v58(16.1600000000000000, 16.1600000000000000),
      v59(-0.1600000000000000, 16.1600000000000000),
     v60(-0.1600000000000000, -0.1600000000000000),
     v61(16.1600000000000000, -0.1600000000000000);

   
  std::list<Segment_2> segments, snapped;
   segments.push_back(Segment_2(v60, v61));

   segments.push_back(Segment_2(v59, v60));
   segments.push_back(Segment_2(v61, v58));
  segments.push_back(Segment_2(v58, v59));
   segments.push_back(Segment_2(v57, v56));
   segments.push_back(Segment_2(v54, v55));

   segments.push_back(Segment_2(v53, v54));


   segments.push_back(Segment_2(v55, v52));
   segments.push_back(Segment_2(v52, v53));
   segments.push_back(Segment_2(v50, v51));
   segments.push_back(Segment_2(v49, v50));

   segments.push_back(Segment_2(v51, v48));
   segments.push_back(Segment_2(v48, v49));
   segments.push_back(Segment_2(v46, v47));

   segments.push_back(Segment_2(v45, v46));
   segments.push_back(Segment_2(v47, v44));
   segments.push_back(Segment_2(v44, v45));

   segments.push_back(Segment_2(v42, v43));
   segments.push_back(Segment_2(v41, v42));
   segments.push_back(Segment_2(v43, v40));
   segments.push_back(Segment_2(v40, v41));

   segments.push_back(Segment_2(v38, v37));
   segments.push_back(Segment_2(v35, v36));
   segments.push_back(Segment_2(v37, v34));
   segments.push_back(Segment_2(v34, v33));
   segments.push_back(Segment_2(v32, v31));

   segments.push_back(Segment_2(v30, v31));
   segments.push_back(Segment_2(v32, v29));
   segments.push_back(Segment_2(v29, v30));
   segments.push_back(Segment_2(v57, v28));
   segments.push_back(Segment_2(v28, v27));
   segments.push_back(Segment_2(v26, v56));
   segments.push_back(Segment_2(v26, v31));
   segments.push_back(Segment_2(v33, v25));
   segments.push_back(Segment_2(v26, v25));
   segments.push_back(Segment_2(v25, v24));
   segments.push_back(Segment_2(v23, v24));
   segments.push_back(Segment_2(v22, v23));
   segments.push_back(Segment_2(v21, v30));
   segments.push_back(Segment_2(v26, v21));

   segments.push_back(Segment_2(v21, v22));
   segments.push_back(Segment_2(v19, v30));
   segments.push_back(Segment_2(v19, v20));
   segments.push_back(Segment_2(v36, v18));
   segments.push_back(Segment_2(v18, v19));
   segments.push_back(Segment_2(v17, v35));
   segments.push_back(Segment_2(v17, v18));
   segments.push_back(Segment_2(v39, v16));
   segments.push_back(Segment_2(v16, v17));

   segments.push_back(Segment_2(v15, v16));
   segments.push_back(Segment_2(v14, v39));
   segments.push_back(Segment_2(v20, v14));
   segments.push_back(Segment_2(v14, v15));
   segments.push_back(Segment_2(v34, v12));
   segments.push_back(Segment_2(v12, v13));
   segments.push_back(Segment_2(v11, v33));
   segments.push_back(Segment_2(v12, v11));
   segments.push_back(Segment_2(v10, v28));
   segments.push_back(Segment_2(v10, v11));

   segments.push_back(Segment_2(v9, v10));
   segments.push_back(Segment_2(v8, v9));
   segments.push_back(Segment_2(v27, v7));
   segments.push_back(Segment_2(v7, v8));
   segments.push_back(Segment_2(v6, v32));
   segments.push_back(Segment_2(v6, v7));
   segments.push_back(Segment_2(v5, v20));
   segments.push_back(Segment_2(v5, v6));
   segments.push_back(Segment_2(v13, v4));

   segments.push_back(Segment_2(v4, v5));
   segments.push_back(Segment_2(v38, v3));
   segments.push_back(Segment_2(v2, v37));
   segments.push_back(Segment_2(v2, v3));
   segments.push_back(Segment_2(v1, v2));
   segments.push_back(Segment_2(v35, v0));
   segments.push_back(Segment_2(v3, v0));
   segments.push_back(Segment_2(v0, v1));
   
  snap_segments(segments.begin(), segments.end(), 
std::back_inserter(snapped), 1, 10000);

  std::cout.precision(17);


  for (std::list<Segment_2>::iterator iter = snapped.begin(); iter != 
snapped.end(); ++iter) {
    cdt.insert_constraint(iter->source(), iter->target());
  }

   std::cout << "Number of vertices before: "
      << cdt.number_of_vertices() << std::endl;
   // make it conforming Delaunay
   CGAL::make_conforming_Delaunay_2(cdt);
   std::cout << "Number of vertices after make_conforming_Delaunay_2: "
      << cdt.number_of_vertices() << std::endl;
   // then make it conforming Gabriel
   CGAL::make_conforming_Gabriel_2(cdt);
   std::cout << "Number of vertices after make_conforming_Gabriel_2: "
      << cdt.number_of_vertices() << std::endl;
}

#ifndef CGAL_SNAP_SEGMENTS_H
#define CGAL_SNAP_SEGMENTS_H

#include <CGAL/Cartesian.h>
#include <CGAL/Gmpq.h>
#include <CGAL/Snap_rounding_traits_2.h>
#include <CGAL/Snap_rounding_2.h>


template <typename InputIterator, typename OutputIterator>
OutputIterator
snap_segments(InputIterator b, InputIterator e, OutputIterator out, int 
pixel_num, int pixel_denum)
{
  typedef CGAL::Gmpq Gmpq;
  typedef CGAL::Cartesian<Gmpq>             Kernel;
  typedef CGAL::Snap_rounding_traits_2<Kernel>     Traits;
  typedef Kernel::Segment_2                        Segment_2;
  typedef Kernel::Point_2                          Point_2;
  typedef std::list<Segment_2>                     Segment_list_2;
  typedef std::list<Point_2>                       Polyline_2;
  typedef std::list<Polyline_2>                    Polyline_list_2;

  Gmpq w(pixel_num,pixel_denum), w2(pixel_num,2*pixel_denum);
  Segment_list_2 seg_list;
  typedef typename std::iterator_traits<InputIterator>::value_type 
InputSegment_2;
  typedef typename CGAL::Kernel_traits<InputSegment_2>::Kernel::Point_2 
InputPoint_2;
  for(; b!= e; ++b){
    seg_list.push_back(Segment_2(Point_2(Gmpq(b->source().x()-w2), 
Gmpq(b->source().y()-w2)),
                                 Point_2(Gmpq(b->target().x()-w2), 
Gmpq(b->target().y()-w2))));
  } 
  Polyline_list_2 output_list;
  CGAL::snap_rounding_2<Traits,typename 
Segment_list_2::const_iterator,Polyline_list_2>
    (seg_list.begin(), seg_list.end(), output_list, w, true, false, 5);

  typename Polyline_list_2::const_iterator iter1;
  for (iter1 = output_list.begin(); iter1 != output_list.end(); ++iter1) {

    typename Polyline_2::const_iterator iter2 = iter1->begin();
    Point_2 p = *iter2;
    InputPoint_2 ip(CGAL::to_double(p.x()+w2), CGAL::to_double(p.y()+w2));
    ++iter2;
    for (; iter2 != iter1->end(); ++iter2){
      Point_2 q = *iter2;
      InputPoint_2 iq(CGAL::to_double(q.x()+w2), CGAL::to_double(q.y()+w2));
      *out++ = InputSegment_2(ip,iq);
      ip = iq;
    }
  }
  return out;
}


#endif