# Segment road map data with heuristics

## Backstory

A little while ago I was assigned with the task of clustering some road segments using open street map data. After parsing a huge XML (maybe that should be another review) I ended up with the following data format:

struct node {
std::string id;
double lat;
double lon;
int refs;
node();
void print();
};

std::string id;
std::string type;
std::vector<int> nodes;
};

So a node has the 2 coordinates plus an id and a ref number, because later I'm supposed to keep track when a node is part of 2 different roads. A road has an id and a type and the vector has the indexes of its nodes in a vector<node> I'm using to keep the nodes. Also this vector doesn't change in size, so it's safe to keep indexes like that.

## Segmenting

My actual task is to make segments out of these roads according to the following criteria:

• When the curvature of the segment's circumcircle exceeds a heuristic value
• When the size of a segment exceeds a heuristic value
• When a node is also part of another road; in this case the segment ends after all the nodes that are part of other roads.

The output should be a text file with the following format:

segment_id, way_id, no_of_nodes, node1_lat, node_1_lon, .... lastnode_lat, lastnode_lon

My solution is this

inline double curvature(double l1, double l2, double l3){
return l1*l2*l3/sqrt((l1+l2+l3)*(l2+l3-l1)*(l3+l1-l2)*(l1+l2-l3));
}

void write_segment(ofstream &out, int &id, string way_id, vector<double> &coords,
int &minsize, int &maxsize, int &tot_n){
out << id << ", " << way_id << ", " << coords.size()/2 << ", ";
for(size_t i=0; i<coords.size()-1; i++){
out << coords[i] << ", ";
}
out << coords.back() << '\n';
//check if we have new max/min
if(coords.size()/2 < minsize)
minsize = coords.size()/2;
else if(coords.size()/2 > maxsize)
maxsize = coords.size()/2;
//ingrement the id
id++;
tot_n += coords.size()/2;
//keep last node because it's also a part of the next segment
coords.erase(coords.begin(), coords.end()-2);
}

const string &out_s){
ofstream out(out_s);
bool write{false};
//lengths for every 3 points, total and temporary curvatures
double l1{}, l2{}, l3{}, curb{}, curv{};
double thrs{0.03};  //curvature threshold over which a segment breaks
int segid{};  //serial segment id for every new segment
//count for average curvature, tot_n -> nodes written
int count{}, tot_n{}, totalnodes{};
//min and max segment sizes for the statistics
int maxsize{}, minsize{std::numeric_limits<int>::max()};
size_t nthrs{200}, minthrs{4}; //min and max threshold for segment size
vector<double> coords; //keep all the coordinates until written to file

cout << "Segmenting:\n";
//special case for roads with one node
out << segid << ", " << roads[i].id << ", " << 1 << ", ";
out << coords[0] << ", " << coords[1] << '\n';
segid++;
tot_n++;
coords.clear();
continue;
}
//make one segment for small roads (according to minthrs)
}
write_segment(out, segid, roads[i].id, coords, minsize, maxsize, tot_n);
continue;
}
//for every other road segment it according to heuristics
//find the 3 sides of the triangle for every 3 points
curb = curvature(l1,l2,l3);
count++;
//exclude the roads with curvature >1 from average curvature
if(isfinite(curb) && curb <=1)
curv += curb;

//start checking if we need to "cut" the segment
//if the segment is too small don't cut it no matter what
if(coords.size()/2+1 <= minthrs){
continue;
}
//indicate that we have to flush next
write = true;
}
else if(curb>thrs || coords.size()/2+1 >= nthrs || write){
//check for curvature or maxsize
write_segment(out, segid, roads[i].id, coords, minsize, maxsize, tot_n);
write = false;
}
}

}
write_segment(out, segid, roads[i].id, coords, minsize, maxsize, tot_n);
coords.clear();
}
cout << "Maxsize: " << maxsize << '\n';
cout << "Minsize: " << minsize << '\n';
cout << "Segs: " << segid << '\n';
cout << "Nodes written: " << tot_n << '\n';
cout << "Total nodes were: " << totalnodes << '\n';
cout << "Average curvature: " << double(curv/count) << endl;
}

I'm interested in good and bad practices this code follows, readability, especially when documenting what each variable stands for and any performance issues.

Prefer Clear Naming over using namespace std

According to the MSDN website:

Namespaces are used to organize code into logical groups and to prevent name collisions that can occur especially when your code base includes multiple libraries.

A collision is when 2 different functions have the same name, the same argument types and a similar functionality (this is why they have the same name). Someone developing software may want to override a function such as std::cout, std::cin or they may want to override the functionality of a class such as std::vector or std::stack. Namespaces allow these constructs to be overridden.

The use of the programming statement:

using namespace std;

hides the fact that cin, cout, vector and stack are coming from the namespace std where cin, cout, vector and stack are used in the code. This can cause confusion of where the code is actually coming from.

As the software becomes more complex and uses more libraries this becomes a bigger problem.

For a more detailed discussion of why it is a bad idea to use using namespace std; see this stackoverflow question and stackoverflow question.

The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows: A class should have only one reason to change.

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines well.

The void make_segments(const std::vector<road> &roads, const std::vector<node> &nodes, const std::string &out_s) function could be broken up into at multiple functions. The following code is a good candidate for a function to be called by make_segments:

//for every other road segment it according to heuristics
for (size_t j = 1; j<roads[i].nodes.size() - minthrs; j++) {
//find the 3 sides of the triangle for every 3 points
curb = curvature(l1, l2, l3);
count++;
//exclude the roads with curvature >1 from average curvature
if (isfinite(curb) && curb <= 1)
curv += curb;

//start checking if we need to "cut" the segment
//if the segment is too small don't cut it no matter what
if (coords.size() / 2 + 1 <= minthrs) {
continue;
}
else if (nodes[roads[i].nodes[j]].refs >= 2 && nodes[roads[i].nodes[j + 1]].refs == 1) {
//indicate that we have to flush next
write = true;
}
else if (curb>thrs || coords.size() / 2 + 1 >= nthrs || write) {
//check for curvature or maxsize
write_segment(out, segid, roads[i].id, coords, minsize, maxsize, tot_n);
write = false;
}
}

The more separate functions there are the easier it is to understand or read the code. This also makes it easier for any programmer to maintain or debug the code.

Prefer Iterators Over Indexes for Container Classes
The function void write_segment(std::ofstream &out, int &id, std::string way_id, std::vector<double> &coords, int &minsize, int &maxsize, int &tot_n) contains the following code:

for (size_t i = 0; i<coords.size() - 1; i++) {
out << coords[i] << ", ";
}

A more modern and less C programming language like construct would be:

for (auto coord_iterator: coords) {
out << coord_iterator << ",";
}

Using iterators in this manner makes it much easier to program correctly.

Declare Variables as Close to Use as Possible
In the loop defined as a possible candidate for a function there are 3 variables that should be defined within the loop rather than at the top of the function. The variables l1, l2 and l3 are only assigned values and used within the loop.

//find the 3 sides of the triangle for every 3 points