How do I determine the intersection point of two lines in GDI+?

Question

I'm using .NET to make an application with a drawing surface, similar to Visio. The UI connects two objects on the screen with Graphics.DrawLine. This simple implementation works fine, but as the surface gets more complex, I need a more robust way to represent the objects. One of these robust requirements is determining the intersection point for two lines so I can indicate separation via some kind of graphic.

So my question is, can anyone suggest a way to do this? Perhaps with a different technique (maybe GraphViz) or an algorithm?

Answer 1

ask dr. math

Answer 2

The representation of lines by y = mx + c is problematic for computer graphics, because vertical lines require m to be infinite.

Furthermore, lines in computer graphics have a start and end point, unlike mathematical lines which are infinite in extent. One is usually only interested in a crossing of lines if the crossing point lies on both the line segments in question.

If you have two line segments, one from vectors x1 to x1+v1, and one from vectors x2 to x2+v2, then define:

a = (v2.v2 v1.(x1-x2) - v1.v2 v2.(x1-x2)) / ((v1.v1)(v2.v2) - (v1.v2)^2)
b = (v1.v2 v1.(x1-x2) - v1.v1 v2.(x1-x2)) / ((v1.v1)(v2.v2) - (v1.v2)^2)

where for the vectors p=(px,py), q=(qx,qy), p.q is the dot product (px * qx + py * qy). First check if (v1.v1)(v2.v2) = (v1.v2)^2 - if so, the lines are parallel and do not cross.

If they are not parallel, then if 0<=a<=1 and 0<=b<=1, the intersection point lies on both of the line segments, and is given by the point

x1 + a * v1

Edit The derivation of the equations for a and b is as follows. The intersection point satisfies the vector equation

x1 + a*v1 = x2 + b*v2

By taking the dot product of this equation with v1, and with v2, we get two equations:

v1.v1*a - v2.v1*b = v1.(x2-x1)
v1.v2*a - v2.v2*b = v2.(x2-x1)

which form two linear equations for a and b. Solving this system (by multiplying the first equation by v2.v2 and the second by v1.v1 and subtracting, or otherwise) gives the equations for a and b.

Answer 3

If you rotate your frame of reference to align with the first line segment (so the origin is now the start of the first line, and the vector for the first line extends along the X-axis) the question becomes, where does the second line hit the X-axis in the new coordinate system. This is a much easier question to answer. If the first line is called A and it is defined by A.O as the origin of the line and 'A.V' being the vector of the line so that A.O + A.V is the end point of the line. The frame of reference can be defined by the matrix:

    | A.V.X   A.V.Y   A.O.X |
M = | A.V.Y  -A.V.X   A.O.Y |
    |   0       0       1   |

In homogeneous coordinates this matrix provides a basis for the frame of reference that maps the line A to 0 to 1 on the X-axis. We can now define the transformed line B as:

C.O = M*(B.O)
C.V = M*(B.O + B.V) - C.O

Where the * operator properly defined for homogeneous coordinates (a projection from 3 space onto 2 space in this case). Now all that remains is to check and see where C hits the X-axis which is the same as solving Y side of the parametric equation of C for t:

C.O.Y + t * C.V.Y = 0
     -C.O.Y
t = --------
      C.V.Y

If t is in the range 0 to 1, then C hits the X-axis inside the line segment. The place it lands on the X-axis is given by the X side of the parametric equation for C:

x = C.O.X + t * C.V.X

If x is in the range 0 to 1 then the intersection is on the A line segment. We can then find the point in the original coordinate system with:

p = A.O + A.V * x

You would of course have to check first to see if either line segment is zero length. Also if C.V.Y = 0 you have parallel line segments. If C.V.X is also zero you have colinear line segments.