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

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. enter image description here

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: enter image description here


1 Answer 1


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

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).

Line segments

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:

print intersections
  • $\begingroup$ thank you @boyfarrel for the algorithm. It is very simple yes i started to code it in c++. as soon i am done i'll also post in here. $\endgroup$
    – Hani Gotc
    Oct 30, 2013 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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