Overlaying Arrangement_with_history destroys edge-to-curve mapping

classic Classic list List threaded Threaded
4 messages Options
gp
Reply | Threaded
Open this post in threaded view
|

Overlaying Arrangement_with_history destroys edge-to-curve mapping

gp
Normally, when I CGAL::insert a curve into an arrangement-with-history, I get
back curve handles such that each halfedge in the arrangement corresponds to
one or more of those curve handles. However, if I make two
arrangements-with-history A and B, store their corresponding curve handles
in two sets, and then make an overlay arrangement, the halfedges in the
overlay arrangement do not correspond to any of the handles in those two
sets. It looks like all the curves are recreated from scratch in the new
arrangement so that my externally stored curve handles become obsolete.

Is this meant to happen? It's not quite clear from the documentation on
overlaying arrangements-with-history: "...the resulting arrangement will
store a consolidated container of input curves, and automatically preserve
the cross-mapping between the arrangement edges and the consolidated curve
set."

The following demonstrates my problem.

main.cpp:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_default_overlay_traits.h>
#include <CGAL/Arr_overlay_2.h>
#include <CGAL/Arr_polyline_traits_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_with_history_2.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using SegmentTraits = CGAL::Arr_segment_traits_2< Kernel >;
using ArrangementTraits = CGAL::Arr_polyline_traits_2< SegmentTraits >;
using Point_2 = ArrangementTraits::Point_2;
using Curve_2 = ArrangementTraits::Curve_2;
using Arrangement = CGAL::Arrangement_with_history_2< ArrangementTraits >;
using OverlayTraits = CGAL::Arr_default_overlay_traits< Arrangement >;

using Curve_handle = Arrangement::Curve_handle;
using Curve_const_handle = Arrangement::Curve_handle;

Curve_2 curve2( const std::vector< Point_2 >& points );

int main ()
{
  // Arrangement A, containing a square-shaped face.
  std::set< Curve_const_handle > arrAHandles;
  Arrangement          arrA;
  Curve_2      c1 = curve2( { Point_2(2, 2), Point_2(6, 2) } );
  Curve_2      c2 = curve2( { Point_2(6, 2), Point_2(6, 6) } );
  Curve_2      c3 = curve2( { Point_2(6, 6), Point_2(2, 6) } );
  Curve_2      c4 = curve2( { Point_2(2, 6), Point_2(2, 2) } );
  arrAHandles.emplace( CGAL::insert (arrA, c1) );
  arrAHandles.emplace( CGAL::insert (arrA, c2) );
  arrAHandles.emplace( CGAL::insert (arrA, c3) );
  arrAHandles.emplace( CGAL::insert (arrA, c4) );

  // Arrangement B, containing a rhombus-shaped face.
  std::set< Curve_const_handle > arrBHandles;
  Arrangement          arrB;
  Curve_2      t1 = curve2( { Point_2(4, 1), Point_2(7, 4) } );
  Curve_2      t2 = curve2( { Point_2(7, 4), Point_2(4, 7) } );
  Curve_2      t3 = curve2( { Point_2(4, 7), Point_2(1, 4) } );
  Curve_2      t4 = curve2( { Point_2(1, 4), Point_2(4, 1) } );
  arrBHandles.emplace( CGAL::insert(arrB, t1) );
  arrBHandles.emplace( CGAL::insert(arrB, t2) );
  arrBHandles.emplace( CGAL::insert(arrB, t3) );
  arrBHandles.emplace( CGAL::insert(arrB, t4) );

  // Compute the overlay of the two arrangements.
  Arrangement          overlay_arr;
  OverlayTraits         overlay_traits;
  overlay (arrA, arrB, overlay_arr, overlay_traits);

  // Look at every halfedge in the overlay result and see if its originating
Curve matches one of the handles
  // in arrAHandles or arrBHandles.
  auto halfEdgeIt = overlay_arr.halfedges_begin();
  while( halfEdgeIt != overlay_arr.halfedges_end() ) {
        bool matchesOneOfTheHandles = false;
        auto originIt =  overlay_arr.originating_curves_begin( halfEdgeIt );
        while( originIt != overlay_arr.originating_curves_end( halfEdgeIt )
) {
            const Curve_handle curveHandle = originIt;
            const bool foundInOldAHandles = arrAHandles.find( curveHandle )
!= arrAHandles.cend();
            const bool foundInOldBHandles = arrBHandles.find( curveHandle )
!= arrBHandles.cend();
            if( foundInOldAHandles || foundInOldBHandles ) {
                matchesOneOfTheHandles = true;
            }
            originIt++;
        }
        if( !matchesOneOfTheHandles ) {
            std::cout << "Halfedge in overlay does not correspond with any
of the original curve handles.\n";
        }
        halfEdgeIt++;
  }
  return 0;
}

