Segment Data Structure

An implementation of the data stucture for reporting segment intersections described in chapter 10 of Computational Geometry: Algorithms and Applications 3rd Edition by Mark de Berg, Otfried Cheong, Marc van Krevel, Mark Overmars

Prerequisites

• CGAL
• Boost

Description

The data structure takes as input as set of line segments $S$. Given a vertical segment $q$, a query method reports the segments in $S$ which intersect $q$.

Note that for this implementation, the segments in $S$ must be in general position, i.e., no vertical segemnts and no intersecting pairs.

Using the library

A simple example of how to use the library is provided in main.cpp