Hi there,
I am using an RTree (Boost.Geometry) to do spatial queries, my geomtric items range from small rectangle to long "thick" lines and complex polygon with holes. Some of my polygons have a bounding box that nearly covers the whole set of items my rtree have to deal with, and I need to efficiently do collision detection b/w the small items and the big polygons. Since the rtree works with bounding box, I gain nothing when inserting such "huge" items (their bounding box collides with everyone else's bounding box). See attached picture showing a layer of 254 polygons with holes for a total of ca 70000 points: green are polygon outer boundaries, yellow are inner boundaries, blue are outer boundary bounding box and magenta inner boundary bounding box. I would first like to split these big polygons into a set of smaller polygons (or rectangles), so that i can take advantage of my rtree. I don't care about how optimal the partitioning is, my definition of optimum is: generate quickly subpolygons that have a smallenough bounding box. I looked at CGAL polygon partitioning algos, and the optimal convex partition looks sexy, but with complexity such as O(n^4) I think it is nogo for me. The approximate convex partitioning has better performance, but it seems that in my case it will produce subpolygons which will potentially have "big" bounding boxes. Then there's the triangulation, but given the (very) detailed "coastline" of my polygon, it might not be efficient and will certainly produce a massive amount of triangles. Maybe if i combine this with multipolyline simplification it might work... But this sounds like requiring lot of CPU ... A simple algo I had in mind is spliting a polygon according to a coarse grid: lay out a polygon on a grid, then insert a grid cell in the rtree, iff the cells overlaps the polygon. I thing it's a classic approach in graphics toolkit (Qt has QRegion for this if i'm not wrong). this could potentially be refined using a dichotomy approach... Maybe i could use a CGAL arrangement and monitor face splitting as i insert horizontal/vertical grid lines... Anyhow, I thought i would send a word to this mailing list, and see is someone has an opinion about these sort of problem, maybe i've missed an awesome CGAL superweapon, or maybe i'm trying to be too clever/complicated. Thanks, Chris  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss Screenshot_20170331_023242.png (118K) Download Attachment 
Check out vertical decomposition; see http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html. ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/('_(/ _/ On 30 March 2017 at 17:13, Ch'Gans <[hidden email]> wrote: Hi there, 
On 31 March 2017 at 05:37, Efi Fogel <[hidden email]> wrote:
> Check out vertical decomposition; see > http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html. Hi Efi, 1. I tried the Polygon_vertical_decomposition_2: Out of my 254 polygons and their 70618 vertices, the vertical decomposition generates 8630 trapezoids. Unfortunately their shape don't look attractive to me (in term of bbox, see attached picture with subpolygons in red), one of the main reason is that my system use 16/32gon to approximate a circles and I have pseudo arcs everywhere, this generates lot of extra edges/vertices and so lot of 'thin' subpolygons 2. I had a look at the source code of Polygon_vertical_decomposition_2: It leads me to the polygon_set and it's associated arrangement. It turns out that Polygon_vertical_decomposition_2 uses the observer mechanism to monitor face splitting, so it looks like my idea wasn't that bad/crazy. Now the vertical decomposition uses the "batched vertical rayshooting" approach using the sweep line algorithm (hence the trapezoids), which i need to replace with a sort of XY rayshooting dichotomy, sounds simple in principle, but will see how it goes with implementation. All in all, i've learned a lot by digging into the source code. Thanks for pointing me this one out. Chris PS: By the look of the vertical decomposition results, and from what i've got from google and wikipedia, it seems to me that 'vertical decomposition' and 'trapezoid decomposition' refer to the same thing. > > ____ _ ____ _ > /_____/_) o /__________ __ // > (____ ( ( ( (_/ (_/('_(/ > _/ > > > > On 30 March 2017 at 17:13, Ch'Gans <[hidden email]> wrote: >> >> Hi there, >> >> I am using an RTree (Boost.Geometry) to do spatial queries, my >> geomtric items range from small rectangle to long "thick" lines and >> complex polygon with holes. >> >> Some of my polygons have a bounding box that nearly covers the whole >> set of items my rtree have to deal with, and I need to efficiently do >> collision detection b/w the small items and the big polygons. Since >> the rtree works with bounding box, I gain nothing when inserting such >> "huge" items (their bounding box collides with everyone else's >> bounding box). >> See attached picture showing a layer of 254 polygons with holes for a >> total of ca 70000 points: green are polygon outer boundaries, yellow >> are inner boundaries, blue are outer boundary bounding box and magenta >> inner boundary bounding box. >> >> I would first like to split these big polygons into a set of smaller >> polygons (or rectangles), so that i can take advantage of my rtree. I >> don't care about how optimal the partitioning is, my definition of >> optimum is: generate quickly subpolygons that have a smallenough >> bounding box. >> >> I looked at CGAL polygon partitioning algos, and the optimal convex >> partition looks sexy, but with complexity such as O(n^4) I think it is >> nogo for me. The approximate convex partitioning has better >> performance, but it seems that in my case it will produce subpolygons >> which will potentially have "big" bounding boxes. >> >> Then there's the triangulation, but given the (very) detailed >> "coastline" of my polygon, it might not be efficient and will >> certainly produce a massive amount of triangles. Maybe if i combine >> this with multipolyline simplification it might work... But this >> sounds like requiring lot of CPU ... >> >> A simple algo I had in mind is spliting a polygon according to a >> coarse grid: lay out a polygon on a grid, then insert a grid cell in >> the rtree, iff the cells overlaps the polygon. I thing it's a classic >> approach in graphics toolkit (Qt has QRegion for this if i'm not >> wrong). this could potentially be refined using a dichotomy >> approach... Maybe i could use a CGAL arrangement and monitor face >> splitting as i insert horizontal/vertical grid lines... >> >> Anyhow, I thought i would send a word to this mailing list, and see is >> someone has an opinion about these sort of problem, maybe i've missed >> an awesome CGAL superweapon, or maybe i'm trying to be too >> clever/complicated. >> >> Thanks, >> Chris >> >>  >> You are currently subscribed to cgaldiscuss. >> To unsubscribe or access the archives, go to >> https://sympa.inria.fr/sympa/info/cgaldiscuss >> >> > You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss Screenshot_20170401_001443.png (159K) Download Attachment 
On 31 March 2017 at 14:18, Ch'Gans <[hidden email]> wrote: On 31 March 2017 at 05:37, Efi Fogel <[hidden email]> wrote: Have you considered using circlearcs and segments to start with for your general polygon? The Arr_circle_segment_traits_2 supports such curves and it should be efficient.
Indeed

On 2 April 2017 at 17:06, Efi Fogel <[hidden email]> wrote:
> On 31 March 2017 at 14:18, Ch'Gans <[hidden email]> wrote: >> >> On 31 March 2017 at 05:37, Efi Fogel <[hidden email]> wrote: >> > Check out vertical decomposition; see >> > >> > http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html. >> >> Hi Efi, >> >> 1. I tried the Polygon_vertical_decomposition_2: >> >> Out of my 254 polygons and their 70618 vertices, the vertical >> decomposition generates 8630 trapezoids. Unfortunately their shape >> don't look attractive to me (in term of bbox, see attached picture >> with subpolygons in red), one of the main reason is that my system >> use 16/32gon to approximate a circles and I have pseudo arcs >> everywhere, this generates lot of extra edges/vertices and so lot of >> 'thin' subpolygons > > > Have you considered using circlearcs and segments to start with for your > general polygon? > The Arr_circle_segment_traits_2 supports such curves and it should be > efficient. I would like to, but my input data are straight polygons with approximated arcs. Anyway, I will try the decomposition with Arr_circle_segment_traits_2, out of curiosity. Even if I could use circlearcs, my next problem would then be offsetting such polygons, AFAICT CGAL doesn't offer this possibility, I might be wrong, haven't tried yet. [..] >> PS: By the look of the vertical decomposition results, and from what >> i've got from google and wikipedia, it seems to me that 'vertical >> decomposition' and 'trapezoid decomposition' refer to the same thing. > > > Indeed Thanks, Chris > >> >> 2. I had a look at the source code of Polygon_vertical_decomposition_2: >> It leads me to the polygon_set and it's associated arrangement. >> It turns out that Polygon_vertical_decomposition_2 uses the observer >> mechanism to monitor face splitting, so it looks like my idea wasn't >> that bad/crazy. Now the vertical decomposition uses the "batched >> vertical rayshooting" approach using the sweep line algorithm (hence >> the trapezoids), which i need to replace with a sort of XY >> rayshooting dichotomy, sounds simple in principle, but will see how >> it goes with implementation. >> >> All in all, i've learned a lot by digging into the source code. >> >> Thanks for pointing me this one out. >> >> Chris > >> >> >> >> > >> > ____ _ ____ _ >> > /_____/_) o /__________ __ // >> > (____ ( ( ( (_/ (_/('_(/ >> > _/ >> > >> > >> > >> > On 30 March 2017 at 17:13, Ch'Gans <[hidden email]> wrote: >> >> >> >> Hi there, >> >> >> >> I am using an RTree (Boost.Geometry) to do spatial queries, my >> >> geomtric items range from small rectangle to long "thick" lines and >> >> complex polygon with holes. >> >> >> >> Some of my polygons have a bounding box that nearly covers the whole >> >> set of items my rtree have to deal with, and I need to efficiently do >> >> collision detection b/w the small items and the big polygons. Since >> >> the rtree works with bounding box, I gain nothing when inserting such >> >> "huge" items (their bounding box collides with everyone else's >> >> bounding box). >> >> See attached picture showing a layer of 254 polygons with holes for a >> >> total of ca 70000 points: green are polygon outer boundaries, yellow >> >> are inner boundaries, blue are outer boundary bounding box and magenta >> >> inner boundary bounding box. >> >> >> >> I would first like to split these big polygons into a set of smaller >> >> polygons (or rectangles), so that i can take advantage of my rtree. I >> >> don't care about how optimal the partitioning is, my definition of >> >> optimum is: generate quickly subpolygons that have a smallenough >> >> bounding box. >> >> >> >> I looked at CGAL polygon partitioning algos, and the optimal convex >> >> partition looks sexy, but with complexity such as O(n^4) I think it is >> >> nogo for me. The approximate convex partitioning has better >> >> performance, but it seems that in my case it will produce subpolygons >> >> which will potentially have "big" bounding boxes. >> >> >> >> Then there's the triangulation, but given the (very) detailed >> >> "coastline" of my polygon, it might not be efficient and will >> >> certainly produce a massive amount of triangles. Maybe if i combine >> >> this with multipolyline simplification it might work... But this >> >> sounds like requiring lot of CPU ... >> >> >> >> A simple algo I had in mind is spliting a polygon according to a >> >> coarse grid: lay out a polygon on a grid, then insert a grid cell in >> >> the rtree, iff the cells overlaps the polygon. I thing it's a classic >> >> approach in graphics toolkit (Qt has QRegion for this if i'm not >> >> wrong). this could potentially be refined using a dichotomy >> >> approach... Maybe i could use a CGAL arrangement and monitor face >> >> splitting as i insert horizontal/vertical grid lines... >> >> >> >> Anyhow, I thought i would send a word to this mailing list, and see is >> >> someone has an opinion about these sort of problem, maybe i've missed >> >> an awesome CGAL superweapon, or maybe i'm trying to be too >> >> clever/complicated. >> >> >> >> Thanks, >> >> Chris >> >> >> >>  >> >> You are currently subscribed to cgaldiscuss. >> >> To unsubscribe or access the archives, go to >> >> https://sympa.inria.fr/sympa/info/cgaldiscuss >> >> >> >> >> > >> >>  >> You are currently subscribed to cgaldiscuss. >> To unsubscribe or access the archives, go to >> https://sympa.inria.fr/sympa/info/cgaldiscuss >> >> >  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
On 4 April 2017 at 11:32, Ch'Gans <[hidden email]> wrote: On 2 April 2017 at 17:06, Efi Fogel <[hidden email]> wrote: I see; so by the time you get it it's too late.
You are correct, CGAL does not offer this. However, if it becomes a desire to have it, it just happen to be that there is a student here at TAU that is implementing this.

On 4 April 2017 at 23:16, Efi Fogel <[hidden email]> wrote:
> On 4 April 2017 at 11:32, Ch'Gans <[hidden email]> wrote: >> >> On 2 April 2017 at 17:06, Efi Fogel <[hidden email]> wrote: >> > On 31 March 2017 at 14:18, Ch'Gans <[hidden email]> wrote: >> >> >> >> On 31 March 2017 at 05:37, Efi Fogel <[hidden email]> wrote: >> >> > Check out vertical decomposition; see >> >> > >> >> > >> >> > http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html. >> >> >> >> Hi Efi, >> >> >> >> 1. I tried the Polygon_vertical_decomposition_2: >> >> >> >> Out of my 254 polygons and their 70618 vertices, the vertical >> >> decomposition generates 8630 trapezoids. Unfortunately their shape >> >> don't look attractive to me (in term of bbox, see attached picture >> >> with subpolygons in red), one of the main reason is that my system >> >> use 16/32gon to approximate a circles and I have pseudo arcs >> >> everywhere, this generates lot of extra edges/vertices and so lot of >> >> 'thin' subpolygons >> > >> > >> > Have you considered using circlearcs and segments to start with for >> > your >> > general polygon? >> > The Arr_circle_segment_traits_2 supports such curves and it should be >> > efficient. >> >> I would like to, but my input data are straight polygons with approximated >> arcs. > > > I see; so by the time you get it it's too late. Actually this is not the whole story, these straight polygons need to be graphically stroked to represent the real polygon, this is just a trick to computationally avoid arc segment and yet visually display them as having some (delegating the "hard" job to the painting engine). Again, this is not my choice, that's how the 'legacy system' works. So i should actually offset them, which will give me a polygon with arc segment. Before all of these i needed first to transform my input from "polygon with horizontally connected holes" to CGAL polygon with holes. This is the reverse operation of CGAL::connect_holes. I have some working code, that i would like to clean up and push upstream if there's any interest. >> >> >> Anyway, I will try the decomposition with Arr_circle_segment_traits_2, >> out of curiosity. >> >> Even if I could use circlearcs, my next problem would then be >> offsetting such polygons, AFAICT CGAL doesn't offer this possibility, >> I might be wrong, haven't tried yet. > > > You are correct, CGAL does not offer this. > However, if it becomes a desire to have it, it just happen to be that there > is a student here at TAU that is implementing this. I think this is a very interesting feature, and it would be groovy if it could be applied to polylines as well (eg, millroute carving, ...) A very quick and dirty approach to "offseting" a polyline is to decompose it into segments, apply the offset on each segment (a segment being a degenerated polygon), and finally massjoin all the offsets into a polygon set. Not the most efficient approach but it definitely works... Chris > >> >> >> [..] >> >> PS: By the look of the vertical decomposition results, and from what >> >> i've got from google and wikipedia, it seems to me that 'vertical >> >> decomposition' and 'trapezoid decomposition' refer to the same thing. >> > >> > >> > Indeed >> >> Thanks, >> Chris >> >> > >> >> >> >> 2. I had a look at the source code of Polygon_vertical_decomposition_2: >> >> It leads me to the polygon_set and it's associated arrangement. >> >> It turns out that Polygon_vertical_decomposition_2 uses the observer >> >> mechanism to monitor face splitting, so it looks like my idea wasn't >> >> that bad/crazy. Now the vertical decomposition uses the "batched >> >> vertical rayshooting" approach using the sweep line algorithm (hence >> >> the trapezoids), which i need to replace with a sort of XY >> >> rayshooting dichotomy, sounds simple in principle, but will see how >> >> it goes with implementation. >> >> >> >> All in all, i've learned a lot by digging into the source code. >> >> >> >> Thanks for pointing me this one out. >> >> >> >> Chris >> >> > >> >> >> >> >> >> >> >> > >> >> > ____ _ ____ _ >> >> > /_____/_) o /__________ __ // >> >> > (____ ( ( ( (_/ (_/('_(/ >> >> > _/ >> >> > >> >> > >> >> > >> >> > On 30 March 2017 at 17:13, Ch'Gans <[hidden email]> wrote: >> >> >> >> >> >> Hi there, >> >> >> >> >> >> I am using an RTree (Boost.Geometry) to do spatial queries, my >> >> >> geomtric items range from small rectangle to long "thick" lines and >> >> >> complex polygon with holes. >> >> >> >> >> >> Some of my polygons have a bounding box that nearly covers the whole >> >> >> set of items my rtree have to deal with, and I need to efficiently >> >> >> do >> >> >> collision detection b/w the small items and the big polygons. Since >> >> >> the rtree works with bounding box, I gain nothing when inserting >> >> >> such >> >> >> "huge" items (their bounding box collides with everyone else's >> >> >> bounding box). >> >> >> See attached picture showing a layer of 254 polygons with holes for >> >> >> a >> >> >> total of ca 70000 points: green are polygon outer boundaries, yellow >> >> >> are inner boundaries, blue are outer boundary bounding box and >> >> >> magenta >> >> >> inner boundary bounding box. >> >> >> >> >> >> I would first like to split these big polygons into a set of smaller >> >> >> polygons (or rectangles), so that i can take advantage of my rtree. >> >> >> I >> >> >> don't care about how optimal the partitioning is, my definition of >> >> >> optimum is: generate quickly subpolygons that have a smallenough >> >> >> bounding box. >> >> >> >> >> >> I looked at CGAL polygon partitioning algos, and the optimal convex >> >> >> partition looks sexy, but with complexity such as O(n^4) I think it >> >> >> is >> >> >> nogo for me. The approximate convex partitioning has better >> >> >> performance, but it seems that in my case it will produce >> >> >> subpolygons >> >> >> which will potentially have "big" bounding boxes. >> >> >> >> >> >> Then there's the triangulation, but given the (very) detailed >> >> >> "coastline" of my polygon, it might not be efficient and will >> >> >> certainly produce a massive amount of triangles. Maybe if i combine >> >> >> this with multipolyline simplification it might work... But this >> >> >> sounds like requiring lot of CPU ... >> >> >> >> >> >> A simple algo I had in mind is spliting a polygon according to a >> >> >> coarse grid: lay out a polygon on a grid, then insert a grid cell in >> >> >> the rtree, iff the cells overlaps the polygon. I thing it's a >> >> >> classic >> >> >> approach in graphics toolkit (Qt has QRegion for this if i'm not >> >> >> wrong). this could potentially be refined using a dichotomy >> >> >> approach... Maybe i could use a CGAL arrangement and monitor face >> >> >> splitting as i insert horizontal/vertical grid lines... >> >> >> >> >> >> Anyhow, I thought i would send a word to this mailing list, and see >> >> >> is >> >> >> someone has an opinion about these sort of problem, maybe i've >> >> >> missed >> >> >> an awesome CGAL superweapon, or maybe i'm trying to be too >> >> >> clever/complicated. >> >> >> >> >> >> Thanks, >> >> >> Chris >> >> >> >> >> >>  >> >> >> You are currently subscribed to cgaldiscuss. >> >> >> To unsubscribe or access the archives, go to >> >> >> https://sympa.inria.fr/sympa/info/cgaldiscuss >> >> >> >> >> >> >> >> > >> >> >> >>  >> >> You are currently subscribed to cgaldiscuss. >> >> To unsubscribe or access the archives, go to >> >> https://sympa.inria.fr/sympa/info/cgaldiscuss >> >> >> >> >> > >> >>  >> You are currently subscribed to cgaldiscuss. >> To unsubscribe or access the archives, go to >> https://sympa.inria.fr/sympa/info/cgaldiscuss >> >> >  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
In reply to this post by Efi Fogel
On 31 March 2017 at 05:37, Efi Fogel <[hidden email]> wrote:
> Check out vertical decomposition; see > http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html. Hi Efi, Is it me or it is not possible to apply the vertical decomposition to general polygon with circle/segment edges? The Polygon_vertical_decomposition_2 class uses these harcoded typedefs: typedef CGAL::Polygon_2<Kernel, Container> Polygon_2; typedef CGAL::Polygon_with_holes_2<Kernel, Container> Polygon_with_holes_2; typedef CGAL::Arr_segment_traits_2<Kernel> Arr_segment_traits; typedef CGAL::Gps_segment_traits_2<Kernel, Container, Arr_segment_traits> Traits_2; typedef CGAL::General_polygon_set_2<Traits_2> General_polygon_set_2; So I have tried to reimplement the vertical decomposition using Gps_circle_segment_traits_2, but i'm stuck with a weird problem: To build a vertical X_monotone_curve_2 connecting two arrangement vertices (with associated '1 root' points) I need first a 'Kernel' supporting line, and AFAICT, i cannot build one _exactly_ out of algebraic numbers... Actually I am not even sure what exactly a '1 root' point is, does that mean that it has coordinates expressed as 'a0 +a1*sqrt(r)' with a0=0 and a1=1? If so then that is an interesting property that i might be able to exploit. Another idea i had (but haven't tried yet), is to calculate, using the Kernel, the intersection point of the supporting lines associated with the first 2 incident edges of each vertices, they should be geometrically equivalent to the '1 root' point of the shared vertex but expressed using the kernel number type. But that would work only with linear segment, ... bummer! decomp() and vertical_decomposition() can be easily modified to work with an arrangement based on Gps_circle_segment_traits_2, the only blocker for me ATM is the add_vertical_segment() Does anyone have tips to share on how to make the vertical decomposition works with the Gps_circle_segment_traits_2, and maybe could someone tell me if it is actually possible to do it in an exact manner or not. Thanks, Chris  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
On 7 April 2017 at 15:56, Ch'Gans <[hidden email]> wrote: On 31 March 2017 at 05:37, Efi Fogel <[hidden email]> wrote: You are the first one to try it, and it has been developed to serve as the convex decomposition step of an implementation of the Minkowski sum operation, which supports only linear polygons, so you are probably right about this limitation.
A oneroot number is actually a Square_root_extension; see http://doc.cgal.org/latest/Number_types/classCGAL_1_1Sqrt__extension.html. It's a number represented as 'a0 + a1 * sqrt(a2)', where the type of a0, a1, and a2 are template parameters. a0 doesn't have to be 0. It turns out that this number type is sufficient for the circlesegment traits. This traits supports line segments and circular arcs, where the coefficients of the line segments must be rational. A vertical segment that has an endpoint with Square_root_extension coordinates does not necessarily have rational coordinates any longer, so I guess it is impossible to do it in an exact manner.
Yes, I think it's a real blocker.

