#include <vtol_cycle_processor.h>

Public Member Functions
	vtol_cycle_processor (vcl_vector< vtol_edge_2d_sptr > &edges, bool debug1=false, bool debug_2=false)
	vtol_cycle_processor (vcl_vector< vtol_edge * > &edges, bool debug1=false, bool debug_2=false)
	~vtol_cycle_processor ()
bool	nested_one_cycles (vcl_vector< vtol_one_chain_sptr > &one_chains, const float &tolerance=1e-03)
Static Public Member Functions
static bool	intersect_edges (vcl_vector< vtol_edge_sptr > &s1, vcl_vector< vtol_edge_sptr > &s2, vcl_vector< vtol_edge_sptr > &s1_and_s2)
	set operations on edges
static bool	difference_edges (vcl_vector< vtol_edge_sptr > &s1, vcl_vector< vtol_edge_sptr > &s2, vcl_vector< vtol_edge_sptr > &s1_minus_s2)
	This method scans the edge sets s1, s2 and computes their set difference.
static bool	corrupt_boundary (vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_sptr > &bad_verts)
	topology repair methods useful in forming cycles.
static bool	connect_paths (vcl_vector< vtol_edge_2d_sptr > &edges, vcl_vector< vtol_vertex_sptr > &bad_verts)
	Input is a set of edges that do not form cycles.
static double	angle_between_edges (vtol_edge_2d_sptr e0, vtol_edge_2d_sptr e1, vtol_vertex_sptr v)
	Compute the angle between two edges at the specified vtol_vertex, v.
Protected Member Functions
void	print_edge (vtol_edge_2d_sptr &e)
void	set_bridge_vars ()
	Initializes the search for cycles starting with an unexplored vtol_edge.
void	init (vcl_vector< vtol_edge_2d_sptr > &edges)
	The initial setup of the cycle process.
vtol_edge_2d_sptr	search_for_next_edge (vcl_vector< vtol_edge_2d_sptr > &edges_at_last)
	Search the set of vtol_edge(s) connected to the last path vertex for a suitable addition to the path.
bool	assignable (vtol_edge_2d_sptr edg, vtol_vertex_sptr last)
	Is an edge assignable to a path?.
void	assign_initial_edge (vtol_edge_2d_sptr &e, vtol_vertex_sptr &first, vtol_vertex_sptr &last)
	Set up the first edge in a cycle (or bridge) traversal.
void	assign_ends (vtol_edge_2d_sptr edg, vtol_vertex_sptr &last)
	Link the vtol_edge, "edg" to the vtol_vertex, "last".
void	add_edge_to_path ()
	A suitable vtol_edge is added to the evolving path.
bool	classify_path (vcl_vector< vtol_edge_2d_sptr > &path_edges, vtol_one_chain_sptr &chain)
	Classify a closed path as a cycle or bridge.
void	compute_cycles ()
	The main cycle tracing algorithm.
void	sort_one_cycles ()
	The input is a set of 1-cycles in chains_.
void	process ()
Protected Attributes
bool	debug1_
bool	debug2_
bool	valid_
float	tolerance_
bool	cycle_
bool	found_next_edge_
vtol_vertex_sptr	first_
vtol_vertex_sptr	last_
vtol_edge_2d_sptr	l_
vtol_edge_2d_sptr	next_edge_
vcl_vector< vtol_edge_2d_sptr >	edges_
vcl_vector< vtol_edge_2d_sptr >	e_stack_
vcl_vector< vtol_vertex_sptr >	v_stack_
vcl_vector< vtol_one_chain_sptr >	chains_
vcl_vector< vtol_one_chain_sptr >	nested_one_cycles_

Detailed Description

Definition at line 27 of file vtol_cycle_processor.h.

Constructor & Destructor Documentation

vtol_cycle_processor::vtol_cycle_processor	(	vcl_vector< vtol_edge_2d_sptr > &	edges,
		bool	debug1 = `false`,
		bool	debug_2 = `false`
	)

