CGAL users discussion list

[Ben Supnik <>]

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: