Skip to Content.
Sympa Menu

cgal-discuss - Re: Re : Re : [cgal-discuss] An error when trying to compute intersection of polygons

Subject: CGAL users discussion list

List archive

Re: Re : Re : [cgal-discuss] An error when trying to compute intersection of polygons


Chronological Thread 
  • From:
  • To:
  • Subject: Re: Re : Re : [cgal-discuss] An error when trying to compute intersection of polygons
  • Date: Sun, 27 Sep 2009 17:15:09 +0200

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






Archive powered by MHonArc 2.6.16.

Top of Page