Space-efficient geometric algorithms and data structures

By Ilya Katz and Hervé Brönnimann    

intersection.hpp File Reference

Go to the source code of this file.

Namespaces

namespace  std
namespace  inplaceds

Data Structures

struct  PQComp
 CHANGE THIS VALUE TO INT MAX. More...
struct  kov
struct  BSTComp

Typedefs

typedef cgl< int > Geometry
typedef Geometry::line_type line_type
typedef Geometry::point_type point_type
typedef Geometry::coord_type coord_type
typedef DataNode< Geometry > node
typedef _Rb_tree< node *,
node *, kov< node * >, BSTComp<
Geometry > > 		tree_type
typedef priority_queue< node *,
vector< node * >, PQComp<
Geometry > > 		priority_queue_type

Functions

std::pair< bool, point_type > intersection (const line_type &l1, const line_type &l2)
 Function that finds the intersection of two line segments, or returns false if two line segments do no intersect.
void update_event (node *current, node *next, priority_queue_type &Q)
 Updates the event of the current node.
void intersection (vector< line_type > all_lines)
 Function that outputs intersections.
ostream & operator<< (ostream &os, node *x)

Variables

int SWEEP_LINE_COORD = -100

Typedef Documentation

typedef Geometry::coord_type coord_type
 

Definition at line 15 of file intersection.hpp.

typedef cgl<int> Geometry
 

Definition at line 12 of file intersection.hpp.

typedef Geometry::line_type line_type
 

Definition at line 13 of file intersection.hpp.

typedef DataNode<Geometry> node
 

Definition at line 16 of file intersection.hpp.

typedef Geometry::point_type point_type
 

Definition at line 14 of file intersection.hpp.

typedef priority_queue<node*, vector<node*>, PQComp<Geometry> > priority_queue_type
 

Definition at line 87 of file intersection.hpp.

typedef _Rb_tree<node*, node*, kov<node*>, BSTComp<Geometry> > tree_type
 

Definition at line 86 of file intersection.hpp.

Function Documentation

void intersection (  vector< line_type >  all_lines  ) 
 

Function that outputs intersections.

Parameters:
all_lines a vector that contains all line segments (possibly unsorted)

Definition at line 109 of file intersection.hpp.

std::pair< bool, point_type > intersection (  const line_type &  l1,
const line_type &  l2
) 
 

Function that finds the intersection of two line segments, or returns false if two line segments do no intersect.

Parameters:
l1 line segment of type line_type
l2 line segment of type line_type
Returns:
an std::pair, first attribute is true if lines intesect and otherwise. If line segments intersect, the second attribute contains their intersection point

Definition at line 260 of file intersection.hpp.

ostream& operator<< (  ostream &  os,
node *  x
) 
 

Definition at line 97 of file intersection.hpp.

void update_event (  node *  current,
node *  next,
priority_queue_type &  Q
) 
 

Updates the event of the current node.

Parameters:
current pointer to the current node
next pointer to the successor in the tree
Q referece to the queue of events
SHOULD IT BE > OR >=

Definition at line 232 of file intersection.hpp.

Variable Documentation

int SWEEP_LINE_COORD = -100
 

Definition at line 18 of file intersection.hpp.

Code Documentation generated Using Doxygen

Copyright © Ilya Katz and Hervé Brönnimann, 2005.