How to determine if a line passes through a plane of 4 points (2d)

user_16697086 0
Viewed 117

I'm currently trying to write a program to determine if a line is going through the area of a square of 4 points and I'm searching for a formula. I only found solutions for 3-dimensional planes with vectors and tried to apply them to my situation by calculating with pen and paper but I always seem to hit a dead end when a third value is being needed.

I think the best way to approach it is to calculate the distance of the line to the square. Which would be 0 if it is passing through (a part of it) obviously. But I can't seem to find the right words for the google and stack overflow search since this seems too basic to not have been answered before.

If anyone has a link or a suggestion on how to calculate this I would be really thankful.

For my formula testing I've been working with these simple values:

Line:
l = (0 , 0) + s * (10, 10)

Points of the Square:
A (5, 5)
B (6, 5)
C (6, 6)
D (5, 6)

EDIT: Using the function of the reply I marked as the answer I got it to work. A problem I had was getting the correct input for the function. The variables a, b and c. This is how I got them in the end:

var a = 1 / x2
var b = -(1 / y2)
var c = y1/y2 - x1/x2
plane coordinate-systems 2d line math
1 Answers

Here's an idea on how you can approach the this problem.

First, what does line passing through a square means in a coordinate system?
Line L passes through square ABCD if and only if L separates the diagonally opposite sides on ABCD (A&C or B&D). Now the problem simplifies to checking whether two given points are separated by a given line.

Let the equation of the line L be ax + by + c = 0. Define a function f(x,y) = ax + by + c. Point A=(x1,y1) and C=(x2,y2) are separated by line L if f(x1,y1) and f(x2,y2) have opposite signs. Additionally if they have the same sign it means for point are on the same side of the line.

Here's the Python code for the above idea:

# Function to check if two points
# lie on the opposite side of the line

def pointsAreOnOppositeSideOfLine(a, b, c, x1, y1, x2, y2):
    fx1 = 0 # Variable to store a * x1 + b * y1 - c
    fx2 = 0 # Variable to store a * x2 + b * y2 - c


    fx1 = a * x1 + b * y1 - c
    fx2 = a * x2 + b * y2 - c

    # If fx1 and fx2 have same sign
    if ((fx1 * fx2) <= 0):
       return True

    return False
user_105267260
Related