# Finding largest subset of line segments that don't intersect

I completed a challenge of codeeval called BayBridges. It can be found here. I have uploaded my code on GitHub here.

In summary, the challenge is to take a list of line segments, each specified by its endpoints in [latitude, longitude] format, and find the largest subset such that no pair of line segments intersects.

The code works for the test input which has been given under the question. However, it fails for large test case since the code takes more than 10 seconds to run for large data sets.

TL;DR description of my solution is as follows

1. create a graph with nodes being bridges and connecting edges representing overlaps. Graph is represented by Jagged Array structure
2. degree of a node represents number of overlaps
3. remove iteratively bridge with maximum degree
4. stop when the graph is completely disconnected

I realize one of the problems is use of Jagged Array type of structure to represent a graph and then iterating over rows and elements in that Jagged array. But This is the only way I could think of a solution.

Please tell me what I could have done differently to produce better code.

Author's note:

1. Please refer to this SO question on how to tokenize a string with multiple delimiters.
2. To check if two lines intersect, functions available online were used.
3. Comments have been provided wherever needed and the code will be uploaded on GitHub and will stay there under user sudhirv20 unless explicitly asked to take it down
4. A monolithic structure has been presented. For better management, division of code into multiple files is preferred.

typedef struct Bridges {
int number;
double x1;
double y1;
double x2;
double y2;
int degree;
bool deleted;
} Bridges;

// Rows are formed by nodes, Vector of rows forms Jagged array
// Jagged array represents the graph
typedef vector<Bridges> Rows;
typedef vector<Rows> Graph;

// Functions to check intersection of two line segments
static bool IsOnSegment(double xi, double yi, double xj, double yj, double xk, double yk);
static char ComputeDirection(double xi, double yi, double xj, double yj, double xk, double yk);
bool DoLineSegmentsIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4);

// Functions to see if there are any overlaps at all in the graph
bool IsOverlap(int& culprit_bridge, Graph& graph);

int main(int argc, char *argv[]) {
string file_name = argv[1];
ifstream infile (file_name);

Bridges bridge;
vector<Bridges>::iterator itrow, itrow_2;
vector<Rows>::iterator itgraph, itgraph_2;
Rows row;
Graph graph;
graph.clear();
double X1, Y1, X2, Y2, X3, Y3, X4, Y4;

// defining the delimiters which will be neglected
// to extract information from the text file
std::vector<std::string> parts;
std::vector<std::string> tokens;
string line;
bridge.degree = 0;
if (infile.is_open()){
while(getline(infile,line)){
tokens.clear();
row.clear();

string str = line;
std::size_t prev_pos = 0, pos;
while ((pos = str.find_first_of(":([],) r\t", prev_pos)) != std::string::npos){
if (pos > prev_pos) tokens.push_back(str.substr(prev_pos, pos-prev_pos));
prev_pos= pos+1;
}
if (prev_pos< str.length()) tokens.push_back(str.substr(prev_pos, std::string::npos));
if(tokens.size() < 5) continue;
bridge.number = atoi(tokens[0].c_str());
bridge.x1 = atof(tokens[1].c_str());
bridge.y1 = atof(tokens[2].c_str());
bridge.x2 = atof(tokens[3].c_str());
bridge.y2 = atof(tokens[4].c_str());
row.push_back(bridge);

// first column of jagged array is formed which
// represents just the nodes without any edges
graph.push_back(row);
}
infile.close();
}
else cout << "Unable to open file";

// Formation of the complete graph with edges connected and
// degrees updated according to the number of overlaps
for(itgraph = graph.begin(); itgraph != graph.end(); itgraph++){
X1 = itgraph->begin()->x1;
Y1 = itgraph->begin()->y1;
X2 = itgraph->begin()->x2;
Y2 = itgraph->begin()->y2;
for(itgraph_2 = itgraph+1; itgraph_2 != graph.end(); itgraph_2++){
X3 = itgraph_2->begin()->x1;
Y3 = itgraph_2->begin()->y1;
X4 = itgraph_2->begin()->x2;
Y4 = itgraph_2->begin()->y2;
if(DoLineSegmentsIntersect(X1, Y1, X2, Y2, X3, Y3, X4, Y4)){
itgraph_2->begin()->degree++;
itgraph->begin()->degree++;
bridge = *(itgraph_2->begin());
itgraph->push_back(bridge);
}
}
}

// The graph is iterated and the node with highest degree is deleted from the graph
// by marking deleted as 1. All the other nodes which are connected with the deleted
// node will reduce their degree by 1.
// The iteration is continued until the degrees of all the nodes in the graph
// becomes zero. Which implies there are no overlaps of bridges anymore.
int culprit_bridge = -1;
while(IsOverlap(culprit_bridge, graph)){
graph[culprit_bridge].begin()->deleted = 1;
for(itrow = graph[culprit_bridge].begin(); itrow != graph[culprit_bridge].end(); itrow++){
graph[(itrow->number)-1].begin()->degree--;
}
culprit_bridge = -1;
}

// Print the numbers of the bridges which are not deleted
for(itgraph = graph.begin(); itgraph != graph.end(); itgraph++){
if(itgraph->begin()->deleted == 0)
cout << itgraph->begin()->number << endl;
}

return 0;
}

