I need to find intersection of N line segments (given by coordinates of start and end points) which are either vertical or horizontal.So I read that Sweep Line Algorithm is a good way to solve this.

But I can't seem to find it's implementation in C++ anywhere on Internet. Can someone provide me it's code in C++ ?

  • 1
    $\begingroup$ I didn't understand what you want to find. N line segments may have many intersections. You need one of them? All of them? Something else? $\endgroup$ Commented Nov 9, 2016 at 21:55
  • 1
    $\begingroup$ Code requests are off-topic here, strict programming questions are also off-topic here. $\endgroup$
    – Evil
    Commented Nov 9, 2016 at 22:57
  • $\begingroup$ @KarolisJuodelė I need all of the intersections. $\endgroup$
    – Sam_Buck
    Commented Nov 10, 2016 at 17:52
  • $\begingroup$ There could be $O(N^2)$ intersections (consider a grid with $N/2$ rows and $N/2$ columns), in which case you need $O(N^2)$ time anyway, which you can achieve with the obvious test-all-pairs algorithm. $\endgroup$ Commented Nov 10, 2016 at 18:14
  • 1
    $\begingroup$ @j_random_hacker I think you mean $\Theta$, not $O$. $\endgroup$ Commented Nov 10, 2016 at 18:46

1 Answer 1


Depending on how long the lines are and what the likelihood of intersections is, you could also use a spatial join. I.e. you treat all all lines as rectangles, put them in a spatial index and search for each line with which other lines it overlaps. You can use a standard R-Tree or Quadtree, but I would actually suggest a PH-Tree here, for example this one, because they are very fast for window queries with small result sets (for example if you expect usually only 1 intersection). For all results, you would have to manually calculate whether the lines actually intersect or not, because overlapping rectangles is an indicator for overlap, but obviously not a guarantee.

Also 'Sweep Line' is more of a general approach of tackling a problem, a bit like 'divide and conquer'. It is not an algorithm in itself, you would have to be more specific how you would use it to solve your intersection problem.

  • $\begingroup$ I need to find the total number of intersection for every line. $\endgroup$
    – Sam_Buck
    Commented Nov 10, 2016 at 18:28
  • $\begingroup$ Is there a specific problem with proposal? Is there a part that is not clear? $\endgroup$
    – TilmannZ
    Commented Nov 10, 2016 at 18:48
  • $\begingroup$ I used sweep line algorithm but I can't figure out how to store number of intersections for every line. $\endgroup$
    – Sam_Buck
    Commented Nov 14, 2016 at 5:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.