Collision line with point

[srod]

Yes some nice math there and some familiar old formulas.

LOL, "nice math", that's a new concept to me... you must be a geek!

If you say so.

[zxtunes.com]

No more ideas?

I cannot finish game without it.

[Kaeru Gaman]

you had a lot of ideas posted, and two codes, by Helle and by akj.

your comment "not work" is maximum insufficent, you did not say what went wrong.
additionally, I asked if you really used floats.

you should have everything at hand you may need to finish that task.
get your game going.

[Psychophanta]

No more ideas?

I cannot finish game without it.

A 2D point p(p1,p2) is contained in a 2D line defined by segment a(a1,a2)-b(b1,b2) if:

Code: Select all

(p1-a1)*(b1-a1)+(p2-a2)*(b2-a2)=Sqr(((p1-a1)^2+(p2-a2)^2)*((b1-a1)^2+(b2-a2)^2))

And you can do it for any number of dimensions, not only 2D. For it just add the dimensions to each point and apply the condition:

Code: Select all

(p1-a1)*(b1-a1)+(p2-a2)*(b2-a2)+ ... +(pn-an)*(bn-an)=Sqr(((p1-a1)^2+(p2-a2)^2+ ... +(pn-an)^2)*((b1-a1)^2+(b2-a2)^2+ ... +(bn-an)^2))

.

[srod]

zxtunes, there is a wealth of info in this thread, but the thing is that you really haven't made it clear what it is you are after? Certainly not clear enough for me to use my time bashing up some code! For example, are we dealing with line segments or infinite lines? At the moment we are left to guess, even though I guess common sense suggests that you are dealing with just line segments.

Now, determining if a point is 'close' (within a certain level of tolerance) to an infinite line (one stretching through the two given end-points) is pretty trivial and involves a single calculation. The said calculation is already detailed within this thread. If, however, you wish only to consider that portion of the line between the two given end-points, then a little more work is required. At this point I have to ask about just how precise you wish to be? Determining the distance from your point to the line segment between the two end-points is still pretty easy, but does require the testing of various conditions. Now, I for one am not going to waste my time with this if it does not meet your requirements, so please be a little more specific!

Are you looking for an exact collision right down to the individual pixel, or are you looking to be 'close' to the line in question, i.e. within a certain tolerance? Are we dealing with inifnite lines......

[zxtunes.com]

@srod: I create platformer game. Line need for description of a relief of a landscape. Character have one point under legs and this point test collision with landscape (many lines). Lines no draw to screen, was only memory. Character should precisely to bend around lanscape, therefore collision should be as much as possible exact (pixel to pixel, as though on the screen lines are drawn and on them the point slides).

[zxtunes.com]

No more ideas?

I cannot finish game without it.

A 2D point p(p1,p2) is contained in a 2D line defined by segment a(a1,a2)-b(b1,b2) if:

Code: Select all

(p1-a1)*(b1-a1)+(p2-a2)*(b2-a2)=Sqr(((p1-a1)^2+(p2-a2)^2)*((b1-a1)^2+(b2-a2)^2))

And this not work too.

Code: Select all

InitSprite():InitKeyboard():InitMouse() 

Procedure LineIntersection(p1,p2,a1,b1,a2,b2) 
  a.f = (p1 - a1) * (b1 - a1) + (p2 - a2) * (b2 - a2)
  b.f = Sqr( (Pow((p1 - a1),2) + Pow((p2 - a2),2)) * (Pow((b1 - a1),2) + Pow((b2 - a2),2)) )
  If a = b: ProcedureReturn 1: EndIf
EndProcedure 

