CGAL users discussion list

[David Keller <>]

Hi,

You find a patch to fix a bug in the equality-comparison of 
polyline-arrangements as reported in my post on 03/14: The problem is 
caused by the segment-wise comparison of polylines which does not take 
into account that polylines with different representation may share the 
same graph. Maybe someone is interested to check its validity or even 
give a more efficient implementation.

I tried to hunt down the bugs observed in IO of Arrangement_2 reported 
in my last post. There are seemingly different inconsistencies in the 
current implementation:

  1. Unbounded faces are not read correctly. See my post from 03/28 for
     a reproducer.
  2. CGAL/Arr_accessor.h (1037) in function clear_all() : The call
     p_arr->dcel.delete_all() removes DCEL-entries in the current
     arrangement. This leads to dangling pointers in Arrangement_2,
     i.e. the fictitious face and the vertices (un_face, v_br, v_bl,
     v_tr, v_tl). The function is called from
     CGAL/IO/Arrangement_2_reader.h (107). From my understanding these
     pointer members in Arrangement_2 are not set when reading an
     arrangement leading to an uncontrolled behavior of the
     reconstructed arrangement.
  3. An empty arrangement (result of default constructor of
     Arrangement_2) contains one fictitious face (actually 2 DCEL
     entries), 4 fictitious vertices and 4 fictitious edges. The
     CGAL/IO/Arrangement_2_writer.h writes 0 fictitious vertices, 4
     fictitious edges and 2 faces. It is not possible to read an empty
     arrangement with the current implementation (comment Line 22 in
     examples/Arrangement_2/io.cpp for a demonstration).

Can somebody sketch a solution to these problems?
Thanks and best regards
David Keller
--- CGAL-3.3.1/include/CGAL/Arr_polyline_traits_2.h	2007-08-25 21:01:33.000000000 +0200
+++ CGAL-3.3.1.patched/include/CGAL/Arr_polyline_traits_2.h	2008-04-02 09:18:37.000000000 +0200
@@ -331,21 +331,31 @@
     bool operator()(const X_monotone_curve_2 & cv1,
                     const X_monotone_curve_2 & cv2) const
     {
-      // The two curves must contain the same number of segments.
-      unsigned int n1 = cv1.size();
-      unsigned int n2 = cv2.size();
-      if (n1 != n2)
-        return false;
-
-      // Check the pairwise equality of the contained segments.
       typename Segment_traits_2::Equal_2 equal = seg_traits->equal_2_object();
-      unsigned int i;
-
-      for (i = 0; i < n1; ++i) {
-        if (!equal(cv1[i], cv2[i]))
-          return false;
+      typename Self::Construct_min_vertex_2 min_vertex = typename Self::Construct_min_vertex_2( seg_traits );
+      typename Self::Construct_max_vertex_2 max_vertex = typename Self::Construct_max_vertex_2( seg_traits );
+      typename Self::Compare_y_at_x_2 compare_y = typename Self::Compare_y_at_x_2( seg_traits );
+
+      // Check if source and target are the same
+      if ( equal( min_vertex( cv1 ), min_vertex( cv2 ) ) &&
+           equal( max_vertex( cv1 ), max_vertex( cv2 ) ) )
+      {
+        // Make long (c1) and short (c2) curve
+        const X_monotone_curve_2* c1 = &cv1;
+        const X_monotone_curve_2* c2 = &cv2;
+        if ( c1->size() < c2->size() ) 
+          std::swap( c1, c2 );
+
+        // Iterate over the points in c1 and try to find them on c2.
+        typename X_monotone_curve_2::const_iterator pit1;
+        for ( pit1 = c1->begin(); pit1 != c1->end(); ++pit1 )
+        {
+          if ( compare_y( *pit1, *c2 ) != EQUAL )
+            return false;
+        }
+        return true;
       }
-      return true;
+      return false;
     }
   };