CARLA
GraphGenerator.cpp
Go to the documentation of this file.
1 // Copyright (c) 2017 Computer Vision Center (CVC) at the Universitat Autonoma
2 // de Barcelona (UAB).
3 //
4 // This work is licensed under the terms of the MIT license.
5 // For a copy, see <https://opensource.org/licenses/MIT>.
6 
7 #include "Carla.h"
8 #include "GraphGenerator.h"
9 
10 #include <vector>
11 
12 namespace MapGen {
13 
15 
16  constexpr static int32 MARGIN = 6;
17 
18  // ===========================================================================
19  // -- Static local methods ---------------------------------------------------
20  // ===========================================================================
21 
22  static int32 signOf(int32 val) {
23  return (0 < val) - (val < 0);
24  }
25 
26  static const Graph::Position &getSourcePosition(const Graph::HalfEdge &edge) {
27  return Graph::GetSource(edge).GetPosition();
28  }
29 
30  static const Graph::Position &getTargetPosition(const Graph::HalfEdge &edge) {
31  return Graph::GetTarget(edge).GetPosition();
32  }
33 
35  return getTargetPosition(edge) - getSourcePosition(edge);
36  }
37 
38  static std::pair<Graph::HalfEdge *, Graph::HalfEdge *> getRandomOpposingEdges(
39  Graph::Face &face,
40  FRandomStream &random) {
41  // Get all the edges in the face.
42  std::vector<Graph::HalfEdge *> edges;
43  edges.reserve(4u);
44  auto &firstEdge = Graph::GetHalfEdge(face);
45  auto *edge = &firstEdge;
46  do {
47  edges.emplace_back(edge);
48  edge = &Graph::GetNextInFace(*edge);
49  } while (edge != &firstEdge);
50  check(edges.size() == 4u);
51  auto randomIndex = random.RandRange(0, edges.size() - 1);
52  return {edges[randomIndex], edges[(randomIndex + 2u) % edges.size()]};
53  }
54 
55  static Graph::Face *splitFace(Graph &graph, Graph::Face &face, FRandomStream &random) {
56  auto edgePair = getRandomOpposingEdges(face, random);
57  auto dir = getDirection(*edgePair.first);
58  // Assumes both edges are opposing faces on a rectangle.
59  auto otherDir = getDirection(*edgePair.second);
60  check((dir.x == -1 * otherDir.x) && (dir.y == -1 * otherDir.y));
61  // If the rectangle is not big enough do not split it.
62  if ((std::abs(dir.x) < 2*MARGIN+1) && (std::abs(dir.y) < 2*MARGIN+1))
63  return nullptr;
64  // Get a random point along the edges.
65  auto randX = (dir.x != 0 ? signOf(dir.x) * random.RandRange(MARGIN, std::abs(dir.x) - MARGIN) : 0);
66  auto randY = (dir.y != 0 ? signOf(dir.y) * random.RandRange(MARGIN, std::abs(dir.y) - MARGIN) : 0);
67  auto position0 = getSourcePosition(*edgePair.first) + Graph::Position{randX, randY};
68  auto position1 = getTargetPosition(*edgePair.second) + Graph::Position{randX, randY};
69  // Split the edges and connect.
70  Graph::Node &node0 = graph.SplitEdge(position0, *edgePair.first);
71  Graph::Node &node1 = graph.SplitEdge(position1, *edgePair.second);
72  return &graph.ConnectNodes(node0, node1);
73  }
74 
75  static void randomize(Graph &graph, const int32 seed)
76  {
77  check(graph.CountNodes() == 4u);
78  check(graph.CountHalfEdges() == 8u);
79  check(graph.CountFaces() == 2u);
80  FRandomStream random(seed);
81  /// @todo We skip first face because is the surrounding face. But this won't
82  /// be always the case, if the graph is generated differently it might be a
83  /// different one.
84  Graph::Face *face = &*(++graph.GetFaces().begin());
85  do {
86  face = splitFace(graph, *face, random);
87 #ifdef CARLA_ROAD_GENERATOR_EXTRA_LOG
88  graph.PrintToLog();
89 #endif // CARLA_ROAD_GENERATOR_EXTRA_LOG
90  } while (face != nullptr);
91  }
92 
93  // =============================================================================
94  // -- GraphGenerator -----------------------------------------------------------
95  // =============================================================================
96 
97  TUniquePtr<DoublyConnectedEdgeList> GraphGenerator::Generate(
98  const uint32 SizeX,
99  const uint32 SizeY,
100  const int32 Seed)
101  {
103  std::array<Position, 4u> box;
104  box[0u] = Position(0, 0);
105  box[1u] = Position(0, SizeY);
106  box[2u] = Position(SizeX, SizeY);
107  box[3u] = Position(SizeX, 0);
108  auto Dcel = MakeUnique<DoublyConnectedEdgeList>(box);
109  randomize(*Dcel, Seed);
110  return Dcel;
111  }
112 
113 } // namespace MapGen
Node & SplitEdge(const Position &Position, HalfEdge &HalfEdge)
Split HalfEdge (and its pair) at Position.
static HalfEdge & GetHalfEdge(Face &face)
static int32 signOf(int32 val)
Simple doubly-connected edge list structure.
static TUniquePtr< DoublyConnectedEdgeList > Generate(uint32 SizeX, uint32 SizeY, int32 Seed)
Create a squared DoublyConnectedEdgeList of size SizeX times SizeY and generate random connections in...
static Graph::Position getDirection(const Graph::HalfEdge &edge)
static Node & GetSource(HalfEdge &halfEdge)
static const Graph::Position & getTargetPosition(const Graph::HalfEdge &edge)
MapGen::Position< int32 > Position
const DoublyConnectedEdgeList::Position & GetPosition() const
static std::pair< Graph::HalfEdge *, Graph::HalfEdge * > getRandomOpposingEdges(Graph::Face &face, FRandomStream &random)
static Graph::Face * splitFace(Graph &graph, Graph::Face &face, FRandomStream &random)
static constexpr int32 MARGIN
static HalfEdge & GetNextInFace(HalfEdge &halfEdge)
static void randomize(Graph &graph, const int32 seed)
static Node & GetTarget(HalfEdge &halfEdge)
static const Graph::Position & getSourcePosition(const Graph::HalfEdge &edge)
ListView< FaceIterator > GetFaces()
Face & ConnectNodes(Node &Node0, Node &Node1)
Connect two nodes by a pair of edges.