1

I have an array of points, of which(points) I know the coordinates(in my coordinate plane, x/y). Then I have a point of unknown coordinates, but I know the distance to that point from "known" points. I'm looking for "unknown" point coordinates. Should be a sort of triangulation.

I've thought about describing the situation with system of equations.

Let suppose this data:

coord[n] basePoints;
double[n] dist;
coord result;

Let think coord like a:

struct {
    double x,y;
};

Now, the circumference equation is:

x^2 + y^2 + ax + bx + c = 0
where:
a = basePoint[i].x
b = basePoint[i].y
c = a^2 + b^2 + r^2
r = dist[i]

In this case, we need 3 points to determine exactly the result point position, so we need a system of three equations. The question is: is there some fast way to find out the result coordinates, and there isn't, is there an algorithm to follow?

edit:

I found the algoritm I was looking for here Trilateration using 3 latitude and longitude points, and 3 distances.

Also a big thanks for @hardmath for the name of method and a wikipedia article.

Community
  • 1
  • 1
Dan Tumaykin
  • 1,213
  • 2
  • 17
  • 37
  • Are you in a position to change `dist` to an array of integers representing the square of the distance, or does it have to happen with a bunch of doubles that are square roots of something and therefore probably imprecise? – harold Jan 18 '12 at 20:31
  • I have an array of points, of which(points) I know the coordinates(in my coordinate plane, x/y). Then I have a point of unknown coordinates, but I know the distance to that point from "known" points. I'm looking for "unknown" point coordinates. It should be a sort of triangulation. – Dan Tumaykin Jan 18 '12 at 20:43
  • The name for this problem is "trilateration". You might want to Google for that term. As it happens [Wikipedia is "out" today](http://en.wikipedia.org/wiki/Trilateration) but this link should get you started when midnight EST rolls around. It's not a hard problem in exact arithmetic, but of course the real world version involves some consideration of measurement errors in the distances, and that makes it a bit more challenging. – hardmath Jan 18 '12 at 20:49
  • @hardmath thanks for the name :) now I know in which direction should I continue my research – Dan Tumaykin Jan 18 '12 at 21:23

2 Answers2

3

Restating the problem: You have n circles centered at basePoint[n] with radius dist[n] which are known to have a single common intersection point. You want to find that one point.

Take the first two circles and find their intersection(s). There are either 1 or 2 (or 0, but then the problem has no solution). If 1, that should be the answer. If 2, disambiguate with the next circle. You could proceed to verify that point is on all of the other circles.

Ben Jackson
  • 90,079
  • 9
  • 98
  • 150
  • sorry, I gave a bad explanation, try to reread the question :) – Dan Tumaykin Jan 18 '12 at 20:48
  • @dtumaykin, sorry, I still don't understand exactly what you are asking. That's why I tried to restate the problem. Can you be specific about how my version is wrong? – Ben Jackson Jan 18 '12 at 20:55
  • 1
    I interpret the problem described in the question the same way as @BenJackson and I can't see a different interpretation. – Alexey Frunze Jan 18 '12 at 20:58
  • You suppose n circumference with same center, and different radius. I suppose n circumferences with different centres. And a point that corresponds to circumferences intersection. – Dan Tumaykin Jan 18 '12 at 21:06
  • @dtumaykin: I suppose *different* centers, each `basePoint[n]` for all `n` – Ben Jackson Jan 18 '12 at 21:08
  • misunderstood you, yes, this is the idea. so, I should just solve a system of two quadratic equations, the question is, is there some fast & easy to code algorithm? – Dan Tumaykin Jan 18 '12 at 21:14
0

First of all, you say you have coordinates of n points, and the distance to the another point(so n distances).

if you have coordinates of only 2 points and you have the distance between those 2 coordinates and a third point(unknown) say X(x,y).

Lets say your first point is A(x1,y1) and your second Point is B(x2,y2)

Now you want to find the unknown Point X(x,y)

you can get distance between A and x like this

d1 = sqrt((x1-x)^2 +(y1-y)^2)

here you already know x1, y1 and d

and similarly distance between B and X will be 

d2 = sqrt((x2-x)^2-(y2-y)^2)

so by these 2 equations, you will get 2 linear equations with 2 unknown variables of this type

mx+ny - d1 = 0

 and 

 px+ qy - d2 = 0

you can solve these two equations to get x and y coordinates of point X(x,y).

you have not mentioned what programming language you are using, but you can implement this using any programming language of your choice. You dont need n points and n distances to calculate the unknown point, you can calculate it using just 2 points.

Rajesh Pantula
  • 10,061
  • 9
  • 43
  • 52
  • I was able to derive from "d1 = sqrt((x1-x)^2 +(y1-y)^2)" only a quadratic equation. Let's suppose for example A(1,2), B(4,2), d1 = 2, d2 = V2. Which linear equations derives from this data? – Dan Tumaykin Jan 18 '12 at 21:05