Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ ¹ ² ³ °
 

You are not logged in. #1 20071103 13:45:28
Intersecting line segments algorithmI'm working on a Flash game, and I can't come up with a simple algorithm to test if to line segments intersect. Last edited by bossk171 (20071103 13:45:46) There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction. #2 20071103 23:09:35
Re: Intersecting line segments algorithmdefine your two line segments as A_{0} to A_{1} and B_{0} to B_{1} 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[0] 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 plusminus 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 precompute 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: Code: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 Last edited by lucadeltodesco (20071103 23:19:23) The Beginning Of All Things To End. The End Of All Things To Come. #3 20071104 14:23:22
Re: Intersecting line segments algorithmI really hate to say this but... what? There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction. #4 20071105 04:26:03
Re: Intersecting line segments algorithmluca 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). Last edited by mikau (20071105 04:34:58) A logarithm is just a misspelled algorithm. #5 20071106 02:48:34
Re: Intersecting line segments algorithmhere is a flash (i have CS3 so i could only export at minimum to flash 8) http://ngup.net/uploads/217476_mif.fla The Beginning Of All Things To End. The End Of All Things To Come. #6 20071106 09:39:06
Re: Intersecting line segments algorithmI 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. There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction. 