Circumference intersection algorithm

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.

---

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.

---

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.

链接地址: http://www.djcxy.com/p/14866.html

上一篇: 在3D高度图上找到一组装点的圆圈

下一篇: 圆周交点算法