CGAL users discussion list

[Efi Fogel <>]

Hi Bob,

The Boolean operations are based on 2D arrangements (from the "2D Arrangements" package).

In general you have more options when you work directly with arrangements.

From your description I understand that you would like to obtain the extreme points on the boundary of the intersection that lie on the boundary of p2.

The code below does it.

Best,

Efi

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_extended_dcel.h>
#include <CGAL/Arr_observer.h>
#include <CGAL/Arr_overlay_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>                Traits;
typedef Traits::Point_2                                   Point;
typedef Traits::X_monotone_curve_2                        X_monotone_curve;
typedef CGAL::Arr_extended_dcel<Traits, bool, bool, bool> Dcel;
typedef CGAL::Arrangement_2<Traits, Dcel>                 Arrangement;

template <typename Arrangement>
struct My_observer : CGAL::Arr_observer<Arrangement> {
  typedef typename Arrangement::Vertex_handle           V_handle;
  typedef typename Arrangement::Halfedge_handle         H_handle;
  typedef typename Arrangement::Face_handle             F_handle;
  My_observer(Arrangement& arr, bool flag) :
    CGAL::Arr_observer<Arrangement>(arr),
    m_flag(flag)
  { arr.unbounded_face()->set_data(false); }
  void after_create_vertex(V_handle v) { v->set_data(m_flag); }
  void after_create_edge(H_handle h) {
    h->set_data(m_flag);
    h->twin()->set_data(m_flag);
  }
  void after_split_face(F_handle f1, F_handle f2, bool is_hole)
    { f2->set_data(true); }
private:
  bool m_flag;
};

template <typename Arrangement>
struct Overlay_traits {
  typedef typename Arrangement::Vertex_const_handle     V_const_handle;
  typedef typename Arrangement::Halfedge_const_handle   H_const_handle;
  typedef typename Arrangement::Face_const_handle       F_const_handle;
  typedef typename Arrangement::Vertex_handle           V_handle;
  typedef typename Arrangement::Halfedge_handle         H_handle;
  typedef typename Arrangement::Face_handle             F_handle;
  void create_face(F_const_handle f1, F_const_handle f2, F_handle f) const {
    f->set_data(f1->data() && f2->data());
  }
  void create_vertex(H_const_handle h1, H_const_handle h2, V_handle v) const {
    v->set_data(h2->data());
  }
  void create_vertex(V_const_handle v1, V_const_handle v2, V_handle v) const {
    v->set_data(v2->data());
  }
  void create_vertex(V_const_handle v1, H_const_handle h2, V_handle v) const {
    v->set_data(h2->data());
  }
  void create_vertex(H_const_handle h1, V_const_handle v2, V_handle v) const {
    v->set_data(v2->data());
  }
  void create_vertex(F_const_handle f1, V_const_handle v2, V_handle v) const {
    v->set_data(v2->data());
  }
  void create_vertex(V_const_handle v1, F_const_handle f2, V_handle v) const {}
  void create_edge(H_const_handle h1, H_const_handle h2, H_handle h) const {}
  void create_edge(H_const_handle h1, F_const_handle f2, H_handle h) const {}
  void create_edge(F_const_handle f1, H_const_handle h2, H_handle h) const {}
};

int main(int argc, char* argv[]) {
  const std::vector<Point> pts1{{-1, -1},{1, -1},{1, 1},{-1, 1}};
  const std::vector<X_monotone_curve> cvs1 = {
    {pts1[0], pts1[1]}, {pts1[1], pts1[2]},
    {pts1[2], pts1[3]}, {pts1[3], pts1[0]},
  };
  Arrangement arr1;
  My_observer<Arrangement> obs1(arr1, false);
  CGAL::insert(arr1, cvs1.begin(), cvs1.end());

  const std::vector<Point> pts2{{0, 1},{0.1, 0.2},{0.6, 0},{2, 0},{2, 1},{0, 2}};
  const std::vector<X_monotone_curve> cvs2 = {
    {pts2[0], pts2[1]}, {pts2[1], pts2[2]}, {pts2[2], pts2[3]},
    {pts2[3], pts2[4]}, {pts2[4], pts2[5]}, {pts2[5], pts2[0]}
  };
  Arrangement arr2;
  My_observer<Arrangement> obs2(arr2, true);
  CGAL::insert(arr2, cvs2.begin(), cvs2.end());

  Overlay_traits<Arrangement> ot;
  Arrangement arr;
  CGAL::overlay(arr1, arr2, arr, ot);

  for (auto it = arr.faces_begin(); it != arr.faces_end(); ++it) {
    if (! it->data()) continue;
    auto curr = it->outer_ccb();
    do {
      if (curr->target()->data())
        std::cout << curr->target()->point() << std::endl;
    } while (++curr != it->outer_ccb());
  }
  return 0;
}

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Wed, 9 Feb 2022 at 19:11, Bob Bill <> wrote:

Dear all,

let's say I have two polygons as in the attached image: P1 (black) and P2 (blue). After I obtained their intersection with CGAL::intersection, I can identify the outer boundary of the intersection.

Unfortunately, I do not need the whole outer boundary, but only the vertices of the resulting intersected polygon that are coming from P2.

In the picture they are precisely the ones described by the points (counterclockwise):

(0 , 2)

(0.1 , 0.2)

(0.6 , 0)

(1 , 0)

How can I get those points only? The following snippet provides the whole intersection in the standard way, but then I don't know how to move from there.

Best regards,

Bob

#include <iostream>

#include <vector>

#include <CGAL/Boolean_set_operations_2.h>

#include <CGAL/Constrained_Delaunay_triangulation_2.h>

#include <CGAL/Delaunay_mesh_face_base_2.h>

#include <CGAL/Delaunay_mesh_size_criteria_2.h>

#include <CGAL/Delaunay_mesher_2.h>

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

#include <CGAL/IO/write_VTU.h>

#include <CGAL/Polygon_2.h>

#include <CGAL/Polygon_with_holes_2.h>

#include <CGAL/Triangulation_2.h>

#include <CGAL/draw_polygon_2.h>

#include <CGAL/draw_polygon_with_holes_2.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;

typedef CGAL::Polygon_2<Kernel> Polygon;

typedef CGAL::Polygon_with_holes_2<Kernel> Polygon_with_holes_2;

typedef Polygon::Point_2 Point;

typedef Polygon::Segment_2 Segment;

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;

typedef CGAL::Triangulation_vertex_base_2<K> Vb;

typedef CGAL::Delaunay_mesh_face_base_2<K> Fb;

typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;

typedef CGAL::Constrained_Delaunay_triangulation_2<K, Tds> CDT;

typedef CGAL::Delaunay_mesh_size_criteria_2<CDT> Criteria;

typedef CDT::Vertex_handle Vertex_handle;

int main() {

// define polygon

const std::vector<Point> pts{{-1, -1}, {1, -1}, {1, 1}, {-1, 1}};

const Polygon p(pts.cbegin(), pts.cend());

const std::vector<Point> pts2{{0, 1}, {0.1,0.2},{0.6, 0}, {2, 1}, {0, 2}};

const Polygon p2(pts2.cbegin(), pts2.cend());

std::vector<Polygon_with_holes_2> poly_list;

auto oi = CGAL::intersection(p, p2, std::back_inserter(poly_list));

Polygon intersect = poly_list[0].outer_boundary();

return 0;

}

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