Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °
You are not logged in.
Post a reply
Topic review (newest first)
I think it's the vector notation I'm getting hung up on. The explanation: "In otherwords, he is defining two infinite lines, finding where they intersect, and then seeing if the lines fall within the boundaries of the line segments." really helps though.
here is a flash (i have CS3 so i could only export at minimum to flash 8) http://ngup.net/uploads/217476_mif.fla
luca is creating parametrically defined lines. suppose you have the line from (a,b) to (c,d). This consists of all points of the form (x,y) = (a, b) + t[(c,d) - (a,b)] for any t you pick, this gives you the point you reach if you start at (a, b) and walk t times the distance from (a,b) to (c,d), walking directly towards (c,d). Note, if you chose t= 1/2, you have (a,b) + 1/2(c,d) - 1/2(a,b) = 1/2[(a,b) + (c,d)] which is the midpoint between the two, which is what we'd expect. Further, if we walk 1 times the distance from (a,b) to (c,d) we should end up at (c,d), and indeed (a,b) + 1[(c,d) - (a,b)] = (a,b) + 1(c,d) - 1(a,b) = (c,d).
I really hate to say this but... what?
define your two line segments as A0 to A1 and B0 to B1 so that you can imagine them as a couple of rays
so that you have removing the 0 index for easier reading
then you have the condition:
this isn't nice to work with, so lets look at it a different way:
as you move along the B ray, and take a vector from A to B[s] the point at which the two rays intersect, is when this vector is parallel to V, or that its perpendicular vector is perpendicular to V: the reason for this is that to find if two vectors are parallel, you have to dot them, and check that the value of the dot product is plus-minus the product of the two magnitudes, whereas checking for perpendicular vectors, no matter what their magnitudes are, the dot product is 0 if they are perpendicular, so you don't need to work out their lengths
if we define a unary operator which is just the same as having the vector transformed by a 90 degree rotation matrix, so all rules apply the same as multiplying with a matrix
So we have:
similarly working for t you get
note that the denominators are the same, so you can pre-compute the inverse of the denominator for faster execution time:
the only time this fails is if Q and V are parallel, in which case the denominator is 0, but in this case it is either that they never intersect (even going past limits of line segment) or that they are the same line segment
then you would do it like this:
calculate inverse of denominator calculate s if (s < 0 || s > 1) return false calculate t return (t >= 0 && t<=1)
so with this you can find if they intersect, and if they do intersect, use either the value for s or t to calculate the exact intersection point
I'm working on a Flash game, and I can't come up with a simple algorithm to test if to line segments intersect.