Message Board
| Message Board > Programming > Looking for a mathematical algorithm |
| May 15, 2007, 14:47 | |
|
Quiest
now with more happynes 142 posts 
|
I need to know if to line segments cross. I want to pass the start points and the end points to a function, i.e. bool checkCross(x1,y1,x2,y2,x3,y3,x4,y4), where (x1|y1) is connected with (x2|y2) and (x3|y3) is conntected with (x4|y4). The function should return false when the line segments do not cross, or true when they do. Could someone supply me with a algorithm to do this? I so far know that the term to calculate the cross point of two lines: a1=(y2-y1)/(x2-x1) b1=y1-a1*x1 a2=(y4-y3)/(x4-x3) b2=y3-a1*x3 you then take the term for a line (y=ax+b) and you get the x and y values of the cross point: cross_x = (b2-b1)/(a1-a2) cross_y = a1*cross_x+b1 But what then? and this isn`t workin at all... could some mathematical genie please help me? Thanks. ____________ Roundhousekick to the face, baby! |
| # | |
| May 15, 2007, 15:34 | |
|
Sandman
F3n!x0r 1194 posts 
|
Check if the cross point is in the X- or Y-range of one of the lines? x1 < cross_x < x2 or x1 > cross_x > x2 x3 < cross_x < x4 or x3 > cross_x > x4 y1 < cross_x < y2 or y1 > cross_y > y2 y3 < cross_y < y4 or y3 > cross_y > y4 Something like this? ____________ BennuWiki Yes, my avatar has grey borders in IE (so get a decent browser) ROOFLEZ ROOFLEZ |
| # | |
| May 15, 2007, 15:34 | |
|
yonni
None 420 posts |
Surely what you want is to arrange each line into the format y=[gradient]a+[y-intercept] like on a line graph. Then what I would do is to take each possible x/y combination from one line, and check to see if it works for the other line's equation (as there are limited possibilites as the line is not infinate). I don't want to write the function myself right now, but I may a bit later. ____________ |
| # | |
| May 15, 2007, 20:04 | |
|
Sandman
F3n!x0r 1194 posts
|
Quoting Dennis: Code: bool checkCross(x1,y1,x2,y2,x3,y3,x4,y4) { if ((x1 > x3 && x2 < x4 && y1 < y3) || (x1 < x3 && x2 > x4 && y1 > y3)) return true; else return false; } ? No:  x1 > x3 is false so (x1 > x3 && x2 < x4 && y1 < y3) is false. y1 > y3 is false so (x1 < x3 && x2 > x4 && y1 > y3) is false. false || false is false so it would return false. And yet they do intersect. On a side note to Dennis, you could do without the if(): Code: return (x1 > x3 && x2 < x4 && y1 < y3) || (x1 < x3 && x2 > x4 && y1 > y3);
____________ BennuWiki Yes, my avatar has grey borders in IE (so get a decent browser) ROOFLEZ ROOFLEZ |
| # | |
| May 15, 2007, 21:14 | |
|
Frimkron
Frustrated Megalomaniac 703 posts 
|
Googled in 5 minutes: Intersection point of two lines To prove it yourself takes a bit of messy re-arranging, but the derived equations are simple to implement in code. ____________ |
| # | |
| May 16, 2007, 02:57 | |
|
Sandman
F3n!x0r 1194 posts
|
But he had that already. 
____________ BennuWiki Yes, my avatar has grey borders in IE (so get a decent browser) ROOFLEZ ROOFLEZ |
| # | |
| May 16, 2007, 15:33 | |
|
Sandman
F3n!x0r 1194 posts
|
Have it your way: It's the same, not? ____________ BennuWiki Yes, my avatar has grey borders in IE (so get a decent browser) ROOFLEZ ROOFLEZ |
| # | |
| May 18, 2007, 18:39 | |
|
Quiest
now with more happynes 142 posts
|
I don`t think its that easy, Dennis... I`m looking through Frimkrons link... and I don`t really get it. 1. What are numerators and denominators? Is it (num/denum) ? 2. I have the equations x = x1 + ua (x2 - x1) and y = y1 + ua (y2 - y1) there, but when would I know that there is no intersection? 3. what means the lines are "coincident"? 4. The main point maybe lies here: "The equations apply to lines, if the intersection of line segments is required then it is only necessary to test if ua and ub lie between 0 and 1. Whichever one lies within that range then the corresponding line segment contains the intersection point. If both lie within the range of 0 to 1 then the intersection point is within both line segments." But I don`t get it. This statement sounds so unlogical too me. ____________ Roundhousekick to the face, baby! |
| # | |
| May 18, 2007, 22:47 | |||
|
Eckolin
Quite Whiskered 388 posts 
|
1. Yes 2. When either ua or ub is outside the [0,1] range. 3. Coincident lines overlap completely. (Parallel at dist 0, if you wish). 4.
____________ Maker of Games... Wisdom is supreme; therefore get wisdom. Need help with coding? I probably wrote something similar. |
||
| # | |||
| May 19, 2007, 21:27 | |
|
DTM
Earthling! 821 posts 
|
Quote: Could someone supply me with a algorithm to do this? This is from irrlicht: Code: //! Tests if this line intersects with another line. //! \param l: Other line to test intersection with. //! \param out: If there is an intersection, the location of the intersection will //! be stored in this vector. //! \return Returns true if there is an intersection, false if not. bool intersectWith(const line2d<T>& l, vector2d<T>& out) const { bool found=false; f32 a1,a2,b1,b2; // calculate slopes, deal with infinity if (end.X-start.X == 0) b1 = (f32)1e+10; else b1 = (end.Y-start.Y)/(end.X-start.X); if (l.end.X-l.start.X == 0) b2 = (f32)1e+10; else b2 = (l.end.Y-l.start.Y)/(l.end.X-l.start.X); // calculate position a1 = start.Y - b1 * start.X; a2 = l.start.Y - b2 * l.start.X; out.X = - (a1-a2)/(b1-b2); out.Y = a1 + b1*out.X; // did the lines cross? if ( (start.X-out.X) *(out.X-end.X) >= -ROUNDING_ERROR_32 && (l.start.X-out.X)*(out.X-l.end.X)>= -ROUNDING_ERROR_32 && (start.Y-out.Y) *(out.Y-end.Y) >= -ROUNDING_ERROR_32 && (l.start.Y-out.Y)*(out.Y-l.end.Y)>= -ROUNDING_ERROR_32 ) { found = true; } return found; } It's from a line class so the first line is (start.X,start.Y,end.X,end.Y) and the other is (l.start.X,l.start.Y,l.end.X,l.end.Y). All floating point. ____________ :o |
| # | |
Message Board > Programming > Looking for a mathematical algorithm