SQlite Получение ближайшего местоположения (с широтой и долготой)

86

У меня есть данные с широтой и долготой, хранящиеся в моей базе данных SQLite, и я хочу получить ближайшие местоположения по параметрам, которые я ввел (например, мое текущее местоположение - широта / долгота и т. Д.).

Я знаю, что это возможно в MySQL, и я провел довольно много исследований о том, что SQLite нужна специальная внешняя функция для формулы Хаверсина (вычисление расстояния на сфере), но я не нашел ничего, что написано на Java и работает .

Кроме того, если я хочу добавить пользовательские функции, мне нужен org.sqliteфайл .jar (for org.sqlite.Function), и это добавляет приложению ненужный размер.

С другой стороны, мне нужна функция Order by из SQL, потому что отображение расстояния - не такая уж большая проблема - я уже сделал это в моем пользовательском SimpleCursorAdapter, но я не могу отсортировать данные, потому что я в моей базе данных нет столбца расстояния. Это будет означать обновление базы данных каждый раз при изменении местоположения, а это потеря заряда аккумулятора и производительности. Так что если у кого-то есть идея отсортировать курсор по столбцу, которого нет в базе данных, я тоже был бы благодарен!

Я знаю, что существует множество приложений для Android, которые используют эту функцию, но кто-нибудь может объяснить волшебство.

Кстати, я нашел такую ​​альтернативу: запрос на получение записей на основе радиуса в SQLite?

Предлагается создать 4 новых столбца для значений cos и sin для lat и lng, но есть ли другой, не такой избыточный способ?

Юре
источник
Вы проверяли, работает ли org.sqlite.Function у вас (даже если формула неверна)?
Томас Мюллер,
Нет, я нашел (избыточную) альтернативу (отредактированный пост), которая звучит лучше, чем добавление 2,6 МБ .jar в приложение. Но я все еще ищу лучшее решение. Благодарность!
Jure,
Что такое единицы измерения обратного расстояния?
Вот полная реализация для создания запроса SQlite на Android на основе расстояния между вашим местоположением и местоположением объекта.
EricLarch 02

Ответы:

112

1) Сначала отфильтруйте данные SQLite с хорошим приближением и уменьшите объем данных, которые вам нужно оценить в своем java-коде. Для этого используйте следующую процедуру:

Чтобы иметь детерминированный порог и более точный фильтр данных, лучше рассчитать 4 местоположения, которые находятся в radiusметрах от севера, запада, востока и юга от вашей центральной точки в вашем Java-коде, а затем легко проверить меньше или больше чем Операторы SQL (>, <), чтобы определить, находятся ли ваши точки в базе данных в этом прямоугольнике или нет.

Этот метод calculateDerivedPosition(...)рассчитывает эти баллы за вас (p1, p2, p3, p4 на картинке).

введите описание изображения здесь

/**
* Calculates the end-point from a given source at a given range (meters)
* and bearing (degrees). This methods uses simple geometry equations to
* calculate the end-point.
* 
* @param point
*           Point of origin
* @param range
*           Range in meters
* @param bearing
*           Bearing in degrees
* @return End-point from the source given the desired range and bearing.
*/
public static PointF calculateDerivedPosition(PointF point,
            double range, double bearing)
    {
        double EarthRadius = 6371000; // m

        double latA = Math.toRadians(point.x);
        double lonA = Math.toRadians(point.y);
        double angularDistance = range / EarthRadius;
        double trueCourse = Math.toRadians(bearing);

        double lat = Math.asin(
                Math.sin(latA) * Math.cos(angularDistance) +
                        Math.cos(latA) * Math.sin(angularDistance)
                        * Math.cos(trueCourse));

        double dlon = Math.atan2(
                Math.sin(trueCourse) * Math.sin(angularDistance)
                        * Math.cos(latA),
                Math.cos(angularDistance) - Math.sin(latA) * Math.sin(lat));

        double lon = ((lonA + dlon + Math.PI) % (Math.PI * 2)) - Math.PI;

        lat = Math.toDegrees(lat);
        lon = Math.toDegrees(lon);

        PointF newPoint = new PointF((float) lat, (float) lon);

        return newPoint;

    }

А теперь создайте свой запрос:

PointF center = new PointF(x, y);
final double mult = 1; // mult = 1.1; is more reliable
PointF p1 = calculateDerivedPosition(center, mult * radius, 0);
PointF p2 = calculateDerivedPosition(center, mult * radius, 90);
PointF p3 = calculateDerivedPosition(center, mult * radius, 180);
PointF p4 = calculateDerivedPosition(center, mult * radius, 270);