On 8 April 2017 at 09:01, Efi Fogel <[hidden email]> wrote:
> On 7 April 2017 at 15:56, Ch'Gans <[hidden email]> wrote: >> On 31 March 2017 at 05:37, Efi Fogel <[hidden email]> wrote: >> > Check out vertical decomposition; see >> > http://doc.cgal.org/latest/Minkowski_sum_2/classCGAL_1_1Polygon__vertical__decomposition__2.html. >> >> Hi Efi, >> >> Is it me or it is not possible to apply the vertical decomposition to >> general polygon with circle/segment edges? > > > You are the first one to try it, and it has been developed to serve as the > convex decomposition step of an implementation of the Minkowski sum > operation, which supports only linear polygons, so you are probably right > about this limitation. [...] >> Actually I am not even sure what exactly a '1 root' point is, does >> that mean that it has coordinates expressed as 'a0 +a1*sqrt(r)' with >> a0=0 and a1=1? If so then that is an interesting property that i might >> be able to exploit. > > > A oneroot number is actually a Square_root_extension; see > http://doc.cgal.org/latest/Number_types/classCGAL_1_1Sqrt__extension.html. > It's a number represented as 'a0 + a1 * sqrt(a2)', where the type of a0, a1, > and a2 are template parameters. a0 doesn't have to be 0. It turns out that > this number type is sufficient for the circlesegment traits. This traits > supports line segments and circular arcs, where the coefficients of the line > segments must be rational. A vertical segment that has an endpoint with > Square_root_extension coordinates does not necessarily have rational > coordinates any longer, so I guess it is impossible to do it in an exact > manner. Thanks for the explanation, very much appreciated. [...] >> decomp() and vertical_decomposition() can be easily modified to work >> with an arrangement based on Gps_circle_segment_traits_2, the only >> blocker for me ATM is the add_vertical_segment() > > > Yes, I think it's a real blocker. I've just spent a few hours this afternoon on this, it all started with: How does boolean set operations deal with that? Surely I can find a piece of code in there that will teach me the tricks... So I dug into the code, frantically looking for a line creating a new segment out of 2 existing points, but never found one! ;) I suddenly realised that my search was vain. The boolean set operations don't need to do that, they "just" need predicates and modifier functions such as split() and merge(), That's it, that's all and it's beautiful! ;) It reminds me of Chuck Norris jokes, one goes "Chuck Norris makes fire by rubbing 2 ice cubes together" lol! Chris  You are currently subscribed to cgaldiscuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgaldiscuss 
Free forum by Nabble  Edit this page 