Given 2 points and a line- do the points intersect the line? : algorithm/pseudocode

Question

A coworker gave me this problem to try out my knowledge:

Consider two points, 1 and 2, having coordinates (x1, y1) and (x2, y2), respectively. In the same plane as these two points is a vertical line whose top and bottom are represented by (xTop, yTop) and (xBot, yBot), respectively. The two points may be on opposite sides of the wall, on the same side of the wall, or directly above/below the wall. For simplicity, neither of the points can be directly on the wall. A line is drawn from point 1 to point 2; if an intersection on the wall (the vertical line) occurs, it will occur at point (xInt, yIint).

Given two points and one wall, write an algorithm to determine if the two points can see one another. This can only occur if the line drawn from point 1 to point 2 does not touch the wall.

I correctly identified that if both points' x-values are less/greater than that of the wall's, they can see one another. The same goes for the y-values. I believe that there is a lot of geometry involved in this problem. But, I'm an old man, just getting back into programming for fun and this is really trying for me to comprehend. Any help would be immensely appreciated. Thank you.

-Jon N.

score 0 · Answer 1 · answered Jan 31 '17 at 00:26

the equation for a line is y = mx + b, where m is the slope, and b is the y-intercept.

To determine if a line between two points intersects another (in your case vertical) line, first determine the slope of the line that connects the two points.

m = slope = (rise/run) = (y2 - y1)/(x2 - x1)

next, determine the y-intercept.

given (x1, y1) is on the line, and y = mx + b is the equation for a line, then y1 = mx1 + b. Since we know y1, x1, and m, we can solve for b.

b = y-intercept = y1 - mx1 = y1 - ((y2 - y1)/(x2 - x1))x1

Now, to determine if the line intercepts the wall, simply put in the x-coordinate for the wall into the equation for the line connecting the two points, and if the result is outside of the range of y values for the wall, then it does not intercept the wall (the two points can see each other).

Y@wall = mxbot + b

If YBot <= Y@wall <= YTop, then the wall is between the two points.

Hope this helps you!

score 0 · Answer 2 · answered Jan 31 '17 at 00:32

Like many geometric algorithms, there are a bunch of special cases. Let's make a table. L means left of the wall, A means above, B means below, and R means right. Y means yes, ? means maybe, n means no (existence of an intersection).

  L A B R
L n n n ?
A n n Y n
B n Y n n
R ? n n n

When one point is to the left and the other is to the right, we compute the intersection with the line containing the wall and check whether it's in the wall.

Code:

def intersects(x1, y1, x2, y2, wallx, wallymin, wallymax):
    if (x1 < wallx and x2 > wallx) or (x1 > wallx and x2 < wallx):
        iy = ((x2 - wallx) * y1 + (wallx - x1) * y2) / (x2 - x1)
        return iy >= wallymin and iy <= wallymax
    elif x1 == wallx and x2 == wallx:
        return (y1 < wallymin and y2 > wallymax) or (y1 > wallymax and y2 > wallymin)
    else:
        return False

Given 2 points and a line- do the points intersect the line? : algorithm/pseudocode

2 Answers2