1
$\begingroup$

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++ ?

$\endgroup$

closed as off-topic by David Richerby, Evil, jmite, D.W. Nov 10 '16 at 18:53

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – David Richerby, Evil, jmite, D.W.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$ – Karolis Juodelė Nov 9 '16 at 21:55
  • 1
    $\begingroup$ Code requests are off-topic here, strict programming questions are also off-topic here. $\endgroup$ – Evil Nov 9 '16 at 22:57
  • $\begingroup$ @KarolisJuodelė I need all of the intersections. $\endgroup$ – Sam_Buck Nov 10 '16 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$ – j_random_hacker Nov 10 '16 at 18:14
  • 1
    $\begingroup$ @j_random_hacker I think you mean $\Theta$, not $O$. $\endgroup$ – David Richerby Nov 10 '16 at 18:46
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I need to find the total number of intersection for every line. $\endgroup$ – Sam_Buck Nov 10 '16 at 18:28
  • $\begingroup$ Is there a specific problem with proposal? Is there a part that is not clear? $\endgroup$ – TilmannZ Nov 10 '16 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 Nov 14 '16 at 5:28

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