CGAL users discussion list

[Dietrich Bollmann <>]

Hi efif, Jens and Ben,

Thanks for your answers!

As I didn't have much time and don't need the best of all possible
solutions, I finally followed Ben's last mentioned pragmatic approach
and just stored the vertices in a hash:

> Finally a totally different approach would be: simply store a tree of 
> vertices...since the coordinates will be unmodified from the original
to 
> the destination vertices, I think you could use a lexicographical
sort 
> to build a sorted array or tree of vertices for fast lookup to source 
> polygon by coordinate.

It seems to work fine :)

Thanks again, Dietrich


Sorry for answering late.  I was busy and didn't find the time to test
this approach before...


On Tue, 2009-05-12 at 10:58 +0200, Jens K. Becker wrote:
Hi all,
> 
> I am not sure if that also applies to the 2D case of polygons, but in
3D
> you can add information to the vertices (or anything else). Thus you
> could store ID's in your original polygon and look for them in the
> resulting polygon. 
> 
> See
>
http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Polyhedron/Chapter_main.html
> 
> for the 3D example how to do that. Again, I am not sure if that also
> works in 2D.
> 
> Jens
> 

On Wed, 2009-05-13 at 10:09 +0300, 

 wrote:
Indeed. It also works in the 2D case. You can extend the DCEL records  
> of the underlying arrangement and use it when you define your
Polygon  
> set (CGAL::Polygon_set_2<Kernel,Container,Extended_dcel>).
> 
> Quoting "Jens K. Becker" 
> <>:
> 

On Thu, 2009-05-07 at 08:36 -0400, Ben Supnik wrote:
> Hi Dietrich,
> 
> The general polygon set code is built on top of (and templated by) 
> arrangement_2.  So in my code, I do some tricks using this.
> 
> While you can add data to the arrangement_2 elements (vertices, 
> halfedges, faces) I think this isn't quite what you want for two reasons:
> 
> - CGAL does not have a general "vertex with history" concept to let you 
> remember what vertex came from where.  E.g. if a vertex is from more 
> than one polygon, it may not be obvious which one it came from and...
> 
> - I believe that you don't get to provide a "merge rule" for 
> arrangement_2 data when doing polygon ops.  In other words, the meta 
> data won't be copied appropriately from your input arrangements (if you 
> convert your input polygons into arrangements) to your final ones.
> 
> I think the "right" way to do this is: use an arrangement with 
> consolidated curve data. Consolidated curve data means that you can have 
> an STL set of data per underlying curve.  The result will be that you 
> can have a set of IDs for each edge in the final map that match the 
> input map.  Thus you could relocate A and C and since A and C have 
> direction, you an find a1, a4, c1, and c8.
> 
> If you use this strategy, you'll need to check for the cases where an 
> underlying curve is either split or reversed in direction...if it is 
> split, only one end of it points to a vertex of interest.
> 
> An edge can be reversed in direction when the same edge (of opposite 
> direction) is present in two different polygons - the arrangement_2 only 
> stores one "curve" (with direction) per complete edge.
> 
> ----------------------------------------------------------------
> 
> Finally a totally different approach would be: simply store a tree of 
> vertices...since the coordinates will be unmodified from the original to 
> the destination vertices, I think you could use a lexicographical sort 
> to build a sorted array or tree of vertices for fast lookup to source 
> polygon by coordinate.
> 
> cheers
> BEn
> 
> Dietrich Bollmann wrote:
> > Hi,
> > 
> > I am experimenting with the union of polygons and wonder, if there is
> > some way to determine which vertices from the resulting polygon
> > correspond to which vertices of the original polygons.
> > 
> > Here comes an example:
> > 
> > Union operation:
> > 
> >   A = [(0, 3), (0, 1), (2, 1), (2, 3)]
> >   B = [(1, 2), (1, 0), (3, 0), (3, 2)]
> > 
> >         a1  A  a4                   c1  C  c8
> >     3    o-----o                     o-----o  
> >          | b1  |  b4                 |     |  c6
> >     2    |  o--+--o                  |     x--o
> >          |  |  |  |      =union=>    | c3  c7 | B
> >     1    o--+--o  | B                o--x     |
> >         a2  |  a3 |                 c2  |     |
> >     0       o-----o                     o-----o
> >            b2     b3                   c4     c5
> > 
> >          0  1  2  3                  0  1  2  3
> > 
> > And here what I am interested in:
> > 
> > Vertex Mapping: C X A U B U {inserted}
> > 
> >   (c1, a1), (c2, a2),
> >   (c3, inserted),
> >   (c4, b2), (c5, b3), (c6, b4),
> >   (c7, inserted),
> >   (c8, a4)
> > 
> >>From Joachim Reichel I got the idea to mark the vertices of the original
> > polygons and to later look for the markers in the resulting polygon.
> > But I couldn't find any information about markers in the manual...
> > 
> > Any idea?
> > 
> > Thanks, Dietrich
> > 
> > 
> > ---
> > Here the same example (wrapped into Python):
> > 
> >>>> from CGAL import do_intersect, join
> >>>> from CGAL.Polygon import Polygon
> >>>> from CGAL.Kernel  import Point_2
> >>>>
> >>>> # Construct the two input polygons.
> > ... 
> >>>> A = [(0, 3), (0, 1), (2, 1), (2, 3)]
> >>>> B = [(1, 2), (1, 0), (3, 0), (3, 2)]
> >>>>
> >>>> p = Polygon([Point_2(v[0], v[1]) for v in A])
> >>>> q = Polygon([Point_2(v[0], v[1]) for v in B])
> >>>>
> >>>> print "p = ",; p.pretty_print()
> > p = { 4 vertices: [(0, 3), (0, 1), (2, 1), (2, 3)] }
> > 
> >>>> print "q = ",; q.pretty_print()
> > q = { 4 vertices: [(1, 2), (1, 0), (3, 0), (3, 2)] }
> > 
> >>>> # Compute the union of P and Q.
> > ... 
> >>>> union = join(p, q)
> >>>> print "union = ",; union.pretty_print()
> > union = { Outer boundary = { 8 vertices: [(1, 0), (3, 0), (3, 2), (2,
> > 2), (2, 3), (0, 3), (0, 1), (1, 1)] }
> >   0 holes:
> >  }
> > 
> > 
> > 
> > 
> 
> -- 
> Scenery Home Page: http://scenery.x-plane.com/
> Scenery blog: http://xplanescenery.blogspot.com/
> Plugin SDK: http://www.xsquawkbox.net/xpsdk/
> X-Plane Wiki: http://wiki.x-plane.com/
> Scenery mailing list: 
> 
> Developer mailing list: 
>