Splitting (and simplifying) complex polygon with holes

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

Splitting (and simplifying) complex polygon with holes

chgans
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
Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

Efi Fogel

   ____  _        ____             _
  /_____/_) 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



Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

chgans
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
Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

Efi Fogel
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 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

Have you considered using circle-arcs and segments to start with for your general polygon?
The Arr_circle_segment_traits_2 supports such curves and it should be efficient.


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.

Indeed
 


>
>    ____  _        ____             _
>   /_____/_) 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



Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

chgans
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 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
>
>
> Have you considered using circle-arcs 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 circle-arcs, 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 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

>
>>
>>
>>
>> >
>> >    ____  _        ____             _
>> >   /_____/_) 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
>>
>>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

Efi Fogel
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 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
>
>
> Have you considered using circle-arcs 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.

Anyway, I will try the decomposition with Arr_circle_segment_traits_2,
out of curiosity.

Even if I could use circle-arcs, 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.
 

[..]
>> 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 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

>
>>
>>
>>
>> >
>> >    ____  _        ____             _
>> >   /_____/_) 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
>>
>>
>

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

chgans
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 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
>> >
>> >
>> > Have you considered using circle-arcs 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 circle-arcs, 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, mill-route carving, ...)

A very quick and dirty approach to "offseting" a poly-line is to
decompose it into segments, apply the offset on each segment (a
segment being a degenerated polygon), and finally mass-join 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 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
>>
>> >
>> >>
>> >>
>> >>
>> >> >
>> >> >    ____  _        ____             _
>> >> >   /_____/_) 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
>> >>
>> >>
>> >
>>
>> --
>> 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


Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

chgans
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 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


Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

Efi Fogel

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.

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 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



Reply | Threaded
Open this post in threaded view
|

Re: Splitting (and simplifying) complex polygon with holes

chgans
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 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.

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 after-noon 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 cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss