CGAL users discussion list

[Efi Fogel <>]

On 31 March 2017 at 14:18, Ch'Gans <> wrote:

On 31 March 2017 at 05:37, Efi Fogel <> 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 <> 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