# Splitting (and simplifying) complex polygon with holes

10 messages
Open this post in threaded view
|
Report Content as Inappropriate

## Splitting (and simplifying) complex polygon with holes

 Hi there, I am using an R-Tree (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 sub-polygons that have a small-enough 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 no-go for me. The approximate convex partitioning has better performance, but it seems that in my case it will produce sub-polygons which will potentially have "big" bounding boxes. Then there's the triangulation, but given the (very) detailed "coast-line" of my polygon, it might not be efficient and will certainly produce a massive amount of triangles. Maybe if i combine this with multi-polyline 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 super-weapon, or maybe i'm trying to be too clever/complicated. Thanks, Chris -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss Screenshot_20170331_023242.png (118K) Download Attachment
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

 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 wrote:Hi there, I am using an R-Tree (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 sub-polygons that have a small-enough 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 no-go for me. The approximate convex partitioning has better performance, but it seems that in my case it will produce sub-polygons which will potentially have "big" bounding boxes. Then there's the triangulation, but given the (very) detailed "coast-line" of my polygon, it might not be efficient and will certainly produce a massive amount of triangles. Maybe if i combine this with multi-polyline 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 super-weapon, or maybe i'm trying to be too clever/complicated. Thanks, Chris -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

 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 sub-polygons in red), one of the main reason is that my system use 16/32-gon to approximate a circles and I have pseudo arcs everywhere, this generates lot of extra edges/vertices and so lot of 'thin' sub-polygons 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 ray-shooting" approach using the sweep line algorithm (hence the trapezoids), which i need to replace with a sort of X-Y ray-shooting 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 R-Tree (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 sub-polygons that have a small-enough >> 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 >> no-go for me. The approximate convex partitioning has better >> performance, but it seems that in my case it will produce sub-polygons >> which will potentially have "big" bounding boxes. >> >> Then there's the triangulation, but given the (very) detailed >> "coast-line" of my polygon, it might not be efficient and will >> certainly produce a massive amount of triangles. Maybe if i combine >> this with multi-polyline 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 super-weapon, or maybe i'm trying to be too >> clever/complicated. >> >> Thanks, >> Chris >> >> -- >> You are currently subscribed to cgal-discuss. >> To unsubscribe or access the archives, go to >> https://sympa.inria.fr/sympa/info/cgal-discuss>> >> > -- You are currently subscribed to cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss Screenshot_20170401_001443.png (159K) Download Attachment
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

 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             Polygon_2;   typedef CGAL::Polygon_with_holes_2  Polygon_with_holes_2;   typedef CGAL::Arr_segment_traits_2             Arr_segment_traits;   typedef CGAL::Gps_segment_traits_2                                                          Traits_2;   typedef CGAL::General_polygon_set_2          General_polygon_set_2; So I have tried to re-implement 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 cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss
Open this post in threaded view
|
Report Content as Inappropriate

## Re: Splitting (and simplifying) complex polygon with holes

 On 7 April 2017 at 15:56, Ch'Gans 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. The Polygon_vertical_decomposition_2 class uses these harcoded typedefs:   typedef CGAL::Polygon_2             Polygon_2;   typedef CGAL::Polygon_with_holes_2  Polygon_with_holes_2;   typedef CGAL::Arr_segment_traits_2             Arr_segment_traits;   typedef CGAL::Gps_segment_traits_2                                                          Traits_2;   typedef CGAL::General_polygon_set_2          General_polygon_set_2; So I have tried to re-implement 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.A one-root 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 circle-segment 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. 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()Yes, I think it's a real blocker. 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 cgal-discuss. To unsubscribe or access the archives, go to https://sympa.inria.fr/sympa/info/cgal-discuss