3 points distance calculation strategy

Question

Problem: I have (lat-long) co-ordinates of a lot of points a, b, c, d . . . in the database. Now, when i choose point a, i need to calculate the distances of point a from each of the other points and get the closest one for eg. This math requires cos and tan calculations of the points. So this seems to be quite expensive on the db side.

So i thought of a strategy to simplify this. Below is the explanation of the strategy.

I have 3 known points (x, y, z) the distance between one point to the other is known. For this example lets assume to be 10. i.e. distance from x to y = 10; y to z = 10; z to x = 10. (this forms an equilateral triangle. but real scenario might not be the case)

Now lets say we have two points a and b. we calculate the distances of point a to x, y and z and store respectively and so for point b. (say application logic)

so we have:

• for point a: Ax, Ay and Az
• for point b: Bx, By and Bz

As for the strategy, the question is how can we calculate the distance between point a to point b.

As for the problem itself, if i apply the above strategy to my it, question is am I simplifying or complicating the situation?

Thanks in advance for your answer.

Answer 1

You can calculate the distance between two points using the Pythagorean theorem assuming they are given in Cartesian coordinates, no expensive trigonometry involved.

But this will probably still be to expensive if you have thousands or millions of points. Depending on the database you use it may offer spatial data types and can handle your query efficiently. See for example spatial data in SQL Server.

If your database does not support spatial data the problem becomes quite complex. You need a spatial index with efficient support for nearest neighbor queries. You can start at the Wikipedia article on spatial databases to learn how this problem is usually solved.

If your set of points is stable another option would be to just precompute and store the nearest neighbor for every point but this will get tricky when points are added, deleted or changed.