intersection.cpp File Reference

Implementation for intersection computation. More...

#include <l_cpp/l_exception.h>
#include <qd_cpp/intersection.h>
#include <l/l_sys_lib.h>
#include <l/l_sys_io.h>
#include <l_cpp/l_util.h>
#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>

Namespaces
	kjb
	Classes and functions for dealing with trajectory files.
	kjb::qd
	support for the path algorithm I call the quasi-Dijkstra method.

Functions
std::vector< std::pair< size_t, size_t > >	kjb::qd::get_intersections (const PixPath &p, bool filter_out_trivial_intersections=true)
	return all intersections of polygonal path segments More...
std::vector< std::pair< size_t, size_t > >	kjb::qd::get_intersections (const std::vector< RatPoint_line_segment > &sl)

Detailed Description

Implementation for intersection computation.

Author

Andrew Predoehl In this file there's an implementation of the Bentley-Ottmann line intersection algorithm as presented by de Berg et al., Computational Geometry, 2nd ed., Springer (Berlin: 1997). This algorithm is in Chapter 2. Using the initials of the first names of these authors, I refer to their presentation by the abbreviation MMMO.