CGAL 6.1 - 2D Intersection of Curves

Loading...
Searching...
No Matches
User Manual

Authors
  Baruch Zukerman, Ron Wein, and Efi Fogel

# Introduction

Let \( {\mathcal C} = \{C_1, C_2, \ldots, C_n\}\) be a set of curves. We wish to compute all intersection points between two curves in the set in an output-sensitive manner, without having to go over all \(O(n^2)\) curve pairs. To this end, we sweep an imaginary line \( l\) from \( x = -\infty\) to \( x = \infty\) over the plane. While sweeping the plane, we keep track of the order of curves intersecting it. This order changes at a finite number of event points, such that we only have to calculate the intersection points between two curves when they become contiguous. For more details on the surface-sweep algorithm see, for example, [1], Chapter 2.

This chapter describes three functions implemented using the surface-sweep algorithm: given a collection of input curves, compute all intersection points, compute the set of subcurves that are pairwise interior-disjoint induced by them, and checking whether there is at least one pair of curves among them that intersect in their interior.

The implementation is robust. It supports general curves and handles all degenerate cases, including overlapping curves, vertical segments, and tangency between curves. The robustness of the algorithm is guaranteed if the functions are instantiated with a traits class that employs certified computations. This traits class must be a model of the `AosTraits_2` concept - see the Chapter 2D Arrangements for more details.

The complexity of the surface-sweep algorithm is \(O((n + k)\log{n})\) where \( n\) is the number of the input curves and \( k\) is the number of intersection points induced by these curves.

# Example

The simple program listed below computes intersection points induced by a set of four input segments illustrated in Figure 37.1.

Figure 37.1 Four input segments

File Surface_sweep_2/plane_sweep.cpp

// Computing intersection points among curves using the surface-sweep alg.
#include <list>
#include <cassert>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Surface_sweep_2_algorithms.h>
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Arr_segment_traits_2<Kernel> Traits_2;
typedef Traits_2::Curve_2 Segment_2;
int main()
{
// Construct the input segments.
Segment_2 segments[] = {Segment_2 (Point_2 (1, 5), Point_2 (8, 5)),
Segment_2 (Point_2 (1, 1), Point_2 (8, 8)),
Segment_2 (Point_2 (3, 1), Point_2 (3, 8)),
Segment_2 (Point_2 (8, 5), Point_2 (8, 8))};
// Compute all intersection points.
std::list<Point_2> pts;
CGAL::compute_intersection_points(segments, segments + 4,
std::back_inserter(pts));
// Print the result.
std::cout << "Found " << pts.size() << " intersection points: " << std::endl;
std::copy(pts.begin(), pts.end(),
std::ostream_iterator<Point_2>(std::cout, "\n"));
// Compute the non-intersecting sub-segments induced by the input segments.
std::list<Segment_2> sub_segs;
CGAL::compute_subcurves(segments, segments + 4, std::back_inserter(sub_segs));
std::cout << "Found " << sub_segs.size()
<< " interior-disjoint sub-segments." << std::endl;
assert(CGAL::do_curves_intersect (segments, segments + 4));
return 0;
}
CGAL::Arr_segment_traits_2
CGAL::Exact_predicates_exact_constructions_kernel
Kernel::Point_2
CGAL::compute_subcurves
OutputIterator compute_subcurves(InputIterator curves_begin, InputIterator curves_end, OutputIterator subcurves, bool multiple_overlaps=false)
Given a range of curves, compute all -monotone subcurves that are pairwise disjoint in their interior...
CGAL::compute_intersection_points
OutputIterator compute_intersection_points(InputIterator curves_begin, InputIterator curves_end, OutputIterator points, bool report_endpoints=false)
Given a range of curves, compute all intersection points between two (or more) input curves.
CGAL::do_curves_intersect
bool do_curves_intersect(InputIterator curves_begin, InputIterator curves_end)
Given a range of curves, check whether there is at least one pair of curves that intersect in their i...
Kernel

# Design and Implementation History

The current version of the surface-sweep algorithm was written by Efi Fogel, based on previous implementations by Baruch Ester Ezra, Tali Zvi, and Baruch Zukerman.