Reduce time taken to find N line intersection

Question

There are N line segments which are either Horizontal or vertical. Now I need to find out total number of Intersections and total number of Intersections per line segment. N can go upto 100000. I tried checking every pair of lines. The answer is correct but I need to reduce it's time taken by it.

Here's my code :

using namespace std;

typedef struct Point
{
     long long int x;
     long long int y;
} ;


bool fun(Point p0, Point p1, Point p2, Point p3)
{
    double s1_x, s1_y, s2_x, s2_y;
    s1_x = p1.x - p0.x;     s1_y = p1.y - p0.y;
    s2_x = p3.x - p2.x;     s2_y = p3.y - p2.y;

    double s, t;
    s = (-s1_y * (p0.x - p2.x) + s1_x * (p0.y - p2.y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0.y - p2.y) - s2_y * (p0.x - p2.x)) / (-s2_x * s1_y + s1_x * s2_y);

    if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
    {
        return 1; // Collision detected
    }

    return 0; // No collision
}


int main()
{
     long long int n // number of line segments;

     Point p[n],q[n]; // to store end points of line segments

    for( long long int i=0;i<n;i++)
    {

// line segments is defined by 2 points P(x1,y1) and Q(x2,y2)
        p[i].x=x1;
        p[i].y=y1;
        q[i].x=x2;
        q[i].y=y2;
    }

    for( long long int i=0;i<n-1;i++)
    {
        for( long long int j=i+1;j<n;j++)
        {
            if(fun(p[i],q[i],p[j],q[j]))
               count++;
        }

    }

    return 0;
}

Can someone help me out in reducing the time complexity of this program ?

If they are either horizontal or vertical, then checking for intersection is much easier than for arbitrary lines (as in your approach). Furthermore, start by sorting the lines by x/y coordinate. Then you know in which area possible intersections must be. A more sophisticated approach to this would be using segment trees or interval trees. — Nico Schertler, Nov 12 '16 at 21:26
The same teacher or contest? http://stackoverflow.com/questions/40570886/c-modified-line-segment-intersection — MBo, Nov 13 '16 at 06:10
see [Implementing Hoey Shamos algorithm with C#](http://stackoverflow.com/q/18512815/2521214) both answers ... — Spektre, Nov 13 '16 at 09:05
@MBoI don't know him but the question seems similar but our approaches are very different. — sammy, Nov 14 '16 at 06:34

score 2 · Accepted Answer · edited May 23 '17 at 10:30

Here's an O(n log n)-time algorithm that uses a sweep line with a Fenwick tree.

Step 0: coordinate remapping

Sort the x-coordinates and replace each value by an integer in 0..n-1 so as to preserve order. Do the same for y-coordinates. The intersection properties are preserved while allowing the algorithms below an easier implementation.

Step 1: parallel line segments

I'll describe this step for horizontal segments. Repeat for the vertical segments.

Group the horizontal segments by y coordinate. Process one group at a time, creating events for the sweep line as follows. Each segment gets a start event at its lesser endpoint and a stop event at its greater. Sort starts before stops if you want closed line segments. Sweep the events in sorted order, tracking the number of line segments that currently intersect the sweep line and the number of start events processed. The number of parallel intersections for a segment is (number of segments intersected at start time + number of start events processed at stop time - number of start events processed at start time). (See also Given a set of intervals, find the interval which has the maximum number of intersections for a previous explanation of mine for this.)

Step 2: perpendicular line segments

I'll describe this step in terms of counting for each horizontal line segment how many vertical line segments it intersects.

We do another sweep line algorithm. The events are horizontal segment starts, vertical segments, and horizontal segment stops, sorted in that order assuming closed line segments. We use a Fenwick tree to track, for each y coordinate, how many vertical segments have covered that y coordinate so far. To process a horizontal start, subtract the tree value for its y coordinate from its intersection count. To process a horizontal stop, add the tree value for its y coordinate to its intersection count. This means that the count increases by the difference, which is the number of vertical segments that stabbed the horizontal one while it was active. To process a vertical segment, use the power of the Fenwick tree to quickly increment all of the values between its lesser y coordinate and its greater (inclusive assuming closed segments).

If you want, these sweep line algorithms can be combined. I kept them separate for expository reasons.

Reduce time taken to find N line intersection

1 Answers1

Linked