java Java中的多点三边测量算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30336278/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Multi-point trilateration algorithm in Java
提问by Chris
I'm trying to implement a trilateration algorithm into my Android app to determine a user's indoor location. I'm using ultra-wideband beacons to get the distances to fixed points. I was able to adapt the method suggested in Trilateration Method Android Javaas follows:
我正在尝试在我的 Android 应用程序中实施三边测量算法来确定用户的室内位置。我正在使用超宽带信标来获取到固定点的距离。我能够采用Trilateration Method Android Java 中建议的方法如下：
public LatLng getLocationByTrilateration(
LatLng location1, double distance1,
LatLng location2, double distance2,
LatLng location3, double distance3){
//DECLARE VARIABLES
double[] P1 = new double[2];
double[] P2 = new double[2];
double[] P3 = new double[2];
double[] ex = new double[2];
double[] ey = new double[2];
double[] p3p1 = new double[2];
double jval = 0;
double temp = 0;
double ival = 0;
double p3p1i = 0;
double triptx;
double tripty;
double xval;
double yval;
double t1;
double t2;
double t3;
double t;
double exx;
double d;
double eyy;
//TRANSALTE POINTS TO VECTORS
//POINT 1
P1[0] = location1.latitude;
P1[1] = location1.longitude;
//POINT 2
P2[0] = location2.latitude;
P2[1] = location2.longitude;
//POINT 3
P3[0] = location3.latitude;
P3[1] = location3.longitude;
//TRANSFORM THE METERS VALUE FOR THE MAP UNIT
//DISTANCE BETWEEN POINT 1 AND MY LOCATION
distance1 = (distance1 / 100000);
//DISTANCE BETWEEN POINT 2 AND MY LOCATION
distance2 = (distance2 / 100000);
//DISTANCE BETWEEN POINT 3 AND MY LOCATION
distance3 = (distance3 / 100000);
for (int i = 0; i < P1.length; i++) {
t1 = P2[i];
t2 = P1[i];
t = t1 - t2;
temp += (t*t);
}
d = Math.sqrt(temp);
for (int i = 0; i < P1.length; i++) {
t1 = P2[i];
t2 = P1[i];
exx = (t1 - t2)/(Math.sqrt(temp));
ex[i] = exx;
}
for (int i = 0; i < P3.length; i++) {
t1 = P3[i];
t2 = P1[i];
t3 = t1 - t2;
p3p1[i] = t3;
}
for (int i = 0; i < ex.length; i++) {
t1 = ex[i];
t2 = p3p1[i];
ival += (t1*t2);
}
for (int i = 0; i < P3.length; i++) {
t1 = P3[i];
t2 = P1[i];
t3 = ex[i] * ival;
t = t1 - t2 -t3;
p3p1i += (t*t);
}
for (int i = 0; i < P3.length; i++) {
t1 = P3[i];
t2 = P1[i];
t3 = ex[i] * ival;
eyy = (t1 - t2 - t3)/Math.sqrt(p3p1i);
ey[i] = eyy;
}
for (int i = 0; i < ey.length; i++) {
t1 = ey[i];
t2 = p3p1[i];
jval += (t1*t2);
}
xval = (Math.pow(distance1, 2) - Math.pow(distance2, 2) + Math.pow(d, 2))/(2*d);
yval = ((Math.pow(distance1, 2) - Math.pow(distance3, 2) + Math.pow(ival, 2) + Math.pow(jval, 2))/(2*jval)) - ((ival/jval)*xval);
t1 = location1.latitude;
t2 = ex[0] * xval;
t3 = ey[0] * yval;
triptx = t1 + t2 + t3;
t1 = location1.longitude;
t2 = ex[1] * xval;
t3 = ey[1] * yval;
tripty = t1 + t2 + t3;
return new LatLng(triptx,tripty);
}
Using this approach gives me a user location, but is not terribly accurate. How can I extend this to use more than 3 known locations/distances? Ideally N number of points where N>=3.
使用这种方法为我提供了用户位置，但不是非常准确。如何扩展它以使用超过 3 个已知位置/距离？理想情况下有 N 个点，其中 N>=3。
回答by Scott Wiedemann
When formulated in the correct manner, the multilateration problem is an optimization problem.
当以正确的方式表述时，多边问题是一个优化问题。
Most scholarly examples, like the one on wikipedia, deal with exactly three circles and assume perfectly accurate information. These circumstances allow for much simpler problem formulations with exact answers, and are usually not satisfactory for practical situations like the one you describe.
大多数学术例子，比如维基百科上的例子，正好处理三个圆圈，并假设信息完全准确。这些情况允许更简单的问题公式化和准确的答案，并且通常不能满足您所描述的实际情况。
The problem in R2or R3euclidean space with distances that contain measurement error, an area (ellipse) or volume (ellipsoid) of interest is usually obtained instead of a point. If a point estimate is desired instead of a region, the area centroid or volume centroid should be used. R2space requires at least 3 non-degenerate points and distances to obtain a unique region; and similarly R3space requires at least 4 non-degenerate points and distances to obtain a unique region.
R 2或R 3欧几里得空间中的问题，其距离包含测量误差、感兴趣的面积（椭圆）或体积（椭圆体），通常是获得而不是点。如果需要点估计而不是区域，则应使用面积质心或体积质心。R 2空间至少需要3个非退化点和距离才能得到唯一区域；类似地，R 3空间需要至少4个非退化点和距离才能获得唯一区域。
Here is a open source java library that will easily meet your needs: https://github.com/lemmingapex/Trilateration
这是一个很容易满足你的需求的开源java库：https: //github.com/lemmingapex/Trilateration
It uses a popular nonlinear least squares optimizer, the Levenberg-Marquardt algorithm, from Apache Commons Math.
它使用流行的非线性最小二乘优化器，即来自 Apache Commons Math 的 Levenberg-Marquardt 算法。
double[][] positions = new double[][] { { 5.0, -6.0 }, { 13.0, -15.0 }, { 21.0, -3.0 }, { 12.42, -21.2 } };
double[] distances = new double[] { 8.06, 13.97, 23.32, 15.31 };
NonLinearLeastSquaresSolver solver = new NonLinearLeastSquaresSolver(new TrilaterationFunction(positions, distances), new LevenbergMarquardtOptimizer());
Optimum optimum = solver.solve();
// the answer
double[] calculatedPosition = optimum.getPoint().toArray();
// error and geometry information
RealVector standardDeviation = optimum.getSigma(0);
RealMatrix covarianceMatrix = optimum.getCovariances(0);
回答by user1667016
I found this solution in an e-book;
我在一本电子书中找到了这个解决方案；
https://books.google.co.uk/books?id=Ki2DMaeeHpUC&pg=PA78
https://books.google.co.uk/books?id=Ki2DMaeeHpUC&pg=PA78
I coded this into a Java example and it seems to work pretty well for 3 circles. However, I have no idea how to adapt this formula to cover trilateration with a 4th and 5th point in the solution. My maths is just not that good.
我将它编码到一个 Java 示例中，它似乎对 3 个圈子工作得很好。但是，我不知道如何调整此公式以涵盖解决方案中的第 4 点和第 5 点的三边测量。我的数学不是那么好。
My code for the formula is here;
我的公式代码在这里；
private void findCenter() {
int top = 0;
int bot = 0;
for (int i=0; i<3; i++) {
Circle c = circles.get(i);
Circle c2, c3;
if (i==0) {
c2 = circles.get(1);
c3 = circles.get(2);
}
else if (i==1) {
c2 = circles.get(0);
c3 = circles.get(2);
}
else {
c2 = circles.get(0);
c3 = circles.get(1);
}
int d = c2.x - c3.x;
int v1 = (c.x * c.x + c.y * c.y) - (c.r * c.r);
top += d*v1;
int v2 = c.y * d;
bot += v2;
}
int y = top / (2*bot);
Circle c1 = circles.get(0);
Circle c2 = circles.get(1);
top = c2.r*c2.r+c1.x*c1.x+c1.y*c1.y-c1.r*c1.r-c2.x*c2.x-c2.y*c2.y-2*(c1.y-c2.y)*y;
bot = c1.x-c2.x;
int x = top / (2*bot);
imHere = new Circle(x,y,5);
}
I would ideally like a code solution that could work with 3+ nodes and also, where multiple points were used, would weight the solution more towards the point derived from nodes with small radius values.
理想情况下，我希望代码解决方案可以与 3 个以上的节点一起使用，并且在使用多个点的情况下，会将解决方案的权重更多地指向从具有小半径值的节点导出的点。
Anyone got any ideas?
有人有任何想法吗？
Either how to expand the book formula for 4+ nodes, or a better code implementation?
要么如何扩展4+节点的书本公式，或者更好的代码实现？