Curve_2 curve2( const std::vector< Point_2 >& points )
{
    ArrangementTraits traits;
    auto constructor = traits.construct_curve_2_object();
    return constructor( points.begin(), points.end() );
}




--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Overlaying Arrangement_with_history destroys edge-to-curve mapping

Efi Fogel
The resulting arrangement has new handles.
This is meant to be and cannot be different.
You can use the overlay traits to store the mapping between handles of the operands and handles of the result.
   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




On Fri, 11 Oct 2019 at 03:47, gp <[hidden email]> wrote:
Normally, when I CGAL::insert a curve into an arrangement-with-history, I get
back curve handles such that each halfedge in the arrangement corresponds to
one or more of those curve handles. However, if I make two
arrangements-with-history A and B, store their corresponding curve handles
in two sets, and then make an overlay arrangement, the halfedges in the
overlay arrangement do not correspond to any of the handles in those two
sets. It looks like all the curves are recreated from scratch in the new
arrangement so that my externally stored curve handles become obsolete.

Is this meant to happen? It's not quite clear from the documentation on
overlaying arrangements-with-history: "...the resulting arrangement will
store a consolidated container of input curves, and automatically preserve
the cross-mapping between the arrangement edges and the consolidated curve
set."

The following demonstrates my problem.

main.cpp:

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_default_overlay_traits.h>
#include <CGAL/Arr_overlay_2.h>
#include <CGAL/Arr_polyline_traits_2.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_with_history_2.h>

using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
using SegmentTraits = CGAL::Arr_segment_traits_2< Kernel >;
using ArrangementTraits = CGAL::Arr_polyline_traits_2< SegmentTraits >;
using Point_2 = ArrangementTraits::Point_2;
using Curve_2 = ArrangementTraits::Curve_2;
using Arrangement = CGAL::Arrangement_with_history_2< ArrangementTraits >;
using OverlayTraits = CGAL::Arr_default_overlay_traits< Arrangement >;

using Curve_handle = Arrangement::Curve_handle;
using Curve_const_handle = Arrangement::Curve_handle;

Curve_2 curve2( const std::vector< Point_2 >& points );

int main ()
{
  // Arrangement A, containing a square-shaped face.
  std::set< Curve_const_handle > arrAHandles;
  Arrangement          arrA;
  Curve_2      c1 = curve2( { Point_2(2, 2), Point_2(6, 2) } );
  Curve_2      c2 = curve2( { Point_2(6, 2), Point_2(6, 6) } );
  Curve_2      c3 = curve2( { Point_2(6, 6), Point_2(2, 6) } );
  Curve_2      c4 = curve2( { Point_2(2, 6), Point_2(2, 2) } );
  arrAHandles.emplace( CGAL::insert (arrA, c1) );
  arrAHandles.emplace( CGAL::insert (arrA, c2) );
  arrAHandles.emplace( CGAL::insert (arrA, c3) );
  arrAHandles.emplace( CGAL::insert (arrA, c4) );

  // Arrangement B, containing a rhombus-shaped face.
  std::set< Curve_const_handle > arrBHandles;
  Arrangement          arrB;
  Curve_2      t1 = curve2( { Point_2(4, 1), Point_2(7, 4) } );
  Curve_2      t2 = curve2( { Point_2(7, 4), Point_2(4, 7) } );
  Curve_2      t3 = curve2( { Point_2(4, 7), Point_2(1, 4) } );
  Curve_2      t4 = curve2( { Point_2(1, 4), Point_2(4, 1) } );
  arrBHandles.emplace( CGAL::insert(arrB, t1) );
  arrBHandles.emplace( CGAL::insert(arrB, t2) );
  arrBHandles.emplace( CGAL::insert(arrB, t3) );
  arrBHandles.emplace( CGAL::insert(arrB, t4) );

  // Compute the overlay of the two arrangements.
  Arrangement          overlay_arr;
  OverlayTraits         overlay_traits;
  overlay (arrA, arrB, overlay_arr, overlay_traits);

  // Look at every halfedge in the overlay result and see if its originating
Curve matches one of the handles
  // in arrAHandles or arrBHandles.
  auto halfEdgeIt = overlay_arr.halfedges_begin();
  while( halfEdgeIt != overlay_arr.halfedges_end() ) {
        bool matchesOneOfTheHandles = false;
        auto originIt =  overlay_arr.originating_curves_begin( halfEdgeIt );
        while( originIt != overlay_arr.originating_curves_end( halfEdgeIt )
) {
            const Curve_handle curveHandle = originIt;
            const bool foundInOldAHandles = arrAHandles.find( curveHandle )
!= arrAHandles.cend();
            const bool foundInOldBHandles = arrBHandles.find( curveHandle )
!= arrBHandles.cend();
            if( foundInOldAHandles || foundInOldBHandles ) {
                matchesOneOfTheHandles = true;
            }
            originIt++;
        }
        if( !matchesOneOfTheHandles ) {
            std::cout << "Halfedge in overlay does not correspond with any
of the original curve handles.\n";
        }
        halfEdgeIt++;
  }
  return 0;
}

