Class ThetaStar

Nested Relationships

Nested Types

Class Documentation

class ThetaStar

Implemetation of the Theta* algorithm.

Note

For vertex at coords x and y we mean the top-left vertex of the pixel at coords x and y.

Public Functions

inline ThetaStar()
inline void updateVertex(const tuple<int, int> s, const tuple<int, int> sNeighbor, const cv::Mat &map)

Update routine of the theta* algorigthm, updates the parent of the current neighbor to either the parent of the s vertex if it has line of sight or to the s vertex.

Note

Depends on gCost and mapImage

Parameters:

  • s – The vertex that is being currently expanded.

  • sNeighbor – The neighbor of s.

  • map – The occupancy map.

inline list<tuple<int, int>> thetaStar(const tuple<int, int> start, tuple<int, int> goal, const cv::Mat &map)

Main function of the theta* algorithm.

Note

Within the function we reverse the x and y coordinates of the vertices for compatability with the lineOfSight function. This detail should be ignored outside of the thetaStar function.

Parameters:

  • start – The start vertex.

  • goal – The goal vertex.

  • map – The occupancy map, binary image.

Returns:

list<tuple<int, int>> The path from the start vertex to the goal vertex, empty if not found.

Public Members

cv::Mat gCost
tuple<int, int> goalVert
unordered_map<tuple<int, int>, tuple<int, int>> parent
set<tuple<int, int>, Comparator> open
list<tuple<int, int>> closed
cv::Mat mapImage

Public Static Functions

static inline float hCost(const tuple<int, int> s, const tuple<int, int> goal)

Calculate straight-line distance between the vertex s and goal vertex, used as an estimation of the cost of the path between s and goal.

Parameters:

  • s – the vertex

  • goal – the goal vertex

Returns:

float

static inline bool lineOfSight(tuple<int, int> a, tuple<int, int> b, const cv::Mat &map)

Check for line of sight between two vertices.

Parameters:

  • a – The first vertex

  • b – The second vertex

  • map – The occupancy map.

Returns:

true If the vertex a has line of sight with vertex b.

Returns:

false If the vertex a does not have line of sight with vertex b.

static inline list<tuple<int, int>> neighbors(const tuple<int, int> s, const tuple<int, int> &mapSize)

Get all neighbors of a vertex (we consider an 8-connected space, so diagonal neighbors included).

Parameters:

  • s – Vertex

  • mapSize – The size of the map.

Returns:

list<tuple<int, int>> List of neighbors

static inline float straightLinecost(const tuple<int, int> a, const tuple<int, int> b)

Calculate the lenght of the straight line between two vertices, in pixels.

Parameters:

  • a – The first vertex.

  • b – The second vertex.

Returns:

float The distance between the two vertices as a straigth line in pixels.

class Comparator

Comparator class used to hold the vertices of the open set in ascending order based on their estimated distance from the goal.

Public Functions

inline Comparator()
inline Comparator(ThetaStar *ts_input)
inline bool operator()(tuple<int, int> l, tuple<int, int> r)