Page 2 of 3
Posted: Tue Jun 10, 2008 12:13 am
by Kaeru Gaman
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...
Posted: Tue Jun 10, 2008 9:20 am
by srod
@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!
Posted: Tue Jun 10, 2008 9:48 am
by Kaeru Gaman
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...
Posted: Tue Jun 10, 2008 9:54 am
by srod
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.
Posted: Tue Jun 10, 2008 10:03 am
by Kaeru Gaman
*shrug* ok...
was just an idea late last night, I thought it could be solvable...
Posted: Tue Jun 10, 2008 10:14 am
by srod
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!
Posted: Tue Jun 10, 2008 12:12 pm
by Helle
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
Posted: Tue Jun 10, 2008 12:25 pm
by srod
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......
Posted: Tue Jun 10, 2008 4:28 pm
by zxtunes.com
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.
Posted: Tue Jun 10, 2008 5:26 pm
by Kaeru Gaman
I bet your Y3 is a LONG....
Posted: Fri Jun 13, 2008 10:04 pm
by veganisafreak
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
Posted: Sat Jun 14, 2008 10:36 am
by srod
Yes some nice math there and some familiar old formulas.
Posted: Sat Jun 14, 2008 12:53 pm
by akj
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
Posted: Sat Jun 14, 2008 3:28 pm
by veganisafreak
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!
Posted: Sat Jun 14, 2008 4:29 pm
by zxtunes.com
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