8 posts

Maths Problem.

Back to Forum: Tech Off
• In a GIS system a location is specified by a couple of co-ordinates, 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 = x2-x1
yd = y2-y1
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 in-depth 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 bounding-sphere 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 square-root 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 square-root.

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 Great-circle 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.