Collision line with point

[zxtunes.com]

Somebody knows algorithm?

[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.

[Kaeru Gaman]

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.

[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.

[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.

[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.

[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".

[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!

[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

[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?

[einander]

I've updated this for PB 4.20
http://www.purebasic.fr/english/viewtop ... 563#113563

[srod]

Can you describe the algorithm please einander? Just curious. Does it calculate the distance to the line or look at angles etc?

[zxtunes.com]

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've updated this for PB 4.20
http://www.purebasic.fr/english/viewtop ... 563#113563

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

[einander]

@Srod:
No angles calculated, only distances.
This night I'll try a search for the origin of this.

[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.