Lines intersections

Question

For two lines or two paths or two point lists as shapes in WPF and c#, does anyone have an idea how to detect the intersection and draw the intersection in a rounded shape to make it clear to the eye that these two lines are not connected (MS visio like)? I just need the principle of doing this, although some code will be helpful. thanks.

Possible duplicate: http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect — KeithS, Sep 10 '12 at 20:21
@SamIam my lines for now are Paths bonded to PathGeometry which consists of multiple PolyLineSegments. — Ziad, Sep 10 '12 at 20:22
If you compare all the individual line segments then it is a duplicate. You state you just need the principle. — paparazzo, Sep 10 '12 at 20:46

score 1 · Answer 1 · edited May 23 '17 at 11:51

As from this related question, basically you can consider your line segments to be the combination of a point and a vector. You can get two points into this form by picking one to be the "origin" and subtracting its X and Y from the X and Y of the other point, producing the "delta". Do the same for the other line segment.

Now, if these two vectors cross, there will be two scalars that can be applied, one to each vector, to produce a shorter vector that is co-linear with the corresponding vector and will represent the delta in X and Y between the origin and the intersection. These scalars can be found by a function of the cross product of the two vectors; see the related question for the exact math. Finally, in order for the two line segments to intersect, the vectors that intersect must do so within their original defined lengths; that is, both of the scalars that represent the length of the vector to the intersection must be 0 < s < 1.

score 1 · Answer 2 · answered Sep 10 '12 at 20:47

There is a way with homogeneous coordinates to easily get what you want. To represent a point P1 use a Vector3 and makes the z coordinate equal 1.

P1 = [x1, y1, 1]
P2 = [x2, y2, 1]

The line connecting the two points is L12 = CROSS(P1,P2) = [a, b, c] where CROSS is the vector cross product, and the equation for the line is a*x+b*y+c=0.

Now if you have two lines

L12 = [a,b,c]
L34 = [e,f,g]

the point of intersection of these two lines is Q = CROSS(L12,L34) = [qx,qy,qw] with coordinates

x = qx/qw
y = qy/qw

Example: Two lines, L12 connecting points (1,1) to (2,8), and L34 connecting points (4,-2) to (9,3). Find the intersection of the two lines.

L12 = CROSS( [1,1,1], [2,8,1] ) = [-7, 1, 6]     //eq: -7*x+y+6=0
L34 = CROSS( [4,-2,1], [9,3,1] ) = [-5, 5, 30]   //eq: -5*x+5*y+30=0
Q = CROSS([-7,1,6], [-5,5,30]) = [0, 180, -30]
x = 0/(-30) = 0
y = 180/(-30) = -6

GeoGebra screenshot: GeoGebra4

Lines intersections

2 Answers2