// This function checks if any bridges are left with degrees
// more than 0. If yes, a culprit node is identified with maximum overlaps
// and true is returned indicating the iteration to continue
bool IsOverlap(int& culprit_bridge, Graph& graph) {
int max_degree = INT_MIN;
int max_position = 0;
int counter = 0;
Graph::iterator itgraph;
for(itgraph = graph.begin(); itgraph != graph.end(); itgraph++){
if(itgraph->begin()->deleted == 0){
if(max_degree < itgraph->begin()->degree){
max_degree = itgraph->begin()->degree;
max_position = counter;
}
}
counter++;
}
if(max_degree == 0) return 0;
else {
culprit_bridge = max_position;
return 1;
}
}

static bool IsOnSegment(double xi, double yi, double xj, double yj, double xk, double yk) {
return (xi <= xk || xj <= xk) && (xk <= xi || xk <= xj) &&
(yi <= yk || yj <= yk) && (yk <= yi || yk <= yj);
}

static char ComputeDirection(double xi, double yi, double xj, double yj, double xk, double yk) {
double a = (xk - xi) * (yj - yi);
double b = (xj - xi) * (yk - yi);
return a < b ? -1 : a > b ? 1 : 0;
}

/** Do line segments (x1, y1)--(x2, y2) and (x3, y3)--(x4, y4) intersect? */
bool DoLineSegmentsIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
char d1 = ComputeDirection(x3, y3, x4, y4, x1, y1);
char d2 = ComputeDirection(x3, y3, x4, y4, x2, y2);
char d3 = ComputeDirection(x1, y1, x2, y2, x3, y3);
char d4 = ComputeDirection(x1, y1, x2, y2, x4, y4);
return (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
(d1 == 0 && IsOnSegment(x3, y3, x4, y4, x1, y1)) ||
(d2 == 0 && IsOnSegment(x3, y3, x4, y4, x2, y2)) ||
(d3 == 0 && IsOnSegment(x1, y1, x2, y2, x3, y3)) ||
(d4 == 0 && IsOnSegment(x1, y1, x2, y2, x4, y4));
}


Don't need to typedef struct in C++ like you did in C. struct are already in the normal namespace (not their own). Also its nice to indent the code to make it nice to read.

struct Bridges {
int number;
double x1;
double y1;
double x2;
double y2;
int degree;
bool deleted;
};


Don't know what a Row is here.

typedef vector<Rows> Graph;


Also your lack of using std:: before vector indicates you are using using namespace std; in some place in your code. Please stop doing that. See Why is “using namespace std;” considered bad practice?

Don't declare all your variables at the top of the function.

Bridges bridge;
vector<Bridges>::iterator itrow, itrow_2;
vector<Rows>::iterator itgraph, itgraph_2;
Rows row;


Declare them as close to the first point of usage as possible. This makes the code easier to read as you can easily glance at the type at the point of usage rather than having to scroll to the top of the function.

You do:

if (infile.is_open()){

// Do Work
}
else cout << "Unable to open file";


I would reverse that. If the file is not open your code has not made the pre-condition on working and may as well exit. Check your pre-conditions first exit fast if any of the preconditions are not met. That way if any of your pre-conditions fail your code just does not execute and normal code becomes laid out without special consideration:

