![]() |
|
Method for a line segment intersecting a box |
Kikaru
Member #7,616
August 2006
![]() |
I need a way to check if a line segment, defined by two points, is crossing through a box. Working in 2-D. The shorter the solution is, the better. Also, if it makes things a lot easier, I could use a circle instead of a square. Thanks in advance! |
Felix-The-Ghost
Member #9,729
April 2008
![]() |
Schyfis
Member #9,752
May 2008
![]() |
The easy way out is to test multiple points on the line and see whether or not any of them are in the box. Naturally, you would need more tests for longer lines and smaller boxes, but this could work for your situation. It might not work for you if the box is being rotated or something though. I'm sure there's a mathematical solution as well, for example you could test to see whether or not the line intersects any of the four lines that make up the box. There's probably a simpler one, but I don't know what it is. ________________________________________________________________________________________________________ |
Kikaru
Member #7,616
August 2006
![]() |
I tried do_line() once, I'm trying to avoid that this time. The one I am looking for would be the mathematical solution. The box won't be rotated. |
SiegeLord
Member #7,827
October 2006
![]() |
Quote: Also, if it makes things a lot easier, I could use a circle instead of a square. It will make things a lot easier. If you are determined to use a rectangle, though, one way to do it (probably naive and innefficient) would be to first test each of the end points of the line segment to see if they intersect the rectangle, and if not, then test the line segment intersection against each of the sides of the rectangle. I am sure you know how to do the first bit, it's a simple point-in-rectangle test. The second bit is harder, but you can either search these forums for the algorithm or implement it as described here: Linky If you choose to do the circle method, look at the method described here: Linky "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
Kikaru
Member #7,616
August 2006
![]() |
Thanks! A question though: does the circle algorithm require the use of floats for all variables? Or can it be moderatly accurate using integers? |
SiegeLord
Member #7,827
October 2006
![]() |
Quote: Thanks! A question though: does the circle algorithm require the use of floats for all variables? Or can it be moderatly accurate using integers? Hmm... The parameter variable has to represent a fraction somehow... you could modify it like this I guess (untested):
As with all integer algorithms, be aware of possible overflows. EDIT: Removed the requirement for the macro, it should be now just as accurate as the floating point algorithm (sans the overflow protection) "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
Kikaru
Member #7,616
August 2006
![]() |
Thank you very much, this should help a lot. |
Thomas Harte
Member #33
April 2000
![]() |
No! No! No! Use the separating planes (/axis) theorem! Hopefully in the morning I'll be in a state to explain more. In the meantime, I just feel the need to point out that it's at most 16 sign of distance of point from line tests. And less work than that if the rectangle is axis aligned... [My site] [Tetrominoes] |
Schyfis
Member #9,752
May 2008
![]() |
I hate it and it's difficult to get it to work, but once the separating axis theorem is integrated into your program, it WORKS. ________________________________________________________________________________________________________ |
james_lohr
Member #1,947
February 2002
|
It's shocking how many people are suggesting ugly iterative methods. One of my favourite little tricks is the directionality test which tells you if three points are arranged in a clockwise or anti-clockwise direction. It may be directly extended to check if two points are on the same side of a line: /* (x1,y1),(x2,y2) defines a line. * If the points (ax,ay) and (bx,by) are on * the same side of the line as each other, the * function returns 1. Otherwise it returns 0. */ int same_side_of_line(float x1,float y1,float x2,float y2,float ax,float ay,float bx,float by){ return ((x1-x2)*(ay-y2)-(y1-y2)*(ax-x2)) * ((x1-x2)*(by-y2)-(y1-y2)*(bx-x2)) >=0); } This is wonderful for collision detection, for example : /*(ax1,ay1),(ax2,ay2) define a line segment A. *(bx1,by1),(bx2,by2) define a line segment B. * If the two line segments intercept, the function returns 1, else 0 */ int line_segment_intercept(float ax1,float ay1,float ax2,float ay2,float bx1,float by1,float bx2,float by2){ return (!same_side_of_line(ax1,ay1,ax2,ay2,bx1,by1,bx2,by2)&&!same_side_of_line(bx1,by1,bx2,by2,ax1,ay1,ax2,ay2)); } You can easily work out how to use it for line-segment / box collision detection. [edit] The following condition must hold for a point to be inside any arbitrary concave polygon: for any sequence of three points along the edge of the polygon, the point you are testing for must be on the same side of the line joining the first two points in the sequence as the third point in the sequence: http://www.allegro.cc/files/attachment/595913 In this diagram, the sequence of three points is q,p,A. B may be inside the polygon because it is on the same side of q,p as A. C is cannot be in the polygon because it is on the wrong side of q,p. If B is on the correct side of every line segment making up the polygon, then it is inside the polygon. So for your line-segment - box collision test, you check both ends of the line. If both points are inside, then you have a collision. Otherwise you'll have a line-segment - line-segment collision (solution already given).
|
|