Polygon decomposition and traversal algorithm structs and functions. Implements the greedy recursive approach using minimum width sum outlined in a paper by Yan Li et al. All units are in meters. More...

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <string>
#include <sstream>
#include <fstream>
#include <assert.h>
#include <cfloat>
#include <utility>
#include "Graph.cpp"
#include "Config.h"

Classes
struct	Coord
	Simple representation of a 2D coordinate. More...

struct	Edge
	Simple representation of an edge. More...

struct	Span
	Representation of a span in Vertex-Edge form. More...

struct	Polygon
	Represents a polygon as a list of vertices in CCW order. More...

struct	Node
	Node class for weighted graph. Consists of the search path for the polygon, a pointer to the polygon, and the start state. More...

struct	Comp

Macros
#define	PI 3.14159265358979323846
	Approximate value for pi.

#define	INF 1000000
	An effective infinity that will not overflow the float type. More...

Enumerations
enum	State { START_V1, START_V2, END_V1, END_V2 }
	State representing which vertex we start the path from. START_V1 = start at vertex 1 of starting edge START_V2 = start at vertex 2 of starting edge END_V1 = start at vertex 1 of end edge END_V2 = start at vertex 2 of end edge.

Functions
float_type	distance (const Coord &v1, const Coord &v2)
	Find the distance between two vertices. More...

float_type	distance (const Coord &v, const Edge &e)
	Find the distance between a vertex and an edge. More...

Span	getWidth (const Polygon &p)
	Find the width of a convex polygon. More...

bool	isConcave (const Polygon &p, int i)
	Determine if a given vertex of a polygon is concave. More...

void	split (const Polygon &p, int v1, int v2, Polygon &p1, Polygon &p2)
	Splits a polygon into two along an edge. More...

void	decompose (const Polygon &p, std::list< Polygon > &l)
	Decompose a concave polygon into multiple convex polygons. More...

Polygon	merge (const Polygon &p1, const Polygon &p2, unsigned int i, unsigned int j)
	Merge two polygons by their shared edge given the edge's index in each polygon and return the result. More...

void	mergeSubregions (std::list< Polygon > &l)
	Combine applicable subregions after decomposition. More...

float_type	cross (const Coord &c1, const Coord &c2)
	Calculate the cross product of two vectors represented as coordinates. More...

bool	intersection (const Edge &e1, const Edge &e2, Coord &intersect)
	Find the intersection of two line segments. More...

void	traverse (const Polygon &p, std::list< Edge > &waypoints)
	Traverse a convex polygon and store the waypoints in a list as Edges. More...

void	computeGraph (Graph< Node, float_type > &g)
	Helper function to compute the adjacencies and weights of the graph. More...

float_type	traversalLength (const Graph< Node, float_type > &g, std::list< unsigned int > &path)
	Compute the total length of a graph traversal. More...

std::list< unsigned int >	minTraversal (Graph< Node, float_type > &g)
	Compute the minimum cost traversal for the weighted graph. More...

void	computeStates (std::list< unsigned int > &path, Graph< Node, float_type > &g)
	Determine the start states of each node along the traversal. More...

std::list< Coord >	searchPath (const Polygon &p)
	Generates the search path for a polygon. More...

bool	clockwise (const std::vector< Coord > &v)
	Determine if the list of coordinates are in clockwise order. More...

std::list< Coord >	pathTo (const Coord &point1, const Coord &point2, const Polygon &boundary)
	Computes a path from one point to another that does not intersect the boundary polygon. Assumes both points are inside the boundary polygon. More...

void	naiveTraverse (const Polygon &p, std::list< Edge > &waypoints)
	Traverse the polygon using a simple parallel traversal. More...

std::list< Coord >	naivePath (const Polygon &p)
	Generates a search path for a polygon using naive traversal. More...

void	pathToHelp (std::list< Coord > &path, std::list< Coord >::iterator point1, std::list< Coord >::iterator point2, const Polygon &boundary)

Detailed Description

Polygon decomposition and traversal algorithm structs and functions. Implements the greedy recursive approach using minimum width sum outlined in a paper by Yan Li et al. All units are in meters.

Author: Harvey Lin

Macro Definition Documentation

◆ INF

#define INF 1000000

An effective infinity that will not overflow the float type.

See also: float_type

Function Documentation

◆ clockwise()

bool clockwise ( const std::vector< Coord > & v )

Determine if the list of coordinates are in clockwise order.

Parameters

v	the list of coordinates

Returns: true if coordinates are clockwise, else false

See also: Coord

◆ computeGraph()

void computeGraph ( Graph< Node, float_type > & g )

Helper function to compute the adjacencies and weights of the graph.

Parameters

g	the graph to compute

See also: Graph

◆ computeStates()

void computeStates	(	std::list< unsigned int > &	path,
		Graph< Node, float_type > &	g
	)

Determine the start states of each node along the traversal.

Parameters

path	the traversal
g	the weighted graph

See also: State

◆ cross()

float_type cross	(	const Coord &	c1,
		const Coord &	c2
	)

inline

Calculate the cross product of two vectors represented as coordinates.

Parameters

c1	the first vector as a coordinate
c2	the second vector as a coordinate

Returns: the cross product

See also: Coord float_type

