2D Intersections

An important relation between geometrical objects is the intersection relation. 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 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.

In the following sections we describe two families of functions. One that checks whether two objects intersect; one that computes the intersection region.

There are two ways to use those functions. The simplest way is to include the header file CGAL/intersections.h. Here all intersection routines are declared.

The drawback of this approach is that a lot is included, which results in long compilation times. It is also possible to include only the intersections that are of interest. The naming scheme of the header files is as follows. Intersections of types Type1<R> and Type2<R> are declared in header file CGAL/Type1_Type2_intersection.h. So, intersection routines of segments and lines in 2D are declared in CGAL/Segment_2_Line_2_intersection.h The order of the type names does not matter. It is also possible to include CGAL/Line_2_Segment_2_intersection.h

For intersections of two objects of the same type, the type name should be mentioned twice:
#include <CGAL/Segment_2_Segment_2_intersection.h>

Every intersection header file declares both the checking routines and the routines to compute the intersection region.

Checking

In order to check if two objects of type Type1 and Type2 intersect, there are routines of the following form:

bool	do_intersect ( Type1<R> obj1, Type2<R> obj2)

The types Type1 and Type2 can be any of the following:

• Point_2
• Line_2
• Ray_2
• Segment_2
• Triangle_2
• Iso_rectangle_2

Computing the intersection region

The intersection region of two geometrical objects of type Type1 and Type2 can be computed with the following family of routines:

Object

intersection ( Type1<R> obj1, Type2<R> obj2)

The return value is Object. This is a special kind of object that can contain an object of any type. Section describes the use of this class.

The types Type1 and Type2 can be any of the following:

• Point_2
• Line_2
• Ray_2
• Segment_2
• Triangle_2
• Iso_rectangle_2

The family of routines that compute the intersection region is not as complete as the family of intersection checking routines. Not all combinations of types are possible. For instance, for more complicated types like polygons and discs those routines are not available. The result must be representable by a single geometric object. The intersection of a line segment with a polygon can result in several line segments. The intersection of a triangle and a disc can result in an object bounded by curved and straight edges. The implementation of boolean operations in the basic library provides more functionality for computing intersections of this kind.

Example

The following example demonstrates the most common use of intersection routines.

#include <CGAL/Segment_2_Line_2_intersection.h>

template <class R>
void foo(Segment_2<R> seg, Line_2<R> line)
{
    Object result;
    Point_2<R> ipoint;
    Segment_2<R> iseg;

    result = intersection(seg, line);
    if (assign(ipoint, result)) {
        // handle the point intersection case.
    } else
        if (assign(iseg, result)) {
            // handle the segment intersection case.
        } else {
            // handle the no intersection case.
        }
}

Possible Result Values

Here we describe the types that can be contained in the Object return value for every possible pair of geometric objects, when the result is non-empty.