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

Functions
template<typename Kernel >
decltype(auto)	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.
template<typename Kernel >
decltype(auto)	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 >

decltype(auto) 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 of intersecting two objects of the types Type1 and Type2 can be specified through the placeholder type specifier auto. It is equivalent to std::optional< std::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 std::optional< std::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 of intersecting two objects of the types Type1 and Type2 can be specified through the placeholder type specifier auto. It is equivalent to std::optional< std::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 std::optional< std::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 specified through the placeholder type specifier auto, but you must anyway know that the result type is a std::optional<std::variant<..> >, in order to unpack the point or segment.

std::optional comes in as there might be no intersection. std::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 std::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);
 
  const auto result = intersection(seg, lin);
  if (result) {
    if (const Segment_2* s = std::get_if<Segment_2>(&*result)) {
      std::cout << *s << std::endl;
    } else {
      const Point_2* p = std::get_if<Point_2 >(&*result);
      std::cout << *p << std::endl;
    }
  }
  return 0;
}

The second example uses std::visit.

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);
 
  const auto result = intersection(seg, lin);
  if (result) {
    std::visit(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>
 
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{
  const Segment& s;
  K::Intersect_2 intersect;
 
  Intersector(const Segment& seg): s(seg) {}
 
  decltype(auto)
  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;
}