CGAL users discussion list

["Ch'Gans" <>]

On 4 April 2017 at 23:16, Efi Fogel 
<>
 wrote:
> 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.

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