How do I determine the intersection point of two lines in GDI+?
.net, c#, gdi+, geometry, graphics
Solution
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.(x2-x1) - v1.v2 v2.(x2-x1)) / ((v1.v1)(v2.v2) - (v1.v2)^2)
b = (v1.v2 v1.(x2-x1) - v1.v1 v2.(x2-x1)) / ((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.
Problem
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?