strWhere =  " WHERE "
        + COL_X + " > " + String.valueOf(p3.x) + " AND "
        + COL_X + " < " + String.valueOf(p1.x) + " AND "
        + COL_Y + " < " + String.valueOf(p2.y) + " AND "
        + COL_Y + " > " + String.valueOf(p4.y);

COL_X- это имя столбца в базе данных, в котором хранятся значения широты и COL_Yдолготы.

Итак, у вас есть данные, которые находятся рядом с вашей центральной точкой с хорошим приближением.

2) Теперь вы можете перебирать эти отфильтрованные данные и определять, действительно ли они находятся рядом с вашей точкой (в круге) или нет, используя следующие методы:

public static boolean pointIsInCircle(PointF pointForCheck, PointF center,
            double radius) {
        if (getDistanceBetweenTwoPoints(pointForCheck, center) <= radius)
            return true;
        else
            return false;
    }

public static double getDistanceBetweenTwoPoints(PointF p1, PointF p2) {
        double R = 6371000; // m
        double dLat = Math.toRadians(p2.x - p1.x);
        double dLon = Math.toRadians(p2.y - p1.y);
        double lat1 = Math.toRadians(p1.x);
        double lat2 = Math.toRadians(p2.x);

        double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.sin(dLon / 2)
                * Math.sin(dLon / 2) * Math.cos(lat1) * Math.cos(lat2);
        double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
        double d = R * c;

        return d;
    }

Наслаждайтесь!

Я использовал и настроил эту ссылку и завершил ее.

Бобы
источник
Посетите отличную веб-страницу Криса Венесса, если вы ищете реализацию этой концепции на Javascript. movable-type.co.uk/scripts/latlong.html
barneymc
@Menma x - это широта, а y - долгота. radius: радиус круга, показанного на картинке.
Bobs
приведенное выше решение является правильным и работает. Попробуй ... :)
YS
1
Это приблизительное решение! Он дает очень приблизительные результаты с помощью быстрого , удобного для индексации SQL-запроса. Это даст неправильный результат в некоторых экстремальных обстоятельствах. Если вы получили небольшое количество приблизительных результатов в пределах нескольких километров, используйте более медленные и более точные методы для фильтрации этих результатов . Не используйте его для фильтрации с очень большим радиусом или если ваше приложение будет часто использоваться на экваторе!
user1643723
1
Но я этого не понимаю. CalculateDerivedPosition преобразует координаты lat, lng в декартову, а затем вы в запросе SQL сравниваете эти декартовы значения со значениями lat, long. Две разные геометрические координаты? Как это работает? Спасибо.
Misgevolution
70

Ответ Криса действительно полезен (спасибо!), Но будет работать, только если вы используете прямолинейные координаты (например, ссылки на сетку UTM или ОС). Если для широты / долготы используются градусы (например, WGS84), то вышеуказанное работает только на экваторе. На других широтах вам нужно уменьшить влияние долготы на порядок сортировки. (Представьте, что вы находитесь близко к северному полюсу ... градус широты остается таким же, как и везде, но градус долготы может составлять всего несколько футов. Это будет означать, что порядок сортировки неверен).

Если вы не на экваторе, предварительно вычислите коэффициент выдумки, исходя из вашей текущей широты:

<fudge> = Math.pow(Math.cos(Math.toRadians(<lat>)),2);

Тогда заказывайте по:

((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) + (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN) * <fudge>)

Это все еще только приближение, но намного лучше, чем первое, поэтому неточности порядка сортировки будут намного реже.

Ворсинка
источник
3
Это действительно интересный момент относительно того, что продольные линии сходятся на полюсах и искажают результаты по мере приближения. Хорошее исправление.
Крис Симпсон
1
похоже, это работает cursor = db.getReadableDatabase (). rawQuery ("Выберите ном, идентификатор как _id," + "(" + широта + "- широта) * (" + широта + "- широта) + (" + долгота + "- lon) * (" + longitude + "- lon) *" + fudge + "as distanza" + "from cliente" + "order by distanza asc", null);
max4ever
должно ((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) + (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN) * <fudge>)быть меньше distanceили distance^2?
Bobs
Разве коэффициент выдумки не в радианах, а столбцы в градусах? Разве их нельзя преобразовать в одну и ту же единицу?
Rangel Reale
1
Нет, фактор выдумки - это масштабный коэффициент, равный 0 на полюсах и 1 на экваторе. Это не градусы и не радианы, это просто безразмерное число. Функция Java Math.cos требует аргумента в радианах, и я предположил, что <lat> был в градусах, отсюда и функция Math.toRadians. Но полученный косинус не имеет единиц.
Teasel
68

