CGAL users discussion list

[Dietrich Bollmann <>]

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