Tech Off Thread

8 posts

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

Maths Problem.

Back to Forum: Tech Off
  • User profile image
    Ian

    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?

  • User profile image
    Yggdrasil

    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.

  • User profile image
    YellowBook

    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;
    }
    "

  • User profile image
    John Galt

    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.

  • User profile image
    Cannot​Resolve​Symbol

    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.

  • User profile image
    Ian

    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!

  • User profile image
    Matthew van Eerde

    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!

  • User profile image
    Matthew van Eerde

    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.