Collision line with point

Kaeru Gaman · Post by **Kaeru Gaman** » Tue Jun 10, 2008 12:13 am

independently, some further steps to my idea:

the checkpoint builds two rectangular triagles to the line when it's within two less-than-90°
the ankathede of both is the distance to the line.

...perhaps a calculation using ()² and Sqr() could follow this ansatz without trigonometric functions....

[edit]
Line |AB|, Checkpoint C... Footpoint D

|CD|² = |AD|² - |AC|²
|CD|² = |BD|² - |BC|²
AD + BD = AB
is what we know...
we don't need Sqr() so far, perhaps never because we could check against CollDist²

is this enough to make you go, srod?
it's too late for me tonight to get deep into intercept theorems and combined Pytagorases...

...the distances themselves are again Sqr()s of dXs and dYs,
all together we will have Xs and Ys like fat and meat in a salami...

srod · Post by **srod** » Tue Jun 10, 2008 9:20 am

@Einander - sorry, the math behind that is very straight forward; what I guess I am getting at is wondering how the intersection of lines fits in to this problem?

The only way I can see this helping is to construct the perpendicular to the line segment in question and passing through the given point, finding where this intersects the extended line and checking some distances...... quite a bit of work.

@Kaeru - sorry mate, I don't really follow your method there!

Having thought about it, I would adopt either one of two methods, depending on how precise I wanted the method to be. A very precise method would be the translate + rotate method I mentioned above. The only down side is having to calculate the angle of rotation first which eats up processor time of course. A quicker method would be similar to the Pascal code above. Calculate the shortest distance to the extended line and if it is greater than the desired level of accuracy then abort (return false etc.) Otherwise, calculate the sum of the two distances of the given point from the two end points. If this total is less than the distance between the end points + 2*the accuracy level, then return true! This method is very quick and basically checks to see if the given point is enclosed within the intersection of a very narrow rectangle and an ellipse (both of which contain the line segment in question). It should be quite accurate, with the only possible (and very slight) inaccuracies being very close to the end points.

These would be my preferred methods, but that is just me!

Kaeru Gaman · Post by **Kaeru Gaman** » Tue Jun 10, 2008 9:48 am

I made a sketch:

we know the length of c and of a1 and a2
we search for b1 = b2

we know that c1 + c2 = c
and that b1² = c1²-a1² = c2²-a2²

should be possible to put that into one formula containing only ()² and Sqr()
that can be checked against an alarmlength...

srod · Post by **srod** » Tue Jun 10, 2008 9:54 am

Well, your Pythag is the wrong way round (

), however, if you are simply trying to calculate the distance b1, then that is not a problem. From your triangle, you would need to use some Trigonometry as the equations you cite will actually lead you around in circles!

Personally I would use coordinate geometry to get the distance b1 instead, it's a bit slicker and avoids trigonometry.

Kaeru Gaman · Post by **Kaeru Gaman** » Tue Jun 10, 2008 10:03 am

*shrug* ok...
was just an idea late last night, I thought it could be solvable...

srod · Post by **srod** » Tue Jun 10, 2008 10:14 am

Oh it is solveable, just messy!

But the distance b1 so obtained is the shortest distance from the given point to the extended line anyhow and so extra work is again required, as with all the methods so far outlined; distance based or angle based!

Helle · Post by **Helle** » Tue Jun 10, 2008 12:12 pm

Or:

Code: Select all

;y = ax + b      function for the line
;if you haven´t this function, you need 2 points of this line; P1 with X1 and Y1
;and P2 with X2 and Y2
;then: a = (Y2 - Y1) / (X2 - X1)
;and:  b = Y2 - (a * X2)
;the 3.point with X3 and Y3 is the test-point for collision, then:
;Y3 = a * X3 + Y2 - (a * X2))
;if the left side and the right side are eqal -> collision (P3 is member of the line)
;Test:
;2 points of the line 
X1.f =  5
Y1.f =  4
X2.f = 16
Y2.f =  6
;1 point for test of collision
X3.f = 11
Y3.f =  5

