NGRandomNetBuilder Class Reference

#include <NGRandomNetBuilder.h>

Detailed Description

A class that builds random network using an algorithm by Markus Hartinger.

Todo:: Describe the algorithm

Definition at line 77 of file NGRandomNetBuilder.h.


Public Member Functions
void	createNet (int numNodes) throw ()
	Builds a NGNet using the set values.
	NGRandomNetBuilder (NGNet &net, SUMOReal minAngle, SUMOReal minDistance, SUMOReal maxDistance, SUMOReal connectivity, int numTries, const TNeighbourDistribution &neighborDist) throw ()
	Constructor.
Private Member Functions
bool	canConnect (NGNode baseNode, NGNode newNode) throw ()
	Checks whether connecting the given two nodes complies with the set restrictions.
bool	checkAngles (NGNode *node) throw ()
	Checks whether the angle of this node's connections are valid.
bool	createNewNode (NGNode *baseNode) throw ()
	Creates new random node.
void	findPossibleOuterNodes (NGNode *node) throw ()
	finds possible connections between Node and OuterNodes complying with restrictions
	NGRandomNetBuilder (const NGRandomNetBuilder &)
	Invalidated copy constructor.
NGRandomNetBuilder &	operator= (const NGRandomNetBuilder &)
	Invalidated assignment operator.
void	removeOuterNode (NGNode *node) throw ()
	Removes the given node from the list of outer nodes.
Private Attributes
NGNodeList	myConNodes
TNeighbourDistribution	myNeighbourDistribution
	The distrubtion of number of neighbours.
NGNet &	myNet
	The network to fill.
int	myNumNodes
	Number of nodes to be created.
int	myNumTries
	Number of tries to create a new node.
NGEdgeList	myOuterLinks
	The list of outer links.
NGNodeList	myOuterNodes
	The list of outer nodes.
restrictions
SUMOReal	myConnectivity
	Probability of connecting to a existing node if possible.
SUMOReal	myMaxDistance
	Maximum distance allowed between two nodes.
SUMOReal	myMinDistance
	Minimum distance allowed between two nodes.
SUMOReal	myMinLinkAngle
	Minimum angle allowed between two links.

Constructor & Destructor Documentation

NGRandomNetBuilder::NGRandomNetBuilder	(	NGNet &	net,
		SUMOReal	minAngle,
		SUMOReal	minDistance,
		SUMOReal	maxDistance,
		SUMOReal	connectivity,
		int	numTries,
		const TNeighbourDistribution &	neighborDist
	)			throw ()

Constructor.

Parameters:

`[in]`	net	The network to fill with generated structures
`[in]`	minAngle	The minimum allowed angle between two streets
`[in]`	minDistance	The minimum allowed distance between two nodes
`[in]`	maxDistance	The maximum allowed distance between two nodes
`[in]`	connectivity	The connectivity factor
`[in]`	numTries	?

Todo:: check meanings of connectivity/numTries

Definition at line 78 of file NGRandomNetBuilder.cpp.

00081         : myNet(net), myMinLinkAngle(minAngle), myMinDistance(minDistance),
00082         myMaxDistance(maxDistance), myConnectivity(connectivity), myNumTries(numTries),
00083         myNeighbourDistribution(neighborDist) {
00084 }

NGRandomNetBuilder::NGRandomNetBuilder ( const NGRandomNetBuilder & ) [private]

Invalidated copy constructor.

Member Function Documentation

bool NGRandomNetBuilder::canConnect	(	NGNode *	baseNode,
		NGNode *	newNode
	)			throw () `[private]`

Checks whether connecting the given two nodes complies with the set restrictions.

Checks whether the distance, the angle, and the connectivity is within the defined range when both nodes would be connected

Parameters:

`[in]`	baseNode	The first node of the combination to check
`[in]`	newNode	The second node of the combination to check

Returns:: Whether the settings allow to connect both nodes

Definition at line 139 of file NGRandomNetBuilder.cpp.

References checkAngles(), GeomHelper::distancePointLine(), GeomHelper::intersects(), myMaxDistance, myMinDistance, myOuterLinks, and SUMOReal.

Referenced by createNet(), createNewNode(), and findPossibleOuterNodes().

