CGAL users discussion list

[Efi Fogel <>]

On 4 April 2017 at 11:32, Ch'Gans <> wrote:

On 2 April 2017 at 17:06, Efi Fogel <> wrote:
> 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.

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