a.f = (Y2 - Y1) / (X2 - X1)
rs.f = a * X3 + Y2 - (a * X2)     ;rs = right side
Y3 - rs

If Y3 < 0
  Y3 = -Y3
EndIf

If Y3 < 0.1                  ;0.1 is a "limit-window" for float (or another value)
  Debug "Collision !"
 Else 
  Debug "No Collision !" 
EndIf

Gruss
Helle

srod · Post by **srod** » Tue Jun 10, 2008 12:25 pm

Aye, but that is testing for an 'exact collision' (right down to the individual pixel) with the entire line through (x1, y1) and (x2, y2). We are dealing with just the line segment between these two points.

Now, whilst it is easy to adjust your code to check for an exact collision within the two end-points, adjusting the code to allow for a 'near collision' is not so easy - at least not if we are to remain accurate. For example, it is not technically accurate to look at the adjusted value of Y3 in your code (although this would be fine for programs in which accuracy can be sacrificed for speed etc.) and to check if it is less than a certain value. This takes no account of the line's direction and will give inconsistent results between lines set at different angles. At this point, we are led inexorably into shortest distance calculations......

zxtunes.com · Post by **zxtunes.com** » Tue Jun 10, 2008 4:28 pm

Helle wrote:Or:

Code: Select all

...
If Y3 < 0.1                  ;0.1 is a "limit-window" for float (or another value)
  Debug "Collision !"
 Else 
  Debug "No Collision !" 
EndIf

Gruss
Helle

Not work.

Kaeru Gaman · Post by **Kaeru Gaman** » Tue Jun 10, 2008 5:26 pm

I bet your Y3 is a LONG....

veganisafreak · Post by **veganisafreak** » Fri Jun 13, 2008 10:04 pm

Hello,

When I was writing an asteroids game I needed a "point in polygon" function, I found this site:

http://www.geometryalgorithms.com/

Looks like it has a distance from point to line function too, with an explanation.

http://www.geometryalgorithms.com/Archi ... m_0102.htm

srod · Post by **srod** » Sat Jun 14, 2008 10:36 am

Yes some nice math there and some familiar old formulas.

akj · Post by **akj** » Sat Jun 14, 2008 12:53 pm

Here is my contribution:

Code: Select all

; PerpDist  AKJ  14-Jun-08
; Perpendicular distance of a point from a line

Procedure.d PerpDist(x1.d,y1.d, x2.d,y2.d, x3.d,y3.d)
; Perpendicular distance of a point (x1,y1) from a line
Protected x0.d, y0.d, l.d, t.d
x0 = x3-x2: y0 = y2-y3
l = x0*x0 + y0*y0
If l=0 ; If the line segment is of zero length
  x0 = x3-x1: y0 = y3-y1
  ProcedureReturn Sqr(x0*x0+y0*y0)
EndIf ; Error
t = ((x3-x1)*y0+(y3-y1)*x0)/l
If t<0.0: t = -t: EndIf
ProcedureReturn t*Sqr(l)
EndProcedure

Debug PerpDist(2,2, 3,4,5,6) ; Point, line
; If the result is less than (say) 0.1 assume a collision has occurred

veganisafreak · Post by **veganisafreak** » Sat Jun 14, 2008 3:28 pm

srod wrote: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!

zxtunes.com · Post by **zxtunes.com** » Sat Jun 14, 2008 4:29 pm

veganisafreak wrote:Hello,

When I was writing an asteroids game I needed a "point in polygon" function, I found this site:

Probably function which I will be useful to probably you use:

x,y - point coordinates
xp(),yp() - poligone coodinates
npol - quantity poligons
c - collison flag

Code: Select all

   j = npol - 1
   FOR i = 0 To npol-1 Step 1 
   
   IF (((( yp(i) <= y) AND (y < yp(j) )) OR ((yp(j) <= y) AND (y < yp(i) ))) AND (x > (xp(j) - xp(i) ) * (y - yp(i) ) / (yp(j) - yp(i) ) + xp(i) )) THEN
       c Xor= 1
   End if    
       
       j = i
   Next i