◆ decompose()

void decompose	(	const Polygon &	p,
		std::list< Polygon > &	l
	)

Decompose a concave polygon into multiple convex polygons.

Parameters

p	the polygon
l	stores the resulting list of polygons

Returns: resulting polygons are stored in l

See also: Polygon

◆ distance() [1/2]

float_type distance	(	const Coord &	v,
		const Edge &	e
	)

Find the distance between a vertex and an edge.

Parameters

v	the vertex
e	the edge

Returns: the distance between the vertex and edge

See also: Coord Edge float_type

◆ distance() [2/2]

float_type distance	(	const Coord &	v1,
		const Coord &	v2
	)

Find the distance between two vertices.

Parameters

v1	the first vertex
v2	the second vertex

Returns: the distance between the two vertices

See also: Coord float_type

◆ getWidth()

Span getWidth ( const Polygon & p )

Find the width of a convex polygon.

Parameters

p	the polygon

Returns: the width of the polygon as a span

See also: Span Polygon

◆ intersection()

bool intersection	(	const Edge &	e1,
		const Edge &	e2,
		Coord &	intersect
	)

Find the intersection of two line segments.

Parameters

e1	the first line segment as an edge
e2	the second line segment as an edge
intersect	stores the intersection if one exists

Returns: returns true and stores result in intersect if intersection exists, else returns false

See also: Coord Edge

◆ isConcave()

bool isConcave	(	const Polygon &	p,
		int	i
	)

Determine if a given vertex of a polygon is concave.

Parameters

p	the polygon
i	index of the vertex

Returns: true if the vertex is concave, else false

See also: Polygon

◆ merge()

Polygon merge	(	const Polygon &	p1,
		const Polygon &	p2,
		unsigned int	i,
		unsigned int	j
	)

Merge two polygons by their shared edge given the edge's index in each polygon and return the result.

Parameters

p1	the first polygon
p2	the second polygon
i	index of the shared edge in p1
j	index of the shared edge in p2

Returns: the merged polygon

See also: Polygon

◆ mergeSubregions()

void mergeSubregions ( std::list< Polygon > & l )

Combine applicable subregions after decomposition.

Parameters

l	list of decomposed polygon subregions

See also: Polygon decompose

◆ minTraversal()

std::list< unsigned int > minTraversal ( Graph< Node, float_type > & g )

Compute the minimum cost traversal for the weighted graph.

Parameters

g	the weighted graph

Returns: the minimum cost traversal as a list of node indeces

See also: Graph

◆ naivePath()

std::list< Coord > naivePath ( const Polygon & p )

Generates a search path for a polygon using naive traversal.

Parameters

p	the polygon

Returns: the search path as a list of Coords

See also: Coord Polygon naiveTraverse

◆ naiveTraverse()

void naiveTraverse	(	const Polygon &	p,
		std::list< Edge > &	waypoints
	)

Traverse the polygon using a simple parallel traversal.

Parameters

p	the polygon
waypoints	stores the resulting waypoints of the traversal

Returns: resulting traversal is stored in waypoints

See also: Polygon Edge

◆ pathTo()

std::list< Coord > pathTo	(	const Coord &	point1,
		const Coord &	point2,
		const Polygon &	boundary
	)

Computes a path from one point to another that does not intersect the boundary polygon. Assumes both points are inside the boundary polygon.

Parameters

point1	the first point
point2	the second point
boundary	the boundary polygon

Returns: the path as a list of Coords

See also: Coord Polygon

◆ searchPath()

std::list< Coord > searchPath ( const Polygon & p )

Generates the search path for a polygon.

Parameters

p	the polygon

Returns: the search path as a list of Coords

See also: Coord

◆ split()

void split	(	const Polygon &	p,
		int	v1,
		int	v2,
		Polygon &	p1,
		Polygon &	p2
	)

Splits a polygon into two along an edge.

Parameters

p	the polygon
v1	first vertex of edge
v2	second vertex of edge
p1	stores the first resulting polygon
p2	stores the second resulting polygon

Returns: resulting polygons are stored in p1 and p2

See also: Polygon

◆ traversalLength()

float_type traversalLength	(	const Graph< Node, float_type > &	g,
		std::list< unsigned int > &	path
	)

Compute the total length of a graph traversal.

Parameters

g	the weighted graph
path	the traversal path

Returns: the total length of the traversal

See also: Graph float_type

◆ traverse()

void traverse	(	const Polygon &	p,
		std::list< Edge > &	waypoints
	)

Traverse a convex polygon and store the waypoints in a list as Edges.

Parameters

p	the polygon to traverse
waypoints	list to store the traversal

See also: Polygon Edge

Classes

Macros

Enumerations

Functions

Detailed Description

Macro Definition Documentation

◆ INF

Function Documentation

◆ clockwise()

◆ computeGraph()

◆ computeStates()

◆ cross()

◆ decompose()

◆ distance() [1/2]

◆ distance() [2/2]

◆ getWidth()

◆ intersection()

◆ isConcave()

◆ merge()

◆ mergeSubregions()

◆ minTraversal()

◆ naivePath()

◆ naiveTraverse()

◆ pathTo()

◆ searchPath()

◆ split()

◆ traversalLength()

◆ traverse()