Page 1 of 3
Collision line with point
Posted: Mon Jun 09, 2008 4:19 pm
by zxtunes.com
Somebody knows algorithm?
Posted: Mon Jun 09, 2008 4:30 pm
by srod
Well, one way would be to calculate the shortest distance from the point to the line in question and if the absolute distance is less than a 'certain amount' (e.g. 10 pixels), you have a collision!
The math depends on the nature of the information stored by your program.
Posted: Mon Jun 09, 2008 5:24 pm
by Kaeru Gaman
srod wrote:Well, one way would be to calculate the shortest distance from the point to the line in question and if the absolute distance is less than a 'certain amount' (e.g. 10 pixels), you have a collision!
..or walk via the angles:
the line builds a triangle with the checkpoint.
if the angles on both line-endpoints are smaller than a certain amount, you can consider this a collision.
e.g. both are smaller than 90° and at least one is smaller than 3°
the advantage is, you only need the three points you already have and some simple trigonometry.
disadvantage: if the checkpoint is nearer to the middle of the line, the collision-distance is greater.
Posted: Mon Jun 09, 2008 5:27 pm
by srod
Nice idea, but slower than calculating the shortest distance from the coordinates of the two end points plus the point in question!
**EDIT : Mind you the shortest distance method suffers from the fact that it operates by extending the given line etc. This means that you will also need to calculate the distances from the point in question to the two end points as well, meaning that the angle method is indeed perhaps the best way of proceeding! It depends on circumstances, i.e. whether we are dealing with a line segment or the entire line through the two end points.
Posted: Mon Jun 09, 2008 5:29 pm
by Kaeru Gaman
I don't get this , srod... distance from the points?
a line (0,0) - (1000,1000) with checkpoint (400,400) has a collision,
checkpoint (-400,-400) will have same distance from one point but no collision.
Posted: Mon Jun 09, 2008 5:33 pm
by srod
Shortest distance of the point to the extended line. It is a single calculation and in the example you cite, the distance would be zero.
Yes, see my edit above!
But then the angle method will produce obtuse angles for points which are nevertheless very very close to one of the line segment's end points.
Posted: Mon Jun 09, 2008 5:44 pm
by zxtunes.com
I fount one source on pascal:
function belong2piece(q: tpoint; tsegment): boolean;
var t: float;
begin
t:= sqr((q.x-p.x1)*(p.y2-p.y1)-(q.y-p.y1)*(p.x2-p.x1))/
(sqr(p.x2-p.x1)+sqr(p.y2-p.y1));
belong2piece:= false;
if t>sqr(eps) then exit;
if((q.x-p.x1)*(p.x2-p.x1)+(q.y-p.y1)*(p.y2-p.y1))*
((q.x-p.x2)*(p.x2-p.x1)+(q.y-p.y2)*(p.y2-p.y1))<eps then
belong2piece:= true;
end;
but not wokr
I do not understand that such "eps".
Posted: Mon Jun 09, 2008 5:45 pm
by srod
Actually, thinking about it, and if we're dealing with just a line segment, a really accurate way would be to simply translate and rotate the coordinate space until the line stretched from the origin along the x-axis. Determining how close the point is to the line segment would then be very quick and very accurate.
It just depends how much work zxtunes is prepared to put in!
Posted: Mon Jun 09, 2008 5:47 pm
by Kaeru Gaman
But then the angle method will produce obtuse angles for points which are nevertheless very very close to one of the line segment's end points.
yes, thus I said
>> e.g. both are smaller than 90° and at least one is smaller than 3°
additionally, you could calculate the angle at the checkpoint,
and allow it if its greater than a certain amound.
I think there would be nice solutions going over the three angles.
sure, more calculation than the simple distance,
but again working for segments not only for infinites
Posted: Mon Jun 09, 2008 5:51 pm
by srod
I can see where the angle method will fail with line segments as indeed the distance method can fail as well. Both methods will require quite a bit of extra work.
But both decent possibilities.
I can't understand the algorithm behind the Pascal code at the moment. Does the source you obtained the code from explain the algorithm?
Posted: Mon Jun 09, 2008 5:52 pm
by einander
Posted: Mon Jun 09, 2008 5:53 pm
by srod
Can you describe the algorithm please einander? Just curious.
Does it calculate the distance to the line or look at angles etc?
Posted: Mon Jun 09, 2008 6:34 pm
by zxtunes.com
srod wrote:Does the source you obtained the code from explain the algorithm?
"Accessory of a point to a piece.
We consider distance from the given point up to a piece, and it is compared with eps.
1) the Square of distance is less sqr (eps)
2) Is between the perpendicular straight lines lead through the ends of a piece.
It is checked through s.p.
1.3.3. How to choose eps? _ it is usual in a condition it is spoken, from what accuracy the result should be given out. Then as eps it is possible to take number in 100, or 1000 times smaller. For example, if it is necessary to give out result with accuracy four signs after a decimal point I take eps equal 1e-6. In general if eps does not influence productivity it is better to take number less."
I adaptation this method for point, but this method not accuracy.
Code: Select all
InitSprite()
InitKeyboard()
InitMouse()
Procedure LineIntersection(px,py,u1,v1,u2,v2)
b1.f = 0
b2.f = (v2 - v1) / (u2 - u1)
a1.f = py - b1 * x1
a2.f = v1 - b2 * u1
xi = - (a1-a2)/(b1-b2)
yi = a1+b1*xi
If (px - xi)*(xi-px+1)> -1 And (u1-xi)*(xi - u2)> 0 And (py-yi)*(yi-py)>-1 And (v1-yi)*(yi-v2)>-1
ProcedureReturn #True
Else
ProcedureReturn #False
EndIf
EndProcedure
OpenWindow(0, 0, 0, 300, 300, "Line Intersection Test", #PB_Window_SystemMenu|#PB_Window_ScreenCentered)
OpenWindowedScreen(WindowID(0), 0, 0, 300, 300, 0, 0, 0)
Gosub random_line
Repeat
FlipBuffers()
ExamineKeyboard()
ExamineMouse()
Event = WindowEvent()
px=MouseX()
py=MouseY()
If MouseButton(#PB_MouseButton_Left): Gosub random_line: EndIf
c = LineIntersection(px, py, x3, y3, x4, y4)
ClearScreen(c*255)
StartDrawing(ScreenOutput())
DrawText(0,0, Str(px)+","+Str(py))
LineXY(x3, y3, x4, y4, RGB(0, 255, 0))
Plot(px,py,RGB(255,255,255))
StopDrawing()
Until KeyboardPushed(#PB_Key_Escape)
random_line:
x3 = Random(300)
Repeat
y3 = Random(300)
Until y3<>x3
x4 = Random(300)
Repeat
y4 = Random(300)
Until y4<>x4
Return
Posted: Mon Jun 09, 2008 6:45 pm
by einander
@Srod:
No angles calculated, only distances.
This night I'll try a search for the origin of this.
Posted: Mon Jun 09, 2008 11:55 pm
by einander
@Srod:
A description for the intersection maths is described at
http://www-static.cc.gatech.edu/gvu/mul ... lines.html
See the paragraph
How do I find the intersection of two lines?
Cheers.