Vertical and horizontal segments intersection (Line Sweep)

Question

Introduction:

I have a vertical segment S That i want to move across a plane (Left --> Right), and find intersections with horizontal lines.

---

Problem :

The problem which i am having is the following: if the vertical segment intersects with multiple horizontal lines, as a result i'll get multiple intersections as you can you see in the following figure. Want I want is that to have just 1 intersection. Or in another way Multiple intersections, should be combined to form 1 group. The 8 intersections Should be considered as 1.

---

As a priori information I have the START and END points of every horizontal line. I was thinking if I can Move the line by using the sweep algorithm, but i can't really figure out how to model the EVENTS

The objective is to have the following result, as shown in the following figure:

Answer 1

I put this python script together from various codes I found on the web,

• https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect?rq=1, there are plenty of good answers here, this one is from Kris.

So basically,

1. Create input list of line segments
2. Create input list of test lines (the red lines in your diagram).
3. Iterate though the intersections of every line
4. Create a set which contains all the intersection points.

I have recreated you diagram and used this to test the intersection code. It gets the two intersection points in the diagram correct.

C and C++ has equivalents to these data structures, and you can code the intersection algorithm in C too (it's fairly simple).

from __future__ import division

# Thanks to @Kris for the intersection algorithm in python
# https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
def find_intersection( p0, p1, p2, p3 ) :

    s10_x = p1[0] - p0[0]
    s10_y = p1[1] - p0[1]
    s32_x = p3[0] - p2[0]
    s32_y = p3[1] - p2[1]

    denom = s10_x * s32_y - s32_x * s10_y

    if denom == 0 : return None # collinear

    denom_is_positive = denom > 0

    s02_x = p0[0] - p2[0]
    s02_y = p0[1] - p2[1]

    s_numer = s10_x * s02_y - s10_y * s02_x

    if (s_numer < 0) == denom_is_positive : return None # no collision

    t_numer = s32_x * s02_y - s32_y * s02_x

    if (t_numer < 0) == denom_is_positive : return None # no collision

    if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision


    # collision detected

    t = t_numer / denom

    intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]
    return intersection_point

# Create input data.
# black lines
line_segments = [[(1,4), (4,4)], [(2,3), (5,3)], [(3,2), (6,2)], [(6.5, 1), (7,1)], [(7.5, 0), (8.5,0)]]
# red lines
test_segments = [[(4.5,0), (4.5,4.5)], [(6.25, 0), (6.25, 4.5)]]

# Check all lines for intersections
intersections = set()
for test_segment in test_segments:
    for line_segment in line_segments:
        p0, p1 = test_segment[0], test_segment[1]
        p2, p3 = line_segment[0], line_segment[1]
        result = find_intersection(p0, p1, p2, p3)
        if result is not None:
            intersections.add(tuple(result))

print intersections