SQlite Getting nearest locations (with latitude and longitude)

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

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

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

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

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

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

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

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

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

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

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

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

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

Затем закажите по:

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

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

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

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

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

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

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

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

Редактировать:

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

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

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

In this case you should pass the following values from code:

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

And you should also store LAT_LON_SQ_SUM = LAT_COL^2 + LON_COL^2 as additional column in database. Populate it inserting your entities into database. This slightly improves performance while extracting large amount of data.