CGAL::intersection() (2D/3D Linear Kernel)

Functions
template<typename Kernel >
cpp11::result_of< Kernel::Intersect_23(Type1, Type2)>::type	CGAL::intersection (Type1< Kernel > obj1, Type2< Kernel > obj2)
	Two objects obj1 and obj2 intersect if there is a point p that is part of both obj1 and obj2. More...
template<typename Kernel >
boost::optional< boost::variant< Point_3, Line_3, Plane_3 > >	CGAL::intersection (const Plane_3< Kernel > &pl1, const Plane_3< Kernel > &pl2, const Plane_3< Kernel > &pl3)
	returns the intersection of 3 planes, which can be a point, a line, a plane, or empty.

Function Documentation

intersection()

template<typename Kernel >

cpp11::result_of<Kernel::Intersect_23(Type1, Type2)>::type CGAL::intersection	(	Type1< Kernel >	obj1,
		Type2< Kernel >	obj2
	)

#include <CGAL/intersections.h>

Two objects obj1 and obj2 intersect if there is a point p that is part of both obj1 and obj2.

The intersection region of those two objects is defined as the set of all points p that are part of both obj1 and obj2. Note that for objects like triangles and polygons that enclose a bounded region, this region is considered part of the object. If a segment lies completely inside a triangle, then those two objects intersect and the intersection region is the complete segment.

Here, Intersect_23 means either Intersect_2 or Intersect_3, depending on the arguments.

The following tables give the possible values for Type1 and Type2.

2D Intersections

The return type can be obtained through CGAL::cpp11::result_of<Kernel::Intersect_2(A, B)>::type. It is equivalent to boost::optional< boost::variant< T... > >, the last column in the table providing the template parameter pack.

Type1	Type2	Return Type: T...
Iso_rectangle_2	Iso_rectangle_2	Iso_rectangle_2
Iso_rectangle_2	Line_2	Point_2, or Segment_2
Iso_rectangle_2	Ray_2	Point_2, or Segment_2
Iso_rectangle_2	Segment_2	Point_2, or Segment_2
Iso_rectangle_2	Triangle_2	Point_2, or Segment_2, or Triangle_2, or std::vector<Point_2>
Line_2	Line_2	Point_2, or Line_2
Line_2	Ray_2	Point_2, or Ray_2
Line_2	Segment_2	Point_2, or Segment_2
Line_2	Triangle_2	Point_2, or Segment_2
Ray_2	Ray_2	Point_2, or Segment_2, or Ray_2
Ray_2	Segment_2	Point_2, or Segment_2
Ray_2	Triangle_2	Point_2, or Segment_2
Segment_2	Segment_2	Point_2, or Segment_2
Segment_2	Triangle_2	Point_2, or Segment_2
Triangle_2	Triangle_2	Point_2, or Segment_2, or Triangle_2, or std::vector<Point_2>

Additional overloads are provided for the type Point_2 combined with any other type with the result type being boost::optional< boost::variant< Point_2 > >. Overloads are also provided for the type Bbox_2, for all intersections existing with the type Iso_rectangle_2. Note that the return type for Bbox_2 - Bbox_2 is Bbox_2 and not Iso_rectangle_2.

3D Intersections

The return type can be obtained through CGAL::cpp11::result_of<Kernel::Intersect_3(A, B)>::type. It is equivalent to boost::optional< boost::variant< T... > >, the last column in the table providing the template parameter pack.

Type1	Type2	Return Type: T...
Line_3	Line_3	Point_3, or Line_3
Line_3	Plane_3	Point_3, or Line_3
Line_3	Ray_3	Point_3, or Ray_3
Line_3	Segment_3	Point_3, or Segment_3
Line_3	Triangle_3	Point_3, or Segment_3
Line_3	Tetrahedron_3	Point_3, or Segment_3
Line_3	Iso_cuboid_3	Point_3, or Segment_3
Plane_3	Plane_3	Line_3, or Plane_3
Plane_3	Ray_3	Point_3, or Ray_3
Plane_3	Segment_3	Point_3, or Segment_3
Plane_3	Sphere_3	Point_3, or Circle_3
Plane_3	Triangle_3	Point_3, or Segment_3, or Triangle_3
Plane_3	Tetrahedron_3	Point_3, or Segment_3, or Triangle_3, or std::vector<Point_3>
Plane_3	Iso_cuboid_3	Point_3, or Segment_3, or Triangle_3, or std::vector<Point_3>
Ray_3	Ray_3	Point_3, or Ray_3, or Segment_3
Ray_3	Segment_3	Point_3, or Segment_3
Ray_3	Triangle_3	Point_3, or Segment_3
Ray_3	Tetrahedron_3	Point_3, or Segment_3
Ray_3	Iso_cuboid_3	Point_3, or Segment_3
Segment_3	Segment_3	Point_3, or Segment_3
Segment_3	Triangle_3	Point_3, or Segment_3
Segment_3	Tetrahedron_3	Point_3, or Segment_3
Segment_3	Iso_cuboid_3	Point_3, or Segment_3
Sphere_3	Sphere_3	Point_3, or Circle_3, or Sphere_3
Triangle_3	Triangle_3	Point_3, or Segment_3, or Triangle_3, or std::vector < Point_3 >
Triangle_3	Tetrahedron_3	Point_3, or Segment_3, or Triangle_3, or std::vector < Point_3 >
Triangle_3	Iso_cuboid_3	Point_3, or Segment_3, or Triangle_3, or std::vector < Point_3 >