Definition at line 25 of file vtol_cycle_processor.cxx.

vtol_cycle_processor::vtol_cycle_processor	(	vcl_vector< vtol_edge * > &	edges,
		bool	debug1 = `false`,
		bool	debug_2 = `false`
	)

vtol_cycle_processor::~vtol_cycle_processor ( ) [inline]

Definition at line 34 of file vtol_cycle_processor.h.

Member Function Documentation

void vtol_cycle_processor::add_edge_to_path ( ) [protected]

A suitable vtol_edge is added to the evolving path.

Definition at line 588 of file vtol_cycle_processor.cxx.

double vtol_cycle_processor::angle_between_edges	(	vtol_edge_2d_sptr	e0,
		vtol_edge_2d_sptr	e1,
		vtol_vertex_sptr	v
	)		`[static]`

Compute the angle between two edges at the specified vtol_vertex, v.

The angle is mapped to the interval [-180, 180]. The angle sense is defined so that the e0 orientation is towards v and the e1 orientation is away from v.

Definition at line 318 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::assign_ends	(	vtol_edge_2d_sptr	edg,
		vtol_vertex_sptr &	last
	)		`[protected]`

Link the vtol_edge, "edg" to the vtol_vertex, "last".

Set the appropriate direction flag

Definition at line 443 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::assign_initial_edge	(	vtol_edge_2d_sptr &	e,
		vtol_vertex_sptr &	first,
		vtol_vertex_sptr &	last
	)		`[protected]`

Set up the first edge in a cycle (or bridge) traversal.

A positive traversal (half edge) is in the direction from v1->v2. Self loops are a special case and use both directions on one traversal. There is no point in traversing the self loop twice.

Definition at line 399 of file vtol_cycle_processor.cxx.

bool vtol_cycle_processor::assignable	(	vtol_edge_2d_sptr	edg,
		vtol_vertex_sptr	last
	)		`[protected]`

Is an edge assignable to a path?.

"Assignable" is defined by the condition that an edge has not already been traversed in the required direction. That is, if a traversal from s to e, (V1 to V2) has occurred then dir1 is true. A second traversal is not allowed and the edge is considered un-assignable.

Definition at line 368 of file vtol_cycle_processor.cxx.

bool vtol_cycle_processor::classify_path	(	vcl_vector< vtol_edge_2d_sptr > &	path_edges,
		vtol_one_chain_sptr &	chain
	)		`[protected]`

Classify a closed path as a cycle or bridge.

The path traverse is reversed since the vtol_edge sequence was popped from the path stack. Thus, the winding angle is opposite in sign, which is accounted for in code.

Definition at line 618 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::compute_cycles ( ) [protected]

The main cycle tracing algorithm.

The input is edges_ and the output is chains_, a set of 1-cycles. The approach is to select a vtol_edge from edges_ and explore all the vtol_edge(s) connected to it. The search proceeds by traversing connected vtol_edge(s), turning in a cw or ccw direction depending on the initial vtol_edge orientation. If the search returns to a vertex already on the path, then a cycle is output. The traversed vtol_edge(s) and vertices are pushed onto a stack so that cycles can be "popped" off and the search continued from a proper state. Each vtol_edge can be traversed in a plus or minus direction (2 half_edges). Thus boundaries might be traced twice producing identical cycles but traversed in opposite senses.

Bridges are detected by the fact that all vtol_edge(s) in the bridge are used(plus and minus) and the traversal winding angle is 180 deg, i.e., the path folds exactly back on itself.

Cycles are labeled according to the accumulated winding angle in traversing the cycle. If the accumulated angle is + then the cycle is ccw, otherwise cw. Here, the winding angle is defined as the exterior angle between two sequential vtol_edge(s) in the traversed path.

In the traversal, completely unused vtol_edge(s) are favored to continue in an unexplored path. If none are available then the bool, force, is set and the remaining half_edge is used, retracing a previous path in the opposite direction.

