Scanning algorithm to find intersections between lines

user_15140262 0
Viewed 60

I have a set of lines L and a set of points P. I want to find how many lines of L intersect by a horizontal line passing through a point p. How can i compute this?

computational-geometry pseudocode algorithm
1 Answers

Assuming your set of line segments are stored as (start, stop) pairs and multiple intersections count multiple times, this answer applies.

The first step is to throw away all x coordinates - only the y coordinates matter. Then construct an array of pairs from L and P. For each line segment in L add (y_start, START) and (y_stop, STOP) to the array. For each point in P add (y, POINT) to the array (START, STOP, POINT are just arbitrary values, e.g. an C enum). Sort the array of pairs by the first value.

Then, initialize n = 0, l = 0 and loop through the array and look at the second value of each pair:

  1. If it is START, increment l.
  2. If it is STOP, decrement l.
  3. If it is POINT, add l to n.

n is your final result. Total complexity is dominated by the sort, O((|L| + |P|) log(|L| + |P|)).

user_5656350
Related