Additional overloads are provided for the type Point_3 combined with any other type with the result type being boost::optional< boost::variant< Point_3 > >. Overloads are also provided for the type Bbox_3, for all intersections existing with the type Iso_cuboid_3. Note that the return type for Bbox_3 - Bbox_3 is Bbox_3 and not Iso_cuboid_3.

Examples

The following examples demonstrate the most common use of intersection() functions with the 2D and 3D Linear Kernel.

In the first two examples we intersect a segment and a line. The result type can be obtained with CGAL::cpp11::result_of. It looks simpler if you use a C++ compiler which supports auto, but you must anyways know that the result type is a boost::optional<boost::variant<..> >, in order to unpack the point or segment.

boost::optional comes in as there might be no intersection. boost::variant comes in as, if there is an intersection, it is either a point or a segment.

As explained in the boost manual pages for boost::variant, there are two ways to access the variants. The first examples uses boost::get.

File Kernel_23/intersection_get.cpp

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/intersections.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;
typedef K::Line_2 Line_2;
typedef K::Intersect_2 Intersect_2;

int main()
{
  Segment_2 seg(Point_2(0,0), Point_2(2,2));
  Line_2 lin(1,-1,0);

  CGAL::cpp11::result_of<Intersect_2(Segment_2, Line_2)>::type
    result = intersection(seg, lin);
  if (result) {
    if (const Segment_2* s = boost::get<Segment_2>(&*result)) {
      std::cout << *s << std::endl;
    } else {
      const Point_2* p = boost::get<Point_2 >(&*result);
      std::cout << *p << std::endl;
    }
  }
  return 0;
}

The second example uses boost::apply_visitor.

File Kernel_23/intersection_visitor.cpp

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/intersections.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;
typedef K::Line_2 Line_2;
typedef K::Intersect_2 Intersect_2;

struct Intersection_visitor {
  typedef void result_type;

  void operator()(const Point_2& p) const
  {
    std::cout << p << std::endl;
  }

  void operator()(const Segment_2& s) const
  {
    std::cout << s << std::endl;
  }
};

int main()
{
  Segment_2 seg(Point_2(0,0), Point_2(1,1));
  Line_2 lin(1,-1,0);

  // with C++11 support
  // auto result = intersection(seg, lin);
  // without C++11
  CGAL::cpp11::result_of<Intersect_2(Segment_2, Line_2)>::type
    result = intersection(seg, lin);
  if (result) {
    boost::apply_visitor(Intersection_visitor(), *result);
  } else {
    // no intersection
  }

  return 0;
}

A third example shows the use of the intersection function as a plain function call and with Dispatch_output_iterator, combined with a standard library algorithm.

File Kernel_23/intersections.cpp

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/iterator.h>
#include <CGAL/point_generators_2.h>

#include <boost/bind.hpp>

typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_2                     Point;
typedef K::Segment_2                   Segment;

typedef CGAL::Creator_uniform_2<double,Point>              Pt_creator;
typedef CGAL::Random_points_on_segment_2<Point,Pt_creator> P1;
typedef CGAL::Random_points_on_circle_2<Point,Pt_creator>  P2;
typedef CGAL::Creator_uniform_2< Point, Segment>           Seg_creator;
typedef CGAL::Join_input_iterator_2< P1, P2, Seg_creator>  Seg_iterator;

struct Intersector{
  typedef CGAL::cpp11::result_of<K::Intersect_2(Segment,Segment)>::type result_type;
  const Segment& s;
  K::Intersect_2 intersect;

  Intersector(const Segment& seg): s(seg) {}

  result_type
  operator() ( const Segment& other) const
  {
    return intersect(s, other);
  }
};

int main()
{
  std::vector<Segment> input;

  // Prepare point generator for the horizontal segment, length 200.
  P1 p1( Point(-100,0), Point(100,0));

  // Prepare point generator for random points on circle, radius 250.
  P2 p2( 250);

  // Create segments.
  Seg_iterator g( p1, p2);
  std::copy_n( g, 200, std::back_inserter(input));


  // splitting results with Dispatch_output_iterator
  std::vector<Point> points;
  std::vector<Segment> segments;

  typedef CGAL::Dispatch_output_iterator<
    std::tuple<Point,Segment>, std::tuple< std::back_insert_iterator<std::vector<Point> >,
                                               std::back_insert_iterator<std::vector<Segment> > > >
    Dispatcher;

  Dispatcher disp = CGAL::dispatch_output<Point,Segment>( std::back_inserter(points),
                                                          std::back_inserter(segments) );

  // intersects the first segment of input with all other segments
  // The resulting points or segments are written in the vectors with the same names
  std::transform( input.begin(), input.end(), disp,
                  Intersector(input.front()) );


  std::cout << "Point intersections: " << points.size() << std::endl;
  std::cout << "Segment intersections: " << segments.size() << std::endl;


  return 0;
}