Tech Off Thread
8 postsForum Read Only
This forum has been made read only by the site admins. No new threads or comments can be added.
Maths Problem.

In a GIS system a location is specified by a couple of coordinates, expressed in metres from a specific location.
EG 5000,5000 represents a particular point on a map and
5000,5050 represents another point 50 metres directly below the first
Here is the question:
What algorithm is required to check whether any other points are within a 50 meter radius of the given point? 
Ian wrote:EG 5000,5000 represents a particular point on a map and 5000,5050 represents another point 50 metres directly below the first
What algorithm is required to check whether any other points are within a 50 meter radius of the given point?
The formula for calculating the distance between any two points is simple. Given (x1,y1) and (x2,y2), you do:
xd = x2x1
yd = y2y1
distance = sqrt(xd*xd + yd*yd).
In a simple (1,1),(1,5) where you'd expect the length to be 4, you have:
xd = 1  1 = 0
yd = 5  1 = 4
distance = sqrt (0*0 + 4*4) = sqrt(16) = 4.
Your case will naturally work the same.
(2,2),(6,5) >
xd = 6  2 = 4
yd = 5  2 = 3
distance = sqrt(4*4 + 3*3) = sqrt(16+9) = sqrt(25) = 5
It's all pythagoras.
Simple explanantion here, more indepth here. 
Another approach be might a games development approach whereby you might use collision detection to determine if any points of interest are within a circle of given radius. Some good articles here: http://www.gamedev.net/reference/list.asp?categoryid=45#199
EDIT:
From one of the above articles:
"
The simplest possible way to do boundingsphere test is to measure the (squared) distance between the two objects in question and to compare the result with the (squared again) sum of their radii. The reason we use the squared distances is to avoid the costly squareroot calculation. The code will look something like this:
"
BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
D3DVECTOR relPos = obj1>prPosition  obj2>prPosition;
float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
float minDist = obj1>fRadius + obj2>fRadius;
return dist <= minDist * minDist;
} 
Neither of these two approaches will work on a sphere (i.e. the earth since you're talking about GIS data).
You have to take into account the bend of the earth which is variable on the lattitude and longitude scale depending on the latitude you're at.
There are a number of products you can buy for really cheap that include this formula to accurately calculate it. 
The curve of the earth is not significant when talking about distances of 50 meters. To determine if something's within a 50 meter radius (provided you know the distances of each from a common point), the easiest method would be Yggdrasil's method. Just iterate through your other possible points. Collision detection seems like it makes the problem a whole lot harder than it is.

Thanks, I'll try this out for real on Monday. I don't think the curvature thing is a problem with the relatively smal distances involved, but its good to know that someone has got that covered as well!

As a performance thing it's faster to square than squareroot.
So your two points were p1 and p2, and the distance you were checking for was d, you could do:
boolean are_within(point p1, point p2, distance d)
return
abs(p1.x  p2.x) <= d && // cheap and fast
abs(p1.y  p2.y) <= d && // cheap and fast
distance_squared(p1, p2) <= d * d // cheaper than sqrt, anyway
;
}
where distance_squared looks like
distance distance_squared(point p1, point p2) {
point offset;
offset.x = p2.x  p1.x;
offset.y = p2.y  p1.y;
return offset.x * offset.x + offset.y * offset.y;
}
EDIT: never mind, YellowBook already covered this point  and in three dimensions, even! 
John Galt wrote:You have to take into account the bend of the earth which is variable on the lattitude and longitude scale depending on the latitude you're at.
The Greatcircle distance formula is discussed on Wikipedia. As you mention, though, the curvature is different at the poles (less) than at the equator (more) but for 50 meters it doesn't make a great deal of difference.
Conversation locked
This conversation has been locked by the site admins. No new comments can be made.