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

• create a graph with nodes being bridges and connecting edges representing overlaps. Graph is represented by Jagged Array structure

• degree of a node represents number of overlaps

• remove iteratively bridge with maximum degree

• 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:

• Please refer to this SO question on how to tokenize a string with multiple delimiters.

• To check if two lines intersect, functions available online were used.

• 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

• 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 Rows;
typedef vector Graph;

// Functions to check intersection of two line segments
static bool IsOnSegment(double xi, double yi, double xj, double yj, double xk, dou

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 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::iterator itrow, itrow_2;
vector::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

Reading Bridges.

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::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
#include
#include
#include
#include
#include
#include

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::min(p.x, r.x) &&
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, P

StackExchange Code Review Q#54677, answer score: 8