|
Page 3 of 4 Parametric form A line segment can be represented in a parametric form: point1 = (xp1, yp1), point2 = (xp2, yp2) Ux = xp1 + t * (xp2 - xp1) Uy = yp1 + t * (yp2 - yp1) where 0 <= t <= 1 As you can see when t = 0, x = xp1 + 0 * (xp2 - xp1) = xp1 When t = 1, x = xp1 + 1*(xp2 - xp1) = xp2 In other words when t equals 0, x equals the the first point of our line segment. When t equals 1, x equals the last point of our line segment. The same goes for y, so when t = 0, y = yp1 and when t = 1, y = yp2  E.g. for a line with point1 = (2, 4) and point2 = (10, 8) Ux = 2 + t * (10 - 2) => Ux = 2 + t * 8 Uy = 4 + t * (8 - 4) => Uy = 4 + t * 4 For 2 line segments: point1 = (xp1, yp1), point2 = (xp2, yp2), S1x = xp2 - xp1, S1y = yp2 - yp1 Ux = xp1 + t * S1x Uy = yp1 + t * S1y point3 = (xp3, yp3), point4 = (xp4, yp4), S2x = xp4 - xp3, S2y = yp4 - yp3 Vx = xp3 + s * S2x Vy = yp3 + s * S2y To find the intersection Ux must equal Vx and Uy must equal Vy. Ux = Vx => xp1 + t * S1x = xp3 + s * S2x => s * S2x - t * S1x = xp1 - xp3 and Uy = Vy => yp1 + t * S1y = yp3 + s * S2y => s * S2y - t * S1y = yp1 - yp3 This gives us two equations, with two unknows, which can be resolved with Cramer's rule as: s = (-S1y * (xp1 - xp3) + S1x * (yp1 - yp3)) / (-S2x*S1y + S1x*S2y) t = (S2x * (yp1 - yp3) - S2y * (xp1 - xp3)) / (-S2x*S1y + S1x*S2y) s and t must be in the range between 0 and 1 to be valid. After checking that, we can determine the x and y-coordinates of the intersection by plugging s and t into the equation for Ux and Uy: Ux = xp1 + t * S1x Uy = yp1 + t * S1y example Step 1: make equations segment 1: point1 = (2, 4) and point2 = (10, 8) S1x = xp2 - xp1 = 10 - 2 = 8 S1y = yp2 - yp1 = 8 - 4 = 4 Ux = xp1 + t * S1x = 2 + t * 8 Uy = yp1 + t * S1y = 4 + t * 4 segment 2: point3 = (3, 7) and point4 = (12, 4) S2x = xp4 - xp3 = 12 - 3 = 9 S2y = yp4 - yp3 = 4 - 7 = -3 Vx = xp3 + s * S2x = 3 + t * 9 Vy = yp3 + s * S2y = 7 + t * -3 Step 2: Resolve s and t s = (-S1y * (xp1 - xp3) + S1x * (yp1 - yp3)) / (-S2x*S1y + S1x*S2y) => s = (-4 * (2 - 3) + 8 * (4 - 7)) / (-9 * 4 + 8 * -3) => s = 0.33333 t = (S2x * (yp1 - yp3) - S2y * (xp1 - xp3)) / (-S2x*S1y + S1x*S2y) => t = (9 * (4 - 7) - -3 * (2 - 3)) / (-9 * 4 + 8 * -3) => t = 0.5 Step 3: check if the intersection is valid The intersection is valid if 0 <= s <= 1 and 0 <= t <= 1 0 <= 0.3333 <= 1 and 0 <= 0.5 <= 1 so our intersection is valid Step 4: get the intersection point Ux = xp1 + t * S1x = 2 + 0.5 * 8 = 6 Uy = yp1 + t * S1y = 4 + 0.5 * 4 = 6
|