00139                                                                         {
00140     bool connectable=true;
00141     Position2D n1(baseNode->getPosition());
00142     Position2D n2(newNode->getPosition());
00143 
00144     // check for range between Basenode and Newnode
00145     if (connectable) {
00146         SUMOReal dist = n1.distanceTo(n2);
00147         if ((dist < myMinDistance) || (dist > myMaxDistance)) {
00148             connectable = false;
00149         }
00150     }
00151 
00152     // check for angle restrictions
00153     if (connectable) connectable = checkAngles(baseNode);
00154     if (connectable) connectable = checkAngles(newNode);
00155 
00156     // check for intersections and range restrictions with outer links
00157     if (connectable) {
00158         NGEdgeList::iterator li;
00159         li = myOuterLinks.begin();
00160         while ((connectable == true) && (li != myOuterLinks.end())) {
00161             // check intersection only if links don't share a node
00162             Position2D p1((*li)->getStartNode()->getPosition());
00163             Position2D p2((*li)->getEndNode()->getPosition());
00164             if ((baseNode != (*li)->getStartNode()) && (baseNode!= (*li)->getEndNode())
00165                     && (newNode != (*li)->getStartNode()) && (newNode!= (*li)->getEndNode())) {
00166                 connectable = !GeomHelper::intersects(n1, n2, p1, p2);
00167 
00168             }
00169             // check NewNode-To-Links distance only, if NewNode isn't part of link
00170             if ((connectable) &&
00171                     (newNode != (*li)->getStartNode()) && (newNode != (*li)->getEndNode())) {
00172                 SUMOReal dist = GeomHelper::distancePointLine(n2, p1, p2);
00173                 if ((dist < myMinDistance) && (dist > -1))
00174                     connectable = false;
00175             }
00176             li++;
00177         }
00178     }
00179     return connectable;
00180 }

bool NGRandomNetBuilder::checkAngles ( NGNode * node ) throw () [private]

Checks whether the angle of this node's connections are valid.

Checks whether the connections of the nodes are in common with the value of myMinLinkAngle.

Parameters:

[in] node The node to check connections of

Returns:: Whether the settings allow to connect both nodes

Definition at line 99 of file NGRandomNetBuilder.cpp.

References GeomHelper::Angle2D(), NGNode::getPosition(), myMinLinkAngle, SUMOReal, Position2D::x(), and Position2D::y().

Referenced by canConnect().

00099                                                     {
00100     bool check = true;
00101 
00102     if (node->LinkList.size() >  1) {
00103         // loop over all links
00104         NGEdgeList::iterator li;
00105         NGNode *ni;
00106         for (li = node->LinkList.begin(); li != node->LinkList.end(); ++li) {
00107             // calc vector of currentnode
00108             if ((*li)->getStartNode() == node) {
00109                 ni = (*li)->getEndNode();
00110             } else {
00111                 ni = (*li)->getStartNode();
00112             }
00113             Position2D v1(
00114                 ni->getPosition().x() - node->getPosition().x(),
00115                 ni->getPosition().y() - node->getPosition().y());
00116             // loop over all links
00117             NGEdgeList::iterator lj;
00118             for (lj = node->LinkList.begin(); lj != node->LinkList.end(); ++lj) {
00119                 if (li != lj) {
00120                     if ((*lj)->getStartNode() == node)
00121                         ni = (*lj)->getEndNode();
00122                     else
00123                         ni = (*lj)->getStartNode();
00124                     Position2D v2(
00125                         ni->getPosition().x() - node->getPosition().x(),
00126                         ni->getPosition().y() - node->getPosition().y());
00127                     SUMOReal angle = GeomHelper::Angle2D(v1.x(), v1.y(), v2.x(), v2.y());
00128                     if (fabs((SUMOReal) angle) < myMinLinkAngle)
00129                         check = false;
00130                 }
00131             }
00132         }
00133     }
00134     return check;
00135 }

void NGRandomNetBuilder::createNet ( int numNodes ) throw ()

Builds a NGNet using the set values.

Parameters:

[in] numNodes Number of iterations (node insertions) to perform

Todo:: Describe the algorithm

Definition at line 233 of file NGRandomNetBuilder.cpp.

References NGNet::add(), canConnect(), createNewNode(), findPossibleOuterNodes(), NGNode::getMaxNeighbours(), NGNet::getNextFreeID(), NGNode::LinkList, myConnectivity, myConNodes, myNet, myNumNodes, myNumTries, myOuterLinks, myOuterNodes, NGNet::nodeNo(), RandHelper::rand(), removeOuterNode(), NGNode::setMaxNeighbours(), NGNode::setX(), NGNode::setY(), and SUMOReal.