Я знаю, что на это ответили и приняли, но я подумал, что добавлю свой опыт и решение.

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

Менее чем удовлетворительное решение - вернуть партию, отсортировать и отфильтровать постфактум, но это приведет к тому, что второй курсор и многие ненужные результаты будут возвращены и отброшены.

Мое предпочтительное решение заключалось в передаче в порядке сортировки квадратов значений дельты long и lats:

((<lat> - LAT_COLUMN) * (<lat> - LAT_COLUMN) +
 (<lng> - LNG_COLUMN) * (<lng> - LNG_COLUMN))

Нет необходимости выполнять полный хаверсинус только для порядка сортировки, и нет необходимости извлекать квадратный корень из результатов, поэтому SQLite может обрабатывать вычисления.

РЕДАКТИРОВАТЬ:

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

Крис Симпсон
источник
Отличный ответ. Не могли бы вы объяснить, как это работало и как называется этот алгоритм?
iMatoria
3
@iMatoria - это просто урезанная версия известной теоремы Пифагора. Учитывая два набора координат, разница между двумя значениями X представляет одну сторону прямоугольного треугольника, а разница между значениями Y - другую. Чтобы получить гипотенузу (и, следовательно, расстояние между точками), вы складываете квадраты этих двух значений вместе, а затем извлекаете квадратный корень из результата. В нашем случае мы не делаем последнюю часть (укоренение квадратного корня), потому что не можем. К счастью, для порядка сортировки в этом нет необходимости.
Крис Симпсон
6
В моем приложении BostonBusMap я использовал это решение для отображения ближайших к текущему местоположению остановок. Однако вам нужно масштабировать расстояние по долготе, cos(latitude)чтобы широта и долгота были примерно равны. См en.wikipedia.org/wiki/...
noisecapella
0

Чтобы максимально повысить производительность, я предлагаю улучшить идею @Chris Simpson следующим ORDER BYпредложением:

ORDER BY (<L> - <A> * LAT_COL - <B> * LON_COL + LAT_LON_SQ_SUM)

В этом случае вы должны передать из кода следующие значения:

<L> = center_lat^2 + center_lon^2
<A> = 2 * center_lat
<B> = 2 * center_lon

И вы также должны сохранить LAT_LON_SQ_SUM = LAT_COL^2 + LON_COL^2как дополнительный столбец в базе данных. Заполните его, вставив свои объекты в базу данных. Это немного повышает производительность при извлечении большого количества данных.

Сергей Метлов
источник
-3

Попробуйте что-то вроде этого:

    //locations to calculate difference with 
    Location me   = new Location(""); 
    Location dest = new Location(""); 

    //set lat and long of comparison obj 
    me.setLatitude(_mLat); 
    me.setLongitude(_mLong); 

    //init to circumference of the Earth 
    float smallest = 40008000.0f; //m 

    //var to hold id of db element we want 
    Integer id = 0; 

    //step through results 
    while(_myCursor.moveToNext()){ 

        //set lat and long of destination obj 
        dest.setLatitude(_myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LATITUDE))); 
        dest.setLongitude(_myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LONGITUDE))); 

        //grab distance between me and the destination 
        float dist = me.distanceTo(dest); 

        //if this is the smallest dist so far 
        if(dist < smallest){ 
            //store it 
            smallest = dist; 

            //grab it's id 
            id = _myCursor.getInt(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_ID)); 
        } 
    } 

После этого id будет содержать элемент, который вы хотите получить из базы данных, чтобы вы могли его получить:

    //now we have traversed all the data, fetch the id of the closest event to us 
    _myCursor = _myDBHelper.fetchID(id); 
    _myCursor.moveToFirst(); 

    //get lat and long of nearest location to user, used to push out to map view 
    _mLatNearest  = _myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LATITUDE)); 
    _mLongNearest = _myCursor.getFloat(_myCursor.getColumnIndexOrThrow(DataBaseHelper._FIELD_LONGITUDE)); 

Надеюсь, это поможет!

Скотт Хельм
источник