Simple doubly-connected edge list structure. More...

#include <DoublyConnectedEdgeList.h>

Inheritance diagram for MapGen::DoublyConnectedEdgeList:

Collaboration diagram for MapGen::DoublyConnectedEdgeList:

Classes
struct	Face

struct	HalfEdge

struct	Node

Public Types
using	ConstFaceIterator = typename FaceContainer::const_iterator

using	ConstHalfEdgeIterator = typename HalfEdgeContainer::const_iterator

using	ConstNodeIterator = typename NodeContainer::const_iterator

using	FaceContainer = std::list< Face >

using	FaceIterator = typename FaceContainer::iterator

using	HalfEdgeContainer = std::list< HalfEdge >

using	HalfEdgeIterator = typename HalfEdgeContainer::iterator

using	NodeContainer = std::list< Node >

using	NodeIterator = typename NodeContainer::iterator

using	Position = MapGen::Position< int32 >

Public Member Functions
	DoublyConnectedEdgeList (const Position &Position0, const Position &Position1)
	Create a DoublyConnectedEdgeList with two nodes, two edges and one face. More...

template<size_t N>
	DoublyConnectedEdgeList (const std::array< Position, N > &Cycle)
	Create a DoublyConnectedEdgeList consisting of a cycle of N nodes. More...

	~DoublyConnectedEdgeList ()

