CGAL users discussion list

["Jens K. Becker" <>]

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 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: 
> 
-- 
Dr. J.K. Becker
University of Tuebingen - Institute for Geoscience
Sigwartst. 10 - 72076 Tuebingen (Germany)
Tel.: ++49 7071 29 73139   Fax: +49 7071 5059
Web: http://www.jkbecker.de