Curve_2 curve2( const std::vector< Point_2 >& points )
{
    ArrangementTraits traits;
    auto constructor = traits.construct_curve_2_object();
    return constructor( points.begin(), points.end() );
}




--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


gp
Reply | Threaded
Open this post in threaded view
|

Re: Overlaying Arrangement_with_history destroys edge-to-curve mapping

gp
How would a custom OverlayTraits model do this? The OverlayTraits concept
doesn't seem to directly involve the internal curve-to-halfedge mapping
information specific to arrangements with history. The closest it offers are
the three create_edges methods invoked whenever elements in arrangement A
intersect elements in arrangement B. But these will not necessarily be
called for all the edges in the new arrangement. Say, for instance, that
none of the elements in A or B intersect at all; OverlayTraits will, if I
understand right, never have any input.

Should I abandon arrangements with history and imitate them by managing the
curve-handle-to-halfedge mapping manually through halfedge metadata (the
HalfedgeData of Arr_extended_dcel)? If I overlay two arrangements that have
my custom HalfedgeData values assigned to their halfedges, do the
HalfedgeData values get preserved automatically in the new arrangement or do
I need to make a custom OverlayTraits model to ensure that?    



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: Overlaying Arrangement_with_history destroys edge-to-curve mapping

Efi Fogel
No and maybe.
First, one of the creation functions of edges is invoked for every edge in the overlay resulting traits.
An edge can be the result of the overlap of 2 edges, or an edge an a face.
Secondly, make sure that arrangement with history do not provide what you need.
However, they are somehow limited (and can be improved).
Using extended arrangements and a custom overlay traits is more powerful though.

The data is not preserved automatically.
If the halfedge of one arrangement extended with some class A, and the halfedge of the other arrangement extended with class B, what would you expect the resulting data to look like?
Blindly having a pair does not make much sense. Yes, you need a custom traits.
   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/




On Fri, 11 Oct 2019 at 19:34, gp <[hidden email]> wrote:
How would a custom OverlayTraits model do this? The OverlayTraits concept
doesn't seem to directly involve the internal curve-to-halfedge mapping
information specific to arrangements with history. The closest it offers are
the three create_edges methods invoked whenever elements in arrangement A
intersect elements in arrangement B. But these will not necessarily be
called for all the edges in the new arrangement. Say, for instance, that
none of the elements in A or B intersect at all; OverlayTraits will, if I
understand right, never have any input.

Should I abandon arrangements with history and imitate them by managing the
curve-handle-to-halfedge mapping manually through halfedge metadata (the
HalfedgeData of Arr_extended_dcel)? If I overlay two arrangements that have
my custom HalfedgeData values assigned to their halfedges, do the
HalfedgeData values get preserved automatically in the new arrangement or do
I need to make a custom OverlayTraits model to ensure that?   



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss