c++2dcomputational-geometrycgalsimplify

Simplest way to use `CGAL::simplify` on a 2D Arrangement?


I have a CGAL 2D Arrangement, and I would like to simplify each sequence of egdes separated by degree-2 vertices using CGAL::simplify. Is there a simple way to do that, or do I have to do something like the following:

  1. extract such sequences,
  2. simplify each sequence,
  3. modify the sequences in the arrangement?

Note that I would like to end up with a simplified 2D arrangement, not just a list of polylines, so using CGAL::split_graph_into_polylines does not seem to be the best option.

I had a look at CGAL manual and examples, but could not find an answer.


Solution

  • The function that you describe does not exist in the 2D Arrangements package. I'll consider adding it, but it only requires few lines of code. I changed the edge_manipulation example a bit to do what you describe. In particular, look for the loop over the vertices in the code below.

    #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
    #include <CGAL/Arr_segment_traits_2.h>
    #include <CGAL/Arrangement_2.h>
    #include <CGAL/draw_arrangement_2.h>
    
    using Kernel = CGAL::Exact_predicates_exact_constructions_kernel;
    using Traits = CGAL::Arr_segment_traits_2<Kernel>;
    using Point = Traits::Point_2;
    using Segment = Traits::X_monotone_curve_2;
    using Arrangement = CGAL::Arrangement_2<Traits>;
    using Halfedge_handle = Arrangement::Halfedge_handle;
    
    int main() {
      // Step (a)---construct a rectangular face.
      Point q1(1, 3), q2(3, 5), q3(5, 3), q4(3, 1);
      Segment s4(q1, q2), s1(q2, q3), s3(q3, q4), s2(q4, q1);
    
      Traits traits;
      Arrangement arr(&traits);
      Halfedge_handle e1 = arr.insert_in_face_interior(s1, arr.unbounded_face());
      Halfedge_handle e2 = arr.insert_in_face_interior(s2, arr.unbounded_face());
    
      e2 = e2->twin();     // as we wish e2 to be directed from right to left
      arr.insert_at_vertices(s3, e1->target(), e2->source());
      arr.insert_at_vertices(s4, e2->target(), e1->source());
      std::cout << "After step (a):\n";
      std::cout << arr.number_of_vertices() << ","
                << arr.number_of_edges() << ","
                << arr.number_of_faces() << std::endl;
    
      // Step (b)---split e1 and e2 and connect the split points with a segment.
      Point p1(4,4), p2(2,2);
      Segment s1_1(q2, p1), s1_2(p1, q3), s2_1(q4, p2), s2_2(p2, q1), s(p1, p2);
    
      e1 = arr.split_edge(e1, s1_1, s1_2);
      e2 = arr.split_edge(e2, s2_1, s2_2);
      Halfedge_handle e = arr.insert_at_vertices(s, e1->target(), e2->target());
      std::cout << std::endl << "After step (b):" << std::endl;
      std::cout << arr.number_of_vertices() << ","
                << arr.number_of_edges() << ","
                << arr.number_of_faces() << std::endl;
    
      // Step (c)---remove the edge e and merge e1 and e2 with their successors.
      arr.remove_edge(e);
      CGAL::draw(arr, "example", true);
    #if 1
      auto is_mergeable = traits.are_mergeable_2_object();
      auto merge = traits.merge_2_object();
      for (auto v = arr.vertices_begin(); v != arr.vertices_end(); ++v) {
        if (v->degree() > 2) continue;
        auto e = v->incident_halfedges();
        if (! is_mergeable(e->curve(), e->next()->curve())) continue;
        Segment c;
        merge(e->curve(), e->next()->curve(), c);
        arr.merge_edge(e, e->next(), c);
      }
    #else
      arr.merge_edge(e1, e1->next(), s1);
      arr.merge_edge(e2, e2->next(), s2);
    #endif
      CGAL::draw(arr, "example", true);
      std::cout << std::endl << "After step (c):\n";
      std::cout << arr.number_of_vertices() << ","
                << arr.number_of_edges() << ","
                << arr.number_of_faces() << std::endl;
    
      return 0;
    }