Adding elements to the graph -------------------------------------
Node &	AddNode (const Position &NodePosition, Node &OtherNode)
	{ More...

Node &	SplitEdge (const Position &Position, HalfEdge &HalfEdge)
	Split HalfEdge (and its pair) at Position. More...

Face &	ConnectNodes (Node &Node0, Node &Node1)
	Connect two nodes by a pair of edges. More...

Counting graph elements ------------------------------------------
size_t	CountNodes () const

size_t	CountHalfEdges () const

size_t	CountFaces () const

Accessing graph elements -----------------------------------------
ListView< NodeIterator >	GetNodes ()

ListView< ConstNodeIterator >	GetNodes () const

ListView< HalfEdgeIterator >	GetHalfEdges ()

ListView< ConstHalfEdgeIterator >	GetHalfEdges () const

ListView< FaceIterator >	GetFaces ()

ListView< ConstFaceIterator >	GetFaces () const

Static Public Member Functions
Accessing graph pointers -----------------------------------------
static Node &	GetSource (HalfEdge &halfEdge)

static const Node &	GetSource (const HalfEdge &halfEdge)

static Node &	GetTarget (HalfEdge &halfEdge)

static const Node &	GetTarget (const HalfEdge &halfEdge)

static HalfEdge &	GetPair (HalfEdge &halfEdge)

static const HalfEdge &	GetPair (const HalfEdge &halfEdge)

static Face &	GetFace (HalfEdge &halfEdge)

static const Face &	GetFace (const HalfEdge &halfEdge)

static HalfEdge &	GetLeavingHalfEdge (Node &node)

static const HalfEdge &	GetLeavingHalfEdge (const Node &node)

static HalfEdge &	GetHalfEdge (Face &face)

static const HalfEdge &	GetHalfEdge (const Face &face)

static HalfEdge &	GetNextInFace (HalfEdge &halfEdge)

static const HalfEdge &	GetNextInFace (const HalfEdge &halfEdge)

static HalfEdge &	GetNextInNode (HalfEdge &halfEdge)

static const HalfEdge &	GetNextInNode (const HalfEdge &halfEdge)

Other member functions -------------------------------------------
static float	GetAngle (const HalfEdge &halfEdge)
	Return the angle [-pi, pi] of the half-edge. More...

Private Attributes
FaceContainer	Faces

HalfEdgeContainer	HalfEdges

NodeContainer	Nodes

Additional Inherited Members
Private Member Functions inherited from NonCopyable
	NonCopyable ()=default

	NonCopyable (const NonCopyable &)=delete

void	operator= (const NonCopyable &)=delete

Detailed Description

Simple doubly-connected edge list structure.

It only allows adding elements, not removing them.

Definition at line 20 of file DoublyConnectedEdgeList.h.

Member Typedef Documentation

◆ ConstFaceIterator

using MapGen::DoublyConnectedEdgeList::ConstFaceIterator = typename FaceContainer::const_iterator

Definition at line 86 of file DoublyConnectedEdgeList.h.

◆ ConstHalfEdgeIterator

using MapGen::DoublyConnectedEdgeList::ConstHalfEdgeIterator = typename HalfEdgeContainer::const_iterator

Definition at line 82 of file DoublyConnectedEdgeList.h.

◆ ConstNodeIterator

using MapGen::DoublyConnectedEdgeList::ConstNodeIterator = typename NodeContainer::const_iterator

Definition at line 78 of file DoublyConnectedEdgeList.h.

◆ FaceContainer

using MapGen::DoublyConnectedEdgeList::FaceContainer = std::list<Face>

Definition at line 84 of file DoublyConnectedEdgeList.h.

◆ FaceIterator

using MapGen::DoublyConnectedEdgeList::FaceIterator = typename FaceContainer::iterator

Definition at line 85 of file DoublyConnectedEdgeList.h.

◆ HalfEdgeContainer

using MapGen::DoublyConnectedEdgeList::HalfEdgeContainer = std::list<HalfEdge>

Definition at line 80 of file DoublyConnectedEdgeList.h.

◆ HalfEdgeIterator

using MapGen::DoublyConnectedEdgeList::HalfEdgeIterator = typename HalfEdgeContainer::iterator

Definition at line 81 of file DoublyConnectedEdgeList.h.

◆ NodeContainer

using MapGen::DoublyConnectedEdgeList::NodeContainer = std::list<Node>

Definition at line 76 of file DoublyConnectedEdgeList.h.

◆ NodeIterator

using MapGen::DoublyConnectedEdgeList::NodeIterator = typename NodeContainer::iterator

Definition at line 77 of file DoublyConnectedEdgeList.h.

◆ Position

using MapGen::DoublyConnectedEdgeList::Position = MapGen::Position<int32>

Definition at line 28 of file DoublyConnectedEdgeList.h.

Constructor & Destructor Documentation

◆ DoublyConnectedEdgeList() [1/2]

MapGen::DoublyConnectedEdgeList::DoublyConnectedEdgeList	(	const Position &	Position0,
		const Position &	Position1
	)

explicit

Create a DoublyConnectedEdgeList with two nodes, two edges and one face.

Definition at line 74 of file DoublyConnectedEdgeList.cpp.

References Faces, HalfEdges, and Nodes.

◆ DoublyConnectedEdgeList() [2/2]

template<size_t N>

MapGen::DoublyConnectedEdgeList::DoublyConnectedEdgeList ( const std::array< Position, N > & Cycle )

inlineexplicit

Create a DoublyConnectedEdgeList consisting of a cycle of N nodes.

Definition at line 99 of file DoublyConnectedEdgeList.h.

◆ ~DoublyConnectedEdgeList()

MapGen::DoublyConnectedEdgeList::~DoublyConnectedEdgeList ( )

Definition at line 102 of file DoublyConnectedEdgeList.cpp.

Member Function Documentation

◆ AddNode()

DoublyConnectedEdgeList::Node & MapGen::DoublyConnectedEdgeList::AddNode	(	const Position &	NodePosition,
		Node &	OtherNode
	)

{

Add a node at NodePosition and attach it to OtherNode.

The time complexity is O(n*log(n)) where n is the number of edges leaving OtherNode.

Returns: The newly generated node.

Definition at line 113 of file DoublyConnectedEdgeList.cpp.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Face, MapGen::FindPositionInNode(), HalfEdges, MapGen::DoublyConnectedEdgeList::HalfEdge::Next, Nodes, and MapGen::DoublyConnectedEdgeList::HalfEdge::Pair.

Here is the call graph for this function:

◆ ConnectNodes()

DoublyConnectedEdgeList::Face & MapGen::DoublyConnectedEdgeList::ConnectNodes	(	Node &	Node0,
		Node &	Node1
	)

Connect two nodes by a pair of edges.

It is assumed that both nodes are connected by the same face.

The time complexity is O(n0*log(n0) + n1*log(n1) + nf) where n0 and n1 are the number of edges leaving Node0 and Node1 respectively, and nf is the number of edges in the face containing both nodes.

Returns: The newly generated face.

Definition at line 194 of file DoublyConnectedEdgeList.cpp.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Face, Faces, MapGen::FindPositionInNode(), GetHalfEdge(), GetNextInFace(), MapGen::DoublyConnectedEdgeList::Face::HalfEdge, HalfEdges, MapGen::DoublyConnectedEdgeList::HalfEdge::Next, and MapGen::DoublyConnectedEdgeList::HalfEdge::Pair.

Referenced by MapGen::splitFace().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CountFaces()

size_t MapGen::DoublyConnectedEdgeList::CountFaces ( ) const

inline

Definition at line 161 of file DoublyConnectedEdgeList.h.

Referenced by MapGen::GraphParser::GraphParser(), and MapGen::randomize().

Here is the caller graph for this function:

◆ CountHalfEdges()

size_t MapGen::DoublyConnectedEdgeList::CountHalfEdges ( ) const

inline

Definition at line 156 of file DoublyConnectedEdgeList.h.

Referenced by MapGen::GraphParser::GraphParser(), and MapGen::randomize().

Here is the caller graph for this function:

◆ CountNodes()

size_t MapGen::DoublyConnectedEdgeList::CountNodes ( ) const

inline

Definition at line 151 of file DoublyConnectedEdgeList.h.

Referenced by MapGen::GraphParser::GraphParser(), and MapGen::randomize().

Here is the caller graph for this function:

◆ GetAngle()

float MapGen::DoublyConnectedEdgeList::GetAngle ( const HalfEdge & halfEdge )

static

Return the angle [-pi, pi] of the half-edge.

Definition at line 250 of file DoublyConnectedEdgeList.cpp.

References GetFace(), GetFaces(), GetHalfEdge(), GetHalfEdges(), GetLeavingHalfEdge(), GetNextInFace(), GetNextInNode(), GetNodes(), MapGen::DoublyConnectedEdgeList::Node::GetPosition(), GetSource(), and GetTarget().

Referenced by MapGen::FindPositionInNode(), and MapGen::fixGraphData().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetFace() [1/2]

static Face& MapGen::DoublyConnectedEdgeList::GetFace ( HalfEdge & halfEdge )

inlinestatic

Definition at line 248 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Face.

Referenced by GetAngle().

Here is the caller graph for this function:

◆ GetFace() [2/2]

static const Face& MapGen::DoublyConnectedEdgeList::GetFace ( const HalfEdge & halfEdge )

inlinestatic

Definition at line 254 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Face.

◆ GetFaces() [1/2]

ListView<FaceIterator> MapGen::DoublyConnectedEdgeList::GetFaces ( )

inline

Definition at line 193 of file DoublyConnectedEdgeList.h.

Referenced by GetAngle(), MapGen::GraphParser::GraphParser(), and MapGen::randomize().

Here is the caller graph for this function:

◆ GetFaces() [2/2]

ListView<ConstFaceIterator> MapGen::DoublyConnectedEdgeList::GetFaces ( ) const

inline

Definition at line 198 of file DoublyConnectedEdgeList.h.

◆ GetHalfEdge() [1/2]

static HalfEdge& MapGen::DoublyConnectedEdgeList::GetHalfEdge ( Face & face )

inlinestatic

Definition at line 272 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::Face::HalfEdge.

Referenced by ConnectNodes(), GetAngle(), MapGen::getRandomOpposingEdges(), and MapGen::GraphParser::GraphParser().

Here is the caller graph for this function:

◆ GetHalfEdge() [2/2]

static const HalfEdge& MapGen::DoublyConnectedEdgeList::GetHalfEdge ( const Face & face )

inlinestatic

Definition at line 278 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::Face::HalfEdge.

◆ GetHalfEdges() [1/2]

ListView<HalfEdgeIterator> MapGen::DoublyConnectedEdgeList::GetHalfEdges ( )

inline

Definition at line 183 of file DoublyConnectedEdgeList.h.

Referenced by GetAngle().

Here is the caller graph for this function:

◆ GetHalfEdges() [2/2]

ListView<ConstHalfEdgeIterator> MapGen::DoublyConnectedEdgeList::GetHalfEdges ( ) const

inline

Definition at line 188 of file DoublyConnectedEdgeList.h.

◆ GetLeavingHalfEdge() [1/2]

static HalfEdge& MapGen::DoublyConnectedEdgeList::GetLeavingHalfEdge ( Node & node )

inlinestatic

Definition at line 260 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::Node::LeavingHalfEdge.

Referenced by MapGen::fixGraphData(), and GetAngle().

Here is the caller graph for this function:

◆ GetLeavingHalfEdge() [2/2]

static const HalfEdge& MapGen::DoublyConnectedEdgeList::GetLeavingHalfEdge ( const Node & node )

inlinestatic

Definition at line 266 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::Node::LeavingHalfEdge.

◆ GetNextInFace() [1/2]

static HalfEdge& MapGen::DoublyConnectedEdgeList::GetNextInFace ( HalfEdge & halfEdge )

inlinestatic

Definition at line 286 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Next.

Referenced by ConnectNodes(), GetAngle(), MapGen::getRandomOpposingEdges(), and MapGen::GraphParser::GraphParser().

Here is the caller graph for this function:

◆ GetNextInFace() [2/2]

static const HalfEdge& MapGen::DoublyConnectedEdgeList::GetNextInFace ( const HalfEdge & halfEdge )

inlinestatic

Definition at line 292 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Next.

◆ GetNextInNode() [1/2]

static HalfEdge& MapGen::DoublyConnectedEdgeList::GetNextInNode ( HalfEdge & halfEdge )

inlinestatic

Definition at line 298 of file DoublyConnectedEdgeList.h.

Referenced by MapGen::fixGraphData(), and GetAngle().

Here is the caller graph for this function:

◆ GetNextInNode() [2/2]

static const HalfEdge& MapGen::DoublyConnectedEdgeList::GetNextInNode ( const HalfEdge & halfEdge )

inlinestatic

Definition at line 303 of file DoublyConnectedEdgeList.h.

◆ GetNodes() [1/2]

ListView<NodeIterator> MapGen::DoublyConnectedEdgeList::GetNodes ( )

inline

Definition at line 173 of file DoublyConnectedEdgeList.h.

Referenced by MapGen::fixGraphData(), and GetAngle().

Here is the caller graph for this function:

◆ GetNodes() [2/2]

ListView<ConstNodeIterator> MapGen::DoublyConnectedEdgeList::GetNodes ( ) const

inline

Definition at line 178 of file DoublyConnectedEdgeList.h.

◆ GetPair() [1/2]

static HalfEdge& MapGen::DoublyConnectedEdgeList::GetPair ( HalfEdge & halfEdge )

inlinestatic

Definition at line 236 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Pair.

Referenced by FHalfEdgeCounter::Insert(), and MapGen::RoadSegmentBuilder::insert().

Here is the caller graph for this function:

◆ GetPair() [2/2]

static const HalfEdge& MapGen::DoublyConnectedEdgeList::GetPair ( const HalfEdge & halfEdge )

inlinestatic

Definition at line 242 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Pair.

◆ GetSource() [1/2]

static Node& MapGen::DoublyConnectedEdgeList::GetSource ( HalfEdge & halfEdge )

inlinestatic

Definition at line 212 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Source.

Referenced by MapGen::RoadSegmentBuilder::Add(), GetAngle(), MapGen::getSourcePosition(), and MapGen::GraphParser::GraphParser().

Here is the caller graph for this function:

◆ GetSource() [2/2]

static const Node& MapGen::DoublyConnectedEdgeList::GetSource ( const HalfEdge & halfEdge )

inlinestatic

Definition at line 218 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Source.

◆ GetTarget() [1/2]

static Node& MapGen::DoublyConnectedEdgeList::GetTarget ( HalfEdge & halfEdge )

inlinestatic

Definition at line 224 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Target.

Referenced by GetAngle(), and MapGen::getTargetPosition().

Here is the caller graph for this function:

◆ GetTarget() [2/2]

static const Node& MapGen::DoublyConnectedEdgeList::GetTarget ( const HalfEdge & halfEdge )

inlinestatic

Definition at line 230 of file DoublyConnectedEdgeList.h.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Target.

◆ SplitEdge()

DoublyConnectedEdgeList::Node & MapGen::DoublyConnectedEdgeList::SplitEdge	(	const Position &	Position,
		HalfEdge &	HalfEdge
	)

Split HalfEdge (and its pair) at Position.

The time complexity is O(n*log(n)) where n is the number of edges leaving HalfEdge's source.

Returns: The newly generated node.

Definition at line 148 of file DoublyConnectedEdgeList.cpp.

References MapGen::DoublyConnectedEdgeList::HalfEdge::Face, MapGen::FindPositionInNode(), HalfEdges, MapGen::DoublyConnectedEdgeList::HalfEdge::Next, Nodes, MapGen::DoublyConnectedEdgeList::HalfEdge::Pair, MapGen::DoublyConnectedEdgeList::HalfEdge::Source, and MapGen::DoublyConnectedEdgeList::HalfEdge::Target.

Referenced by MapGen::splitFace().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ Faces

FaceContainer MapGen::DoublyConnectedEdgeList::Faces

private

Definition at line 333 of file DoublyConnectedEdgeList.h.

Referenced by ConnectNodes(), and DoublyConnectedEdgeList().

◆ HalfEdges

HalfEdgeContainer MapGen::DoublyConnectedEdgeList::HalfEdges

private

Definition at line 331 of file DoublyConnectedEdgeList.h.

Referenced by AddNode(), ConnectNodes(), DoublyConnectedEdgeList(), and SplitEdge().

◆ Nodes

NodeContainer MapGen::DoublyConnectedEdgeList::Nodes

private

Definition at line 329 of file DoublyConnectedEdgeList.h.

Referenced by AddNode(), DoublyConnectedEdgeList(), and SplitEdge().

The documentation for this class was generated from the following files:

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ ConstFaceIterator

◆ ConstHalfEdgeIterator

◆ ConstNodeIterator

◆ FaceContainer

◆ FaceIterator

◆ HalfEdgeContainer

◆ HalfEdgeIterator

◆ NodeContainer

◆ NodeIterator

◆ Position

Constructor & Destructor Documentation

◆ DoublyConnectedEdgeList() [1/2]

◆ DoublyConnectedEdgeList() [2/2]

◆ ~DoublyConnectedEdgeList()

Member Function Documentation

◆ AddNode()

◆ ConnectNodes()

◆ CountFaces()

◆ CountHalfEdges()

◆ CountNodes()

◆ GetAngle()

◆ GetFace() [1/2]

◆ GetFace() [2/2]

◆ GetFaces() [1/2]

◆ GetFaces() [2/2]

◆ GetHalfEdge() [1/2]

◆ GetHalfEdge() [2/2]

◆ GetHalfEdges() [1/2]

◆ GetHalfEdges() [2/2]

◆ GetLeavingHalfEdge() [1/2]

◆ GetLeavingHalfEdge() [2/2]

◆ GetNextInFace() [1/2]

◆ GetNextInFace() [2/2]

◆ GetNextInNode() [1/2]

◆ GetNextInNode() [2/2]

◆ GetNodes() [1/2]

◆ GetNodes() [2/2]

◆ GetPair() [1/2]

◆ GetPair() [2/2]

◆ GetSource() [1/2]

◆ GetSource() [2/2]

◆ GetTarget() [1/2]

◆ GetTarget() [2/2]

◆ SplitEdge()

Member Data Documentation

◆ Faces

◆ HalfEdges

◆ Nodes