OpenWindow(0, 0, 0, 300, 300, "Line to point collison", #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, x1, y1, x2, y2) 
      ClearScreen(c*255) 
        
      StartDrawing(ScreenOutput()) 
      DrawText(0,0, Str(px)+","+Str(py)) 
      LineXY(x1, y1, x2, y2, RGB(0, 255, 0)) 
      Plot(px,py,RGB(255,255,255))  
      StopDrawing() 

Until KeyboardPushed(#PB_Key_Escape) 

random_line: 

      x1 = Random(300)  
      y1 = Random(300) 
      
      x2 = Random(300) 
      y2 = Random(300) 
      
Return

[Comtois]

Code: Select all

;http://www.swissdelphicenter.ch/torry/printcode.php?id=2080
;If you need to deal with speed 
;http://texel3d.free.fr/opengl/collisions.htm 
#Epsilon = 0.5

InitSprite():InitKeyboard()

Procedure.f Distance(x1, y1, x2, y2)
  ProcedureReturn Sqr((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
EndProcedure

Procedure.f PntToSegmentDistance(Px, Py, x1, y1, x2, y2)
Define.f Ratio, Dx, Dy, Result
  If x1 = x2 And y1 = y2
    Result = Distance(Px, Py, x1, y1)
  Else
    Dx    = x2 - x1
    Dy    = y2 - y1
    Ratio = ((Px - x1) * Dx + (Py - y1) * Dy) / (Dx * Dx + Dy * Dy)
    If Ratio < 0 
      Result = Distance(Px, Py, x1, y1)
    ElseIf Ratio > 1 
      Result = Distance(Px, Py, x2, y2)
    Else
      Result = Distance(Px, Py, (1 - Ratio) * x1 + Ratio * x2, (1 - Ratio) * y1 + Ratio * y2)
    EndIf  
  EndIf
  ProcedureReturn Result
;   If Result > -#Epsilon And Result < #Epsilon
;     ProcedureReturn 1
;   Else
;     ProcedureReturn 0
;   EndIf    
EndProcedure

OpenWindow(0, 0, 0, 300, 300, "Line to point collison", #PB_Window_SystemMenu|#PB_Window_ScreenCentered)
OpenWindowedScreen(WindowID(0), 0, 0, 300, 300, 0, 0, 0)

Gosub random_line

Repeat
      FlipBuffers()
      ExamineKeyboard()

     
      event = WindowEvent()

      px=WindowMouseX(0)
      py=WindowMouseY(0)

      If event = #WM_LBUTTONDOWN : Gosub random_line: EndIf
      c.f = PntToSegmentDistance(px, py, x1, y1, x2, y2)
      If c > -#Epsilon And c < #Epsilon
        ClearScreen($0000FF)
      Else
        ClearScreen($00FF00)
      EndIf
       
      StartDrawing(ScreenOutput())
      DrawText(0,0, StrF(c,2)) 
      LineXY(x1, y1, x2, y2, RGB(0, 0, 255))
      ;Plot(px,py,RGB(255,255,255)) 
      StopDrawing()

Until KeyboardPushed(#PB_Key_Escape)

random_line:

      x1 = Random(300) 
      y1 = Random(300)
     
      x2 = Random(300)
      y2 = Random(300)
     
Return

[Psychophanta]

Good one Comtois.
@zxtunes.com, my solution is too much math theoretic than practical for computer games.

[zxtunes.com]

@Comtois YES you code worked!! Thanks!!

Thanks all.

Argh, If 20 years ago I knew that school knowledge can really be useful, I would shirk less lessons.

[srod]

Yes, nice code Comtois. That is a very nice method. Use the vector dot product to effectively project the point onto the line and the ratio tells you whereabouts on the line the projection falls and thus which distance to calculate. Yes, very clever indeed!

I likes it!

[Demivec]

@zxtunes: I know you have a solution already but here is one I came up with also. It takes a different approach than Comtois's, though I'm sure any solution would involve similar principles. I started on it before Comtois posted his, so I wanted to present it for completeness now that it is finished.

This method determines whether the point in question lies on a screen (or other rasterizing surface) coordinate that would be used to represent the line. It is based on Bresenham's line algorithm, aside from that the remainder of the work was mine.

I think it has some advantages over Comtois's code because it doesn't use the Sqr() function and uses only integer math. The only exception is the Int() function which is used once in the process. In other words I think the advantage of my solution would be it's speed. I used this code to test:

Code: Select all

lNumberOfLoops.l = 1000000
  RandomSeed(33333)
  Timer1 = GetTickCount_()
  For i = 0 To lNumberOfLoops
    PntToSegmentDistance(Random(5000),Random(5000),Random(5000),Random(5000),Random(5000),Random(5000))
    ;procedure call repeated 10 times inside the loop to demonstrate the procedure's speed and not the loop's speed
  Next
  Timer1 = GetTickCount_() - Timer1

The result on my machine was 1578ms for Comtois's method and 1115ms for mine, making mine 30% faster. I also tested with "Random(5)" to guarantee more hits on a line segment, my code was only 25% faster in those tests.

Code: Select all

;Author: Demivec (Jared)   6/19/2008
;PureBasic v4.20
;Description: check if a point is on a rasterized line segment.  The point's coordiates are determined
;to be on the line segment if it's coordinates coincide with a point that would be used to draw the line segment
;using Bresenham's line algorithm.
;


Procedure.l isPointOnSegment(Px.l, Py.l, x1.l, y1.l, x2.l, y2.l)
  Protected dx.l,dy.l,xInc.l,yInc.l
  
  ;calculate cordinate delta's for line segment
  dx = x2 - x1 
  If dx < 0
    If Px > x1 Or Px < x2  ;check if x coordinante of point is in the span of points that contain line segment
      ProcedureReturn #False 
    EndIf
    dx = - dx  ;make delta positive (for comparison later)
    xInc = -1   ;set the line's slope direction
  Else
    If Px > x2 Or Px < x1
      ProcedureReturn #False
    EndIf
    xInc = 1
  EndIf
  
  dy = y2 - y1
  If dy < 0
    If Py > y1 Or Py < y2
      ProcedureReturn #False
    EndIf
    dy = - dy
    yInc = -1
  Else
    If Py > y2 Or Py < y1
      ProcedureReturn #False
    EndIf
    yInc = 1
  EndIf
  
  ;check if remaining coordinate matches the calculated one for the line segment
  If (dx > dy)	
    If Py = y1 + Int(((Px - x1) * dy / dx) + 0.5 * xInc) * xInc * yInc
      ProcedureReturn #True
    EndIf
  Else 		
    If dy > 0
      If Px = x1 + Int(((Py - y1) * dx / dy) + 0.5 * yInc) * xInc * yInc
        ProcedureReturn #True
      EndIf
    Else ;special case to avoid division by zero for vertical segments and singular line segments (i.e. points)
      If Px = x1
        ProcedureReturn #True
      EndIf
    EndIf 
  EndIf 
  
  ProcedureReturn #False
EndProcedure

[zxtunes.com]

thanks Demivec!

I am surprised.

In fact the first that has occurred to me it your way, but it has seemed to me stupid, I even did not reflect that it can be faster mathematical method. :roll:

[Demivec]

thanks Demivec!

I am surprised.

In fact the first that has occurred to me it your way, but it has seemed to me stupid, I even did not reflect that it can be faster mathematical method. :roll:

The first way that I thought of was to look at the distance from the line, unfortunately that ran into a problem (for me) with floating point inaccuracies.

I had to do some research before I could complete the method that I posted. It occurred to me that the point (x,y) actually was intersecting an approximation of a line on the display and not an actual line. Because of this the code could be accomplished with integer math ( = faster)

The only thing that dissatisfied me about it was that it wasn't as short as Comtois's solution.