![]() |
Performs cycle detection on the cross section, used for determination of cells during thin-wall analysis. More...
#include <CycleDetection.h>
Public Types | |
typedef std::pair< int, int > | Edge |
Defining an Edge to consist of to vertices (start and end) in the format of int's. | |
Public Member Functions | |
CycleDetection (std::vector< LineElement * > elements) | |
Constructor. More... | |
void | constructGraph (std::vector< LineElement * > element) |
Creates graph from the elements provided. More... | |
void | findAllCycles () |
Finds all cells in a cross-section without duplicates. Calls findNewCycle() from all the nodes in the cross-section, in order to ensure that all cells are found. | |
void | findNewCycles (std::vector< int > path) |
Finds new cells not previously found, and stores them as a vector of nodes. More... | |
void | convertCyclesToEdges () |
Converts the cycles from storing nodes, to storing edges. More... | |
void | removeSuperCycles () |
Removes all cycles containing other (smaller) cycles. | |
void | sortCycles () |
Sorts cycles vector from largest cycles to the smallest cycles. More... | |
void | convertEdgesToElements (std::vector< LineElement * > elements) |
Converts the edges in cycles, to their corresponding elements. More... | |
void | printCells () |
Prints all the cells found. More... | |
void | calculateCellArea () |
Calculates the area of each cell. More... | |
void | printEdgeCycles (std::vector< std::vector< Edge >> edges) |
Prints cycles and their edges. More... | |
void | reverseCycle (int i) |
Reverses the cycle. More... | |
bool | equals (std::vector< int > a, std::vector< int > b) |
Determines if two vectors are equal, i.e contains the same nodes in the same order. More... | |
bool | isNew (std::vector< int > path) |
Determines if a cycle is not discovered. More... | |
bool | visited (int n, std::vector< int > path) |
Checks if node n is part of the path. More... | |
int | findSmallestElement (std::vector< int > path) |
Finds the smallest element in path. More... | |
std::vector< std::vector< LineElement * > > | getAllCycles () |
Gets all cells that have been detected. More... | |
std::vector< LineElement * > | getOpenElements (std::vector< LineElement * > elements) |
Gets all open elements. More... | |
std::vector< int > | invert (std::vector< int > path) |
Inverts a path. More... | |
std::vector< int > | normalize (std::vector< int > path) |
Rotates path so the smallest node is listed first. More... | |
Public Attributes | |
std::vector< std::vector< int > > | cycles |
Vector containing cycles in vertex form. | |
std::vector< std::vector< int > > | graph |
Graph that is created from vertices and edges. | |
std::vector< std::vector< LineElement * > > | elementCycles |
Vector containing only the line elements that are a part of a cell (sub-cycle) | |
std::vector< std::vector< Edge > > | edges |
Vector containing edges. | |
std::vector< double > | cycleArea |
Vector containing the areas of all the cycles not containing other cycles. | |
Performs cycle detection on the cross section, used for determination of cells during thin-wall analysis.
CycleDetection::CycleDetection | ( | std::vector< LineElement * > | elements | ) |
Constructor.
Takes a vector of all the LineElement pointers in the mesh and performs cycle detection on them based on depth first search.
elements | is a vector of all LineElement pointers in the mesh. |
void CycleDetection::calculateCellArea | ( | ) |
Calculates the area of each cell.
In order to find shear flow, the area of each cell is needed. The area of irregular polygons is found using the method described at https://www.mathsisfun.com/geometry/area-irregular-polygons.html
void CycleDetection::constructGraph | ( | std::vector< LineElement * > | element | ) |
Creates graph from the elements provided.
element | vectorcontaining all elements in cross-section |
void CycleDetection::convertCyclesToEdges | ( | ) |
Converts the cycles from storing nodes, to storing edges.
The cycles need to be defined in terms of edges rather than nodes in order for the removeSuperCycle() algorithm to work
void CycleDetection::convertEdgesToElements | ( | std::vector< LineElement * > | elements | ) |
Converts the edges in cycles, to their corresponding elements.
Each edge is matched up with it's corresponding LineElement from the cross-section. i.e std::vector<std::vector<Edge>> becomes std::vector<std::vector<LineElement*>>
elements | vector containing pointers to all LineElements |
bool CycleDetection::equals | ( | std::vector< int > | a, |
std::vector< int > | b | ||
) |
Determines if two vectors are equal, i.e contains the same nodes in the same order.
Used in findNewCycles() to avoid adding already discovered cells
a | vector to check for equality |
b | vector to checkfor equality |
void CycleDetection::findNewCycles | ( | std::vector< int > | path | ) |
Finds new cells not previously found, and stores them as a vector of nodes.
The cycle detection algorithm is based on a recursive depth first search. A cycle is detected when a backedge is found i.e the tree loops back to a visited node (the current path needs to be longer than 2, as a cycle by defenition needs at least three nodes).
path | vector containing the start of a path (one node) |
int CycleDetection::findSmallestElement | ( | std::vector< int > | path | ) |
Finds the smallest element in path.
path | path to be checked |
std::vector< std::vector< LineElement * > > CycleDetection::getAllCycles | ( | ) |
Gets all cells that have been detected.
std::vector< LineElement * > CycleDetection::getOpenElements | ( | std::vector< LineElement * > | elements | ) |
Gets all open elements.
Open elements are elements not part of any cycle
std::vector< int > CycleDetection::invert | ( | std::vector< int > | path | ) |
Inverts a path.
Used to prevent findNewCycle() from adding inverse cycles
path | path to be inverted |
bool CycleDetection::isNew | ( | std::vector< int > | path | ) |
Determines if a cycle is not discovered.
path | a cycle described as a vector of nodes |
std::vector< int > CycleDetection::normalize | ( | std::vector< int > | path | ) |
Rotates path so the smallest node is listed first.
path | path to be normalized |
void CycleDetection::printCells | ( | ) |
Prints all the cells found.
Helper method used for debugging
void CycleDetection::printEdgeCycles | ( | std::vector< std::vector< Edge >> | edges | ) |
Prints cycles and their edges.
Used for debugging and verification
void CycleDetection::reverseCycle | ( | int | i | ) |
Reverses the cycle.
i | used to identify the cycle cycle[i][x] gives the i'th cycle |
void CycleDetection::sortCycles | ( | ) |
Sorts cycles vector from largest cycles to the smallest cycles.
After sort, the cycles will show up as:
Cycle1: (x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5), (x6, y6)
Cycle2: (x1, y1), (x2, y2), (x3, y3), (x4, y4)
Cycle3: (x1, y1), (x2, y2), (x3, y3)
bool CycleDetection::visited | ( | int | n, |
std::vector< int > | path | ||
) |
Checks if node n is part of the path.
n | node |
path | path to be checked |