Алгоритм многоточечной трилатерации в Java

Я пытаюсь внедрить алгоритм трилатерации в свое приложение для Android, чтобы определить местоположение пользователя в помещении. Я использую сверхширокополосные маяки, чтобы определить расстояние до фиксированных точек. Мне удалось адаптировать метод, предложенный в Метод трилатерации 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);

}

Использование этого подхода дает мне местоположение пользователя, но не очень точное. Как я могу расширить это, чтобы использовать более 3 известных местоположений/расстояний? В идеале N количество точек, где N>=3.


android java gps indoor-positioning-system trilateration
person Chris    schedule 19.05.2015    source источник
comment
Это, безусловно, поможет вам: gis.stackexchange.com/questions/40660/   -  person Chris Stillwell    schedule 20.05.2015
comment
Похоже, что эта ссылка предоставляет решение только с использованием стороннего программного пакета под названием Mathematica. Мне нужно что-то на Java. В идеале мне не нужно включать стороннюю библиотеку или SDK, а просто настроить приведенный выше алгоритм.   -  person Chris    schedule 20.05.2015
comment
Они используют это для обработки чисел, но математика остается той же, используя нелинейный метод наименьших квадратов В математической библиотеке Apache есть все необходимые функции.   -  person Chris Stillwell    schedule 20.05.2015
comment
Честно говоря, математика немного выше моей головы, поэтому попытка преобразовать эту формулу Mathematica в функцию Java проблематична. Не могли бы вы предоставить фрагмент кода? Интересно, что, похоже, есть проблема с алгоритмом, который я вставил выше. Когда я помещаюсь очень близко к одному из маяков (например, в пределах 1 фута), трилатерация приводит к примерно 15 метрам. Я также попытался реализовать алгоритм на странице code.google.com/p/talking-points-3/source/browse/trunk/, но получил аналогичный результат.   -  person Chris    schedule 20.05.2015
comment
@Chris С тех пор ты нашел решение? Я сталкиваюсь с той же проблемой...   -  person Jaythaking    schedule 29.09.2016

Ответы (2)


arrow_upward
9
arrow_downward

При правильной формулировке проблема мультилатерации является задачей оптимизации.

В большинстве научных примеров, например в Википедии, используется ровно три круга и предполагается абсолютно точная информация. Эти обстоятельства позволяют формулировать гораздо более простые задачи с точными ответами и обычно не подходят для практических ситуаций, подобных той, которую вы описываете.

Задача в R2 или R3 евклидовом пространстве с расстояниями, содержащими погрешность измерения, вместо точки обычно получается интересующая площадь (эллипс) или объем (эллипсоид). . Если вместо области требуется точечная оценка, следует использовать центроид площади или центроид объема. Пространство R2 требует не менее 3 невырожденных точек и расстояний для получения уникальной области; и аналогично пространству R3 требуется как минимум 4 невырожденных точки и расстояния для получения уникальной области.

Вот библиотека Java с открытым исходным кодом, которая легко удовлетворит ваши потребности: https://github.com/lemmingapex/Trilateration

трилатерация

Он использует популярный нелинейный оптимизатор наименьших квадратов, алгоритм Левенберга-Марквардта, от Apache Commons Math.

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);
person Scott Wiedemann    schedule 17.09.2015
comment
В моем случае я не даю правильного результата ... Вы пробовали это с реальной точкой местоположения с широтой и широтой? - person Jaythaking; 29.09.2016
comment
@Jaythaking Вам нужно будет преобразовать координаты (широта, долгота, высота) в декартову систему координат, например ECEF: en.wikipedia.org/wiki/ECEF См. github.com/lemmingapex/trilateration/ вопросы/1 - person Scott Wiedemann; 29.11.2016
comment
Я не пробовал реализовать это, но насколько это точно? - person Guru Teja; 25.03.2017
comment
Я использовал приведенное выше решение для трилата. Знаете ли вы, как алгоритм подходит для решения, скажем, например, все три опорные точки находятся на прямой линии, тогда круги сойдутся в двух местах, какое из них он должен считать. другой, например, из-за того, что три круга не имеют общей области пересечения, один из кругов имеет некоторую общую площадь с каждым из других кругов, поэтому у нас здесь 4 точки пересечения, как она будет определять центр тяжести в этом случае - person user3123372; 18.12.2018

arrow_upward
1
arrow_downward

Я нашел это решение в электронной книге;

https://books.google.co.uk/books?id=Ki2DMaeeHpUC&pg=PA78

Я закодировал это в примере Java, и, похоже, он работает очень хорошо для 3 кругов. Однако я понятия не имею, как адаптировать эту формулу для покрытия трилатерации с 4-й и 5-й точкой в ​​решении. Моя математика просто не так хороша.

Мой код для формулы здесь;

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);

}

Вот пример того, что я получаю

В идеале я хотел бы, чтобы кодовое решение могло работать с 3+ узлами, а также, когда использовалось несколько точек, придавало бы решению больший вес в отношении точки, полученной из узлов с малыми значениями радиуса.

У кого-нибудь есть идеи?

Либо как расширить формулу книги для 4+ узлов, либо лучше реализовать код?

person user1667016    schedule 26.06.2015