CGAL users discussion list

[Ben Supnik <>]

Right - in my case I think it was just numerical coincidence...basically 
with my compiler options wrong and the rounding math un-trustworth, it 
was just dumb luck which segments were brought together by sweep-line 
that might produce bogus results.

If I understand correctly, the merge should be "simplified" (that is, 
unneeded edges removed) after any sweep...whether a recursive sweep or a 
one-at-a-time.  So the actual set of intersections computed could be 
different with the two use cases, making it possible to "dodge" a 
rounding-error induced bug.

I mention this because I have thrown a huge amount of lousy data at the 
arrangement/sweep line algs and they are really stable...but if the 
underlying code is wrong due to compiler options, they will function 
part of the time - they won't blow up consistently.

cheers
Ben


 wrote:
> Yes, as Ben pointed out, the computation is different. The function that 
> you are using (S.intersection) applies a recursive procedure until the 
> no. of polygons reduces below a certain threshold. Then,  it performs a 
> sweep-line procedure. When you provide a polygon at a time, I think that 
> the sweep-line procedure is immediately invoked. Anyhow, thanks for the 
> info. We'll take it in account when we look into it.
>
> Quoting "Ben Supnik" 
> <>:
>
> > Hi Hichem,
> >
> > The order of computation is different - the first (failing) case is I 
> > think more efficient because the code can use a merge-sort-like sequence.
> >
> > You say that your polygons "seem" to be correct...did you use the CGAL 
> > tests for self-intersection, etc. or a different unrelated set of code 
> > to check the input data?
> >
> > Also, I'm not sure what the MSVC version of -frounding-math is...if 
> > the low level rounding in CGAL is incorrect, polygon ops can become 
> > intermittently unreliable...I saw that when I had compiler options 
> > wrong, and the symptoms were similar.
> >
> > cheers
> > Ben
> >
> > BBB HHH wrote:
> > > Hello,
> > >
> > > I tried to compute the intersection of the polygons by inserting each 
> > > polygon apart like this:
> > >
> > > std::vector<Polygon_2>        polygons;
> > > // Fill the list of polygons
> > > Initialize the polygon set with a polygon
> > > Polygon_set_2 S(first_polygon);
> > > // Instead of S.intersection(polygons.begin(), polygons.end());
> > > for (int i = 0; i != polygons.size(); ++i)
> > > {
> > >    S.intersection(polygons[i];
> > > }
> > >
> > > This variation of source code is working fine for the polygons I 
> > > attached to the previous e-mail. I do not know what is the difference 
> > > (perhaps in runtime or storage) between the first source code (which 
> > > didn't work) and the second one?
> > >
> > > Thanks
> > > Hichem
> > >
> > > ------------------------------------------------------------------------
> > > *De :* BBB HHH 
> > > <>
> > > *À :* 
> > >
> > > *Envoyé le :* Samedi, 26 Septembre 2009, 18h25mn 19s
> > > *Objet :* Re : [cgal-discuss] An error when trying to compute 
> > > intersection of polygons
> > >
> > > Hello,
> > >
> > > Attached to this e-mail, you can find the .dat files storing the 
> > > polygns i am working with (file first_polygon.dat and files 
> > > polygon_00.dat to polygon_15.dat). I also attached .off files storing 
> > > the same polygons so you can visualize them.
> > >
> > > Thanks
> > > Hichem
> > >
> > > ------------------------------------------------------------------------
> > > *De :* 
> > > ""
> > >  
> > > <>
> > > *À :* 
> > >
> > > *Envoyé le :* Samedi, 26 Septembre 2009, 16h24mn 57s
> > > *Objet :* Re: [cgal-discuss] An error when trying to compute 
> > > intersection of polygons
> > >
> > > So you are trying to compute the intersection between 'first_polygon' 
> > > and all the polygons in the range 'polygons.begin(), polygons.end()'. 
> > > Could you please provide the data that causes the problem. It would 
> > > be nice if you narrow it down first.
> > >
> > > Quoting "BBB HHH" 
> > > <
> > >  
> > > <mailto:>>:
> > >
> > > > Hello,
> > > >
> > > > I am trying to compute the intersection of some polygons in 2D. For 
> > > that purpose, i am using the 2D Regularized Boolean Set-Operations of 
> > > CGAL 3.4. I am also using VS2005 under Windows XP SP3.
> > > >
> > > > For some polygons which seemto be correct (CCW orientation, 
> > > non-degenerate, simple, bounded), i have the following error:
> > > >
> > > > CGAL error: precondition violation!
> > > > Expression : cv.is_in_x_range (p)
> > > > File      : c:\program 
> > > files\cgal-3.4-beta1\include\cgal\arr_segment_traits_2.h
> > > >
> > > > Line      : 481
> > > > Explanation:
> > > > Refer to the bug-reporting instructions at 
> > > http://www.cgal.org/bug_report.html
> > > >
> > > >
> > > > I am using an exact kernel 
> > > (CGAL::Simple_cartesian<CGAL::Lazy_exact_nt<Gmpq> >). The problematic 
> > > line of code is that computing the intersection of some polygons
> > > >
> > > > std::vector<Polygon_2>        polygons;
> > > > // Fill the list of polygons
> > > > // Initialize the polygon set with a polygon
> > > > Polygon_set_2 S(first_polygon);
> > > > S.intersection(polygons.begin(), polygons.end());
> > > >
> > > > Thanks in advance for your help
> > > > Hichem Barki
> > > >
> > > >
> > > >
> > > >      --
> > > > You are currently subscribed to cgal-discuss.
> > > > To unsubscribe or access the archives, go to
> > > > https://lists-sop.inria.fr/wws/info/cgal-discuss
> > > >
> > >
> > >
> > > --You are currently subscribed to cgal-discuss.
> > > To unsubscribe or access the archives, go to
> > > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> > --
> > Scenery Home Page: http://scenery.x-plane.com/
> > Scenery blog: http://xplanescenery.blogspot.com/
> > Plugin SDK: http://www.xsquawkbox.net/xpsdk/
> > X-Plane Wiki: http://wiki.x-plane.com/
> > Scenery mailing list: 
> >
> > Developer mailing list: 
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: