Scanning algorithm to find intersections between lines

Question

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?

Are you expecting to do this without looking at every line in L (say, by using some optimises container datatype)? — rici
– rici, Commented Feb 3, 2021 at 22:20
Do you have a set of lines or a set of line segments? In the former case it's simply checking which lines are parallel to the X axis. — orlp
– orlp, Commented Feb 4, 2021 at 0:04
Also how are your lines L stored, assuming they're line segments? As pairs of points (start/end)? — orlp
– orlp, Commented Feb 4, 2021 at 0:06
What if a line segment is intersected by multiple horizontal lines originating from points in P? Does that count multiple times or only once? — orlp
– orlp, Commented Feb 4, 2021 at 0:10
Lines or line segments ?? How many lines ? How many points ? — user1196549
– user1196549, Commented Feb 4, 2021 at 9:04

orlp · Accepted Answer · 2021-02-04 00:16:19Z

1

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:

If it is START, increment l.
If it is STOP, decrement l.
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|)).

answered Feb 4, 2021 at 0:16

orlp

119k39 gold badges226 silver badges324 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Scanning algorithm to find intersections between lines

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related