00233                                                   {
00234     myNumNodes = numNodes;
00235 
00236     NGNode *outerNode = new NGNode(myNet.getNextFreeID());
00237     outerNode->setX(0);
00238     outerNode->setY(0);
00239     outerNode->setMaxNeighbours(4);
00240 
00241     myNet.add(outerNode);
00242     myOuterNodes.push_back(outerNode);
00243 
00244     bool created = true;
00245     while (((int) myNet.nodeNo() < numNodes) && (myOuterNodes.size() > 0)) {
00246         // brings last element to front
00247         if (!created) {
00248             myOuterNodes.push_front(myOuterNodes.back());
00249             myOuterNodes.pop_back();
00250         }
00251         outerNode = myOuterNodes.back();
00252         findPossibleOuterNodes(outerNode);
00253         created = false;
00254         if ((myConNodes.size() > 0) && (RandHelper::rand() < myConnectivity)) {
00255             // create link
00256             NGEdge *newLink = new NGEdge(myNet.getNextFreeID(), outerNode, myConNodes.back());
00257             if (canConnect(outerNode, myConNodes.back())) {
00258                 // add link
00259                 myNet.add(newLink);
00260                 myOuterLinks.push_back(newLink);
00261                 // check nodes for being outer node
00262                 if (outerNode->LinkList.size() >= outerNode->getMaxNeighbours()) {
00263                     removeOuterNode(outerNode);
00264                 }
00265                 if (myConNodes.back()->LinkList.size() >= myConNodes.back()->getMaxNeighbours()) {
00266                     removeOuterNode(myConNodes.back());
00267                 }
00268                 created = true;
00269             } else {
00270                 delete newLink;
00271             }
00272         } else {
00273             int count=0;
00274             do {
00275                 created = createNewNode(outerNode);
00276                 count++;
00277             } while ((count <= myNumTries) && !created);
00278             if (!created) {
00279                 outerNode->setMaxNeighbours((SUMOReal) outerNode->LinkList.size());
00280                 myOuterNodes.remove(outerNode);
00281             }
00282         }
00283     }
00284 }

bool NGRandomNetBuilder::createNewNode ( NGNode * baseNode ) throw () [private]

Creates new random node.

Returns true, if creation was successfull.

Parameters:

[in] baseNode ?

Todo:: Describe better

Definition at line 202 of file NGRandomNetBuilder.cpp.

References NGNet::add(), canConnect(), NGNet::getNextFreeID(), myMaxDistance, myMinDistance, myNeighbourDistribution, myNet, myOuterLinks, myOuterNodes, TNeighbourDistribution::num(), PI, RandHelper::rand(), removeOuterNode(), NGNode::setMaxNeighbours(), NGNode::setX(), NGNode::setY(), and SUMOReal.

Referenced by createNet().

00202                                                           {
00203     // calculate position of new node based on BaseNode
00204     SUMOReal dist = RandHelper::rand(myMinDistance, myMaxDistance);
00205     SUMOReal angle = RandHelper::rand((SUMOReal)(2*PI));
00206     SUMOReal x = baseNode->getPosition().x() + dist * cos(angle);
00207     SUMOReal y = baseNode->getPosition().y() + dist * sin(angle);
00208     NGNode *newNode = new NGNode(myNet.getNextFreeID());
00209     newNode->setX(x);
00210     newNode->setY(y);
00211     newNode->setMaxNeighbours((SUMOReal) myNeighbourDistribution.num());
00212     NGEdge *newLink = new NGEdge(myNet.getNextFreeID(), baseNode, newNode);
00213     if (canConnect(baseNode, newNode)) {
00214         // add node
00215         myNet.add(newNode);
00216         myOuterNodes.push_front(newNode);
00217         // add link
00218         myNet.add(newLink);
00219         myOuterLinks.push_back(newLink);
00220         // check basenode for being outer node
00221         if (baseNode->LinkList.size() >= baseNode->getMaxNeighbours()) {
00222             removeOuterNode(baseNode);
00223         }
00224         return true;
00225     } else {
00226         delete newNode;
00227         return false;
00228     }
00229 }

void NGRandomNetBuilder::findPossibleOuterNodes ( NGNode * node ) throw () [private]

finds possible connections between Node and OuterNodes complying with restrictions

Parameters:

[in] node ?

Todo:: Describe better

Definition at line 184 of file NGRandomNetBuilder.cpp.

References canConnect(), myConNodes, and myOuterNodes.

Referenced by createNet().

00184                                                                {
00185     myConNodes.clear();
00186     NGNodeList::iterator ni;
00187     for (ni = myOuterNodes.begin(); ni != myOuterNodes.end(); ++ni) {
00188         NGNode *on=*ni;
00189         if (!node->connected(on)) {
00190             if ((node->getMaxNeighbours() > node->LinkList.size()) &&
00191                     ((on)->getMaxNeighbours() > (on)->LinkList.size())) {
00192                 if (canConnect(node, on)) {
00193                     myConNodes.push_back(on);
00194                 }
00195             }
00196         }
00197     }
00198 }

NGRandomNetBuilder& NGRandomNetBuilder::operator= ( const NGRandomNetBuilder & ) [private]

Invalidated assignment operator.

void NGRandomNetBuilder::removeOuterNode ( NGNode * node ) throw () [private]

Removes the given node from the list of outer nodes.

Parameters:

[in] node The node to remove

Definition at line 88 of file NGRandomNetBuilder.cpp.

References myOuterNodes.

Referenced by createNet(), and createNewNode().

00088                                                         {
00089     for (NGNodeList::iterator ni=myOuterNodes.begin(); ni!=myOuterNodes.end(); ++ni) {
00090         if (*ni==node) {
00091             myOuterNodes.erase(ni);
00092             return;
00093         }
00094     }
00095 }