Definition at line 720 of file vtol_cycle_processor.cxx.

bool vtol_cycle_processor::connect_paths	(	vcl_vector< vtol_edge_2d_sptr > &	edges,
		vcl_vector< vtol_vertex_sptr > &	bad_verts
	)		`[static]`

Input is a set of edges that do not form cycles.

There is a set of vertices that represent the unconnected endpoints of a set of paths. Two endpoints can be connected if there exists an edge between them that is not included in the input set of edges.

Definition at line 1123 of file vtol_cycle_processor.cxx.

bool vtol_cycle_processor::corrupt_boundary	(	vcl_vector< vtol_edge_2d_sptr > &	edges,
		vcl_vector< vtol_vertex_sptr > &	bad_verts
	)		`[static]`

topology repair methods useful in forming cycles.

mark all vertices as used if they are incident on exactly two edges.

Vertices that are not incident two edges are output in the vector, bad_verts.

Definition at line 1030 of file vtol_cycle_processor.cxx.

bool vtol_cycle_processor::difference_edges	(	vcl_vector< vtol_edge_sptr > &	s1,
		vcl_vector< vtol_edge_sptr > &	s2,
		vcl_vector< vtol_edge_sptr > &	s1_minus_s2
	)		`[static]`

This method scans the edge sets s1, s2 and computes their set difference.

i.e, s1 with any edges also in s2 removed. If the difference is empty then the method returns false. The method uses flags to mark edges appearing in both lists. Thus the computation is O(n1+n2).

This method might not be needed if stl algorithms worked ("old" vcl probs) however with flags this might be faster than stl

Definition at line 990 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::init ( vcl_vector< vtol_edge_2d_sptr > & in_edges ) [protected]

The initial setup of the cycle process.

Used by the vtol_cycle_processor constructors to establish the start conditions

Definition at line 490 of file vtol_cycle_processor.cxx.

bool vtol_cycle_processor::intersect_edges	(	vcl_vector< vtol_edge_sptr > &	s1,
		vcl_vector< vtol_edge_sptr > &	s2,
		vcl_vector< vtol_edge_sptr > &	s1_and_s2
	)		`[static]`

set operations on edges

This method scans the edge sets s1, s2 and computes their set intersection.

If the intersection is empty then the method returns false. The method uses flags to mark edges appearing in both lists. Thus the computation is O(n1+n2).

This method might not be needed if stl algorithms worked ("old" vcl probs) however with flags this might be faster than stl

Definition at line 943 of file vtol_cycle_processor.cxx.

bool vtol_cycle_processor::nested_one_cycles	(	vcl_vector< vtol_one_chain_sptr > &	one_chains,
		const float &	tolerance = `1e-03`
	)

Definition at line 907 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::print_edge ( vtol_edge_2d_sptr & e ) [protected]

Definition at line 684 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::process ( ) [protected]

Definition at line 900 of file vtol_cycle_processor.cxx.

vtol_edge_2d_sptr vtol_cycle_processor::search_for_next_edge ( vcl_vector< vtol_edge_2d_sptr > & edges_at_last ) [protected]

Search the set of vtol_edge(s) connected to the last path vertex for a suitable addition to the path.

Definition at line 568 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::set_bridge_vars ( ) [protected]

Initializes the search for cycles starting with an unexplored vtol_edge.

This initialization is called after a connected set of vtol_edge(s) is completely explored and removed from edges_.

Definition at line 509 of file vtol_cycle_processor.cxx.

void vtol_cycle_processor::sort_one_cycles ( ) [protected]

The input is a set of 1-cycles in chains_.

These cycles are sorted so that they form a proper containment relation. That is, there is one outer cycle, with traversal in the ccw direction and zero or more interior hole boundaries with traversal in the cw direction. All other cycles are removed. The output is nested_one_cycles_.

Definition at line 822 of file vtol_cycle_processor.cxx.