CGAL 5.5.2 - 2D and 3D Linear Geometry 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. More...
 
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 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 of intersecting two objects of the types Type1 and Type2 can be specified through the placeholder type specifier auto. 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 specified through the placeholder type specifier auto, but you must anyway 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 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 = 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 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) {
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>
typedef K::Point_2 Point;
typedef K::Segment_2 Segment;
typedef CGAL::Random_points_on_segment_2<Point,Pt_creator> P1;
typedef CGAL::Random_points_on_circle_2<Point,Pt_creator> P2;
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;
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;
}