if (!infile.is_open()){
cout << "Unable to open file";
exit(1);
}

// Do Work


while(getline(infile,line)){
// Lots of code
}


You put lots of minuta code into the main function. You should put this code into its own function. I personally define the std::istream operator>>(std::ostream&, Bridges&) method. This way a bridge knows how to read itself from the input. Your basic code is then simplifies too:

Bridge br;
while(std::cin >> br)
{
Rows row;
row.push_back(br);
graph.push_back(row);
}


Now this makes the code much easier to read. If I really want to look up how bridge is de-serialized then I will go look it up. But I don't need to understand that to understand the main function.

Don't manually close a file.

infile.close();


Unless you want to check for file closing errors best to just let the destructor close the file for you.

Those iterators you declared at the top. Just declare them in the for loop:

for(itgraph = graph.begin(); itgraph != graph.end(); itgraph++){

// Easier to declare an use the iterator here:

for(vector<Rows>::iterator itgraph = graph.begin(); itgraph != graph.end(); ++itgraph){

// If you have C++11 you can use aut.

for(auto itgraph = graph.begin(); itgraph != graph.end(); ++itgraph){


Note: slightly quicker to use prefix increment on iterator. (probably not significant in your case) but a good general rule.

Your speed issue is coming here (probably).

for(itgraph = graph.begin(); itgraph != graph.end(); itgraph++){
for(itgraph_2 = itgraph+1; itgraph_2 != graph.end(); itgraph_2++){


It's $O(N^2)$. I tried looking at DoLineSegmentsIntersect() to see if I could spot a smarter way of applying this. But because the variable names make it incomprehensible to decipher (and there is no comments) I can't help you there. But maybe you don't have to search all the bridges. If you use a map to keep an ordered set of bridges maybe you can just extract lists of map that have a specific property.

## This is my version:

Score: 99.230

This section contains the line intersection detection code. Which I found here I just changed the Point structure to hold doubles rather than integers. This meant I needed to update the orientation() function (as test for zero was needed) and I made it test up to 6 decimal places of accuracy (which matched the sample input data).

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <iterator>
#include <algorithm>

struct Point
{
double x;
double y;
};

// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point const& p, Point const& q, Point const& r)
{
if (q.x <= std::max(p.x, r.x) && q.x >= std::min(p.x, r.x) &&
q.y <= std::max(p.y, r.y) && q.y >= std::min(p.y, r.y))
return true;

return false;
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point const& p, Point const& q, Point const& r)
{
// See 10th slides from following link for derivation of the formula
// http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
double val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);

// Check to the nearest 6 decimal places.
int test = val*1000000+0.5;
if (test == 0) return 0;  // colinear

return (val > 0)? 1: 2; // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point const& p1, Point const& q1, Point const& p2, Point const& q2)
{
// Find the four orientations needed for general and
// special cases
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);

// General case
if (o1 != o2 && o3 != o4)
return true;

// Special Cases
// p1, q1 and p2 are colinear and p2 lies on segment p1q1
if (o1 == 0 && onSegment(p1, p2, q1)) return true;

// p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 && onSegment(p1, q2, q1)) return true;

// p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;

// p2, q2 and q1 are colinear and q1 lies on segment p2q2
if (o4 == 0 && onSegment(p2, q1, q2)) return true;

return false; // Doesn't fall in any of the above cases
}


### Bridge

A class for reading and writing bridge information from/to a stream. Just one extra function to detect intersection between two bridges.

class Bridge
{
int     id;
Point   start;
Point   end;
public:
friend std::istream& operator>>(std::istream& in, Bridge& data)
{
std::string line;
if(std::getline(in, line))
{
std::stringstream   lineStream(line);
char c[10];
lineStream >> data.id >> c[0] >> c[1] >> c[2] >> data.start.x >> c[3] >> data.start.y >> c[4] >> c[5] >> c[6] >> data.end.x >> c[7] >> data.end.y >> c[8] >> c[9];
if (c[0] != ':' || c[1] != '(' || c[2] != '[' || c[3] != ',' || c[4] != ']' || c[5] != ',' || c[6] != '[' || c[7] != ',' || c[8] != ']' || c[9] != ')')
{
throw std::runtime_error("Failed: Input error");
}
}
return in;
}
friend std::ostream& operator<<(std::ostream& out, Bridge& data)
{
return out << data.id;
}

bool Intersect(Bridge const& rhs) const
{
bool r = (id == rhs.id)
? true
: doIntersect(start, end, rhs.start, rhs.end);
return r;
}
};


### BridgeCross

A class to cache information about weather two bridges cross. The first time you ask it calculates the value. Subsequent requests just use the previous value.

class BridgeCross
{
std::vector<Bridge> const&      data;           // All the bridges
std::vector<std::vector<int>>   validBridges;
public:
BridgeCross(std::vector<Bridge> const& data)
: data(data)
, validBridges(data.size(), std::vector<int>(data.size(), -1))
{}

bool isBridegeOK(int src, int dst)
{
int x = std::min(src, dst);
int y = std::max(src, dst);

int& test = validBridges[x][y];
if (test == -1)
{
test  = data[x].Intersect(data[y]);
}
return !test;
}
};


### main

I creat3ed a better version using boost::dynamic_bitset. But the compatition site did not have boost installed (I complained obviously).

int main()
{
std::vector<Bridge>     bridges;
std::copy(std::istream_iterator<Bridge>(std::cin), std::istream_iterator<Bridge>(),
std::back_inserter(bridges));

BridgeCross                 bridgeCrossInfo(bridges);

typedef     std::set<int>       DataSet;
typedef     std::set<DataSet>   ContSet;

/*
* DataSet:    A set of bridges that work together.
*             We are trying to build a bunch of these the set with the largest
*             number of members is the answer to the solution.
* ContSet:    A set of potential answers.
*             Each iteration of the outer loop we take each answer we already
*             have constructed and add each of the bridges to it.
*
*             After the first iteration we have N DataSets each with a different
*             bridge in it.
*             After the second iteration we have N*N DataSets with all
*             of combinations X,Y (assuming X and Y work together).
*
*             So basically every iteration we do a cartesian product of the
*             the current result set and all the bridges in the input data.
*
*             You would thinkg this woudl explode the data size required.
*             But you also have to remember that a lot of the combinations
*             produce the same set:
*               1 + 2 + 3  =>  2 + 1 + 3 => 2 + 3 + 1 => 3 + 1 + 2 => 3 + 2 + 1
*
*             We also add the optimization that if we fail to add a bridge
*             we remove the set from the potential results (because we are
*             reying all results at the same time this optimization is fine
*             and does not limit us in finding the solution.
*/
ContSet     bridgeSets;
DataSet     bestSetSoFar;

std::size_t const size = bridges.size();
bridgeSets.insert(DataSet());  // Adds an empty set.

/*
* Two main loops. (loop and test) make sure we add all combinations.
* The check loop iterates over all the current results.
* The std::find_if() loops over all current bridges in a DataSet
*
* So this is technically a O(n^4) complexity.
*
* But in reality it automatically prunes itself well.
* I don't have the maths skill to work out the true complexity.
*
*/
for(int loop = 0; loop < size; ++loop)
{
ContSet  replacement;
bool haveBestSetAtThisSize = false;
for(auto const& check: bridgeSets)
{
for(int test = 0; test < size; ++test)
{
if (std::find_if(check.begin(), check.end(),
[&bridgeCrossInfo, &test](int val)
{
bool t = !bridgeCrossInfo.isBridegeOK(test, val);
return t;
}
) == check.end())
{
DataSet result(check);
result.insert(test);
replacement.insert(std::move(result));
}
else
{
}
}
{
// In every iteration there may be multiple best results
// It does not matter which one we choose.
// So choose the first and avoid the extra copies.
haveBestSetAtThisSize   = true;
bestSetSoFar            = check;
}
}
replacement.swap(bridgeSets);
}
if (!bridgeSets.empty())
{
// If this is not empty. Then we managed to add all the bridges and thus have a full set of bridges.
bestSetSoFar= *(bridgeSets.begin());
}

// Just print out the bridges in the bestSetSoFar.
// DataSet is a sorted set so it should come out in the correct order
// with no work.
for(auto loop = bestSetSoFar.begin(); loop != bestSetSoFar.end(); ++loop)
{
std::cout << bridges[*loop] << "\n";
}
}