Algorithm for detection of overlapping between vectors

Question

I am currently developing a math-physics program and I need to calculate if two vectors overlap one another, the one is vertical and the other is horizontral. Is there any fast algorithm to do this because what I came up so far, has a lot of repeats. Eg lets say we have vector V1((0,1),(2,1)) and a V2((1,0),(1,2)) where the first parenthesis is the coordinates starting and the second coordinates that the vector reaches. I want as a result to take that they overlap at (1,1)

So far the only idea I came up is to ''expand'' each vector to a list of points and then compare the lists e.g for V1 its list would be (0,1) (1,1) (2,1)

Answer 1

Terminology nitpick: those aren't vectors: vectors have a direction and size, but there is no “starting point” in a vector space. instead, you're defining a line segment via the starting and ending point of this line segment.

Given these two points A and B on the line, we can calculate the direction D = B - A of the line. The line segment we are interested in consist of all points P that fulfill the following equation:

P = A + k·D,

where k is some scalar value in [0, 1]. When you have transformed all your inputs into this form, it's fairly straightforward to find solutions where the lines overlap:

           P1 = P2
=> A1 + k1·D1 = A2 + k2·D2
=>         0 = (A2 - A1) + (-k1·D1 ) + k2·D2

This is essentially a system of linear equations, which can be solved if we have two or more dimensions. (We have to solve for the two variables k1 and k2). There are three possible outcomes:

• no solutions exist (remember also the 0 <= k <= 1 constraint), i.e. the line segments do not overlap.
• exactly one solution exists, i.e. the lines touch in one point (e.g. by intersecting each other)
• there is an infinite number of solutions. This means that the lines are parallel and lie in each other for more than one point.

Answer 2

Another algorithm is described here, which is based on these slides.

Given line segments p1 -> q1 and p2 -> q2, the line segments intersect if:

1. General Case:

   • if (p1, q1, p2) and (p1, q1, q2) have different orientations and
   • (p2, q2, p1) and (p2, q2, q1) have different orientations

2. Special Case

   • if (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
   • the x-projections of (p1, q1) and (p2, q2) intersect and
   • the y-projections of (p1, q1) and (p2, q2) intersect

where the 'orientation' can be 'clockwise', 'counterclockwise' or 'collinear'.

Intuitively: if a line segment does not cross another line segment, it is entirely 'on one side' of the other segment. Only then will tracing (p1, q1, p2) and (p1, q1, q2) or (p2, q2, p1) and (p2, q2, q1) result in tracing the triangle in the same direction.