أسرع طريقة للعثور على المسافة بين اثنين من خطوط الطول/العرض النقاط

Question

لدي حاليا فقط في ظل وجود ملايين المواقع في قاعدة بيانات mysql مع كل خطوط الطول والعرض المعلومات.

أنا أحاول أن تجد المسافة بين نقطة واحدة وغيرها الكثير من النقاط عن طريق الاستعلام.إنه ليس بالسرعة التي أريد لها أن تكون خاصة مع 100+ يضرب الثاني.

هل هناك أسرع الاستعلام أو ربما أسرع نظام آخر من الخلية من أجل هذا ؟ أنا باستخدام هذا الاستعلام:

SELECT 
  name, 
   ( 3959 * acos( cos( radians(42.290763) ) * cos( radians( locations.lat ) ) 
   * cos( radians(locations.lng) - radians(-71.35368)) + sin(radians(42.290763)) 
   * sin( radians(locations.lat)))) AS distance 
FROM locations 
WHERE active = 1 
HAVING distance < 10 
ORDER BY distance;

ملاحظة:المقدمة المسافة في ميل.إذا كنت بحاجة إلى كم, استخدام 6371 بدلا من 3959.

Answer 1

• إنشاء الخاصة بك باستخدام نقاط Point القيم Geometry أنواع البيانات في MyISAM الجدول. كما من الخلية 5.7.5, InnoDB الجداول الآن تدعم أيضا SPATIAL المؤشرات.

• إنشاء SPATIAL مؤشر على هذه النقاط

• استخدام MBRContains() للعثور على القيم:

  SELECT  *
  FROM    table
  WHERE   MBRContains(LineFromText(CONCAT(
          '('
          , @lon + 10 / ( 111.1 / cos(RADIANS(@lon)))
          , ' '
          , @lat + 10 / 111.1
          , ','
          , @lon - 10 / ( 111.1 / cos(RADIANS(@lat)))
          , ' '
          , @lat - 10 / 111.1 
          , ')' )
          ,mypoint)
  

, أو في MySQL 5.1 وما فوق:

    SELECT  *
    FROM    table
    WHERE   MBRContains
                    (
                    LineString
                            (
                            Point (
                                    @lon + 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat + 10 / 111.1
                                  ),
                            Point (
                                    @lon - 10 / ( 111.1 / COS(RADIANS(@lat))),
                                    @lat - 10 / 111.1
                                  ) 
                            ),
                    mypoint
                    )

وهذا اختيار كل نقطة تقريبا داخل مربع (@lat +/- 10 km, @lon +/- 10km).

هذا هو في الواقع ليس إلا كروية المستطيل:خطوط الطول والعرض لا بد جزء من مجال.هذا قد تختلف من مستطيل عادي على فرانز جوزيف لاند, ولكن قريبة جدا على معظم الأماكن المأهولة.

• تطبيق تصفية إضافية لتحديد كل شيء داخل الدائرة (لا مربع)

• ربما تطبيق غرامة إضافية تصفية لحساب دائرة كبيرة المسافة (على مسافات كبيرة)

Answer 2

ليس الخلية محددة الإجابة ، ولكن سوف تحسين أداء sql.

ما كنت بفعالية به هو حساب المسافة إلى كل نقطة في الجدول ، لمعرفة إذا كان في غضون 10 وحدات من نقطة معينة.

ما يمكنك القيام به قبل تشغيل sql هذا ، هو إنشاء أربع نقاط رسم مربع 20 وحدة على الجانب الخاص بك نقطة في المركز الأول.ه..(x1,y1 ) ...(x4, س4) ، حيث (x1,y1) هو (givenlong + 10 وحدات givenLat + 10units) ...(givenLong - 10units, givenLat -10 الوحدات).في الواقع ، ما عليك سوى نقطتين ، أعلى اليسار وأسفل اليمين ندعو لهم (X1, Y1) و (X2, Y2)

الآن لديك SQL استخدام هذه النقاط إلى الصفوف يستبعد التي هي بالتأكيد أكثر من 10u من نقطة معينة ، فإنه يمكن استخدام المؤشرات على خطوط العرض & الطول, لذلك سوف تكون أوامر من حجم أسرع من ما لديك حاليا.

على سبيل المثال

select . . . 
where locations.lat between X1 and X2 
and   locations.Long between y1 and y2;

المربع النهج يمكن العودة ايجابيات كاذبة (يمكنك التقاط النقاط في زوايا مربع التي هي > 10u من نقطة معينة) ، لذلك كنت لا تزال بحاجة إلى حساب المسافة من كل نقطة.ومع ذلك هذا مرة أخرى سوف يكون أسرع بكثير لأن لديك بشكل كبير في عدد محدود من النقاط إلى اختبار نقطة داخل منطقة الجزاء.

أنا أسمي هذا الأسلوب "التفكير داخل الصندوق" :)

تحرير: يمكن أن يكون هذا في إحدى SQL البيان ؟

ليس لدي أي فكرة ما mySql و Php قادر على آسفة.أنا لا أعرف من أين أفضل مكان هو بناء أربع نقاط ، أو كيف يمكن أن يكون تم تمريرها إلى الخلية الاستعلام في Php.ومع ذلك, مرة واحدة لديك أربع نقاط ، لا يوجد شيء يمنعك الجمع بين الخاص بك SQL مع الألغام.

select name, 
       ( 3959 * acos( cos( radians(42.290763) ) 
              * cos( radians( locations.lat ) ) 
              * cos( radians( locations.lng ) - radians(-71.35368) ) 
              + sin( radians(42.290763) ) 
              * sin( radians( locations.lat ) ) ) ) AS distance 
from locations 
where active = 1 
and locations.lat between X1 and X2 
and locations.Long between y1 and y2
having distance < 10 ORDER BY distance;

وأنا أعلم مع MS SQL يمكنني بناء SQL التي تعلن أربع عوامات (X1, Y1, X2, Y2) و يحسب لهم قبل "الرئيسية" select كما قلت ليس لدي فكرة إذا كان هذا يمكن أن يتم مع MySql.ومع ذلك أود أن يكون لا يزال يميل إلى بناء أربع نقاط في C# وتمريرها كما المعلمات إلى استعلام SQL.

آسف لا أستطيع المساعدة إذا كان أي شخص يمكن أن يجيب على MySQL & Php أجزاء معينة من هذا, لا تتردد في تحرير هذا الجواب في القيام بذلك.

Answer 3

تحقق من هذا العرض عن إجابة جيدة.في الأساس فإنه يدل على نهجين مختلفين هو مبين في التعليقات, مع شرح مفصل لماذا/متى يجب استخدام واحدة أو أخرى و لماذا "في خانة" الحساب يمكن أن تكون مثيرة جدا للاهتمام.

الجغرافية المسافة البحث مع MySQL

Answer 4

على هذا بلوق وظيفة, التالية الخلية وظيفة تم نشرها.لم يختبر كثيرا لكن من ما جمعت من آخر ، إذا كان لديك خطوط الطول والعرض الحقول المفهرسة, هذه قد تعمل جيدا بالنسبة لك:

DELIMITER $$

DROP FUNCTION IF EXISTS `get_distance_in_miles_between_geo_locations` $$
CREATE FUNCTION get_distance_in_miles_between_geo_locations(geo1_latitude decimal(10,6), geo1_longitude decimal(10,6), geo2_latitude decimal(10,6), geo2_longitude decimal(10,6)) 
returns decimal(10,3) DETERMINISTIC
BEGIN
  return ((ACOS(SIN(geo1_latitude * PI() / 180) * SIN(geo2_latitude * PI() / 180) + COS(geo1_latitude * PI() / 180) * COS(geo2_latitude * PI() / 180) * COS((geo1_longitude - geo2_longitude) * PI() / 180)) * 180 / PI()) * 60 * 1.1515);
END $$

DELIMITER ;

نموذج الاستخدام: على افتراض جدول يسمى الأماكن مع الحقول خطوط الطول والعرض:

حدد get_distance_in_miles_between_geo_locations(-34.017330, 22.809500 ، وخط العرض ، وخط الطول) كما distance_from_input من الأماكن ؛

كل متمزق من هذا المنصب

Answer 5

SELECT * FROM (SELECT *,(((acos(sin((43.6980168*pi()/180)) * 
sin((latitude*pi()/180))+cos((43.6980168*pi()/180)) * 
cos((latitude*pi()/180)) * cos(((7.266903899999988- longitude)* 
pi()/180))))*180/pi())*60*1.1515 ) as distance 
FROM wp_users WHERE 1 GROUP BY ID limit 0,10) as X 
ORDER BY ID DESC

هذا هو حساب المسافة الاستعلام بين النقاط في الخلية ، لقد استخدمت في قاعدة بيانات طويلة ، فإنه يعمل الكمال!ملاحظة:هل التغييرات (اسم قاعدة البيانات, اسم الجدول عمود الخ) وفقا لمتطلبات الخاص بك.

Answer 6

set @latitude=53.754842;
set @longitude=-2.708077;
set @radius=20;

set @lng_min = @longitude - @radius/abs(cos(radians(@latitude))*69);
set @lng_max = @longitude + @radius/abs(cos(radians(@latitude))*69);
set @lat_min = @latitude - (@radius/69);
set @lat_max = @latitude + (@radius/69);

SELECT * FROM postcode
WHERE (longitude BETWEEN @lng_min AND @lng_max)
AND (latitude BETWEEN @lat_min and @lat_max);

المصدر

Answer 7

إذا كنت تستخدم الخلية 5.7.*, ثم يمكنك استخدام st_distance_sphere(نقطة نقطة).

Select st_distance_sphere(POINT(-2.997065, 53.404146 ), POINT(58.615349, 23.56676 ))/1000  as distcance

Answer 8

   select
   (((acos(sin(('$latitude'*pi()/180)) * sin((`lat`*pi()/180))+cos(('$latitude'*pi()/180)) 
    * cos((`lat`*pi()/180)) * cos((('$longitude'- `lng`)*pi()/180))))*180/pi())*60*1.1515) 
    AS distance
    from table having distance<22;

Answer 9

الرمز الكامل مع تفاصيل حول كيفية تثبيت MySQL المساعد هنا: https://github.com/lucasepe/lib_mysqludf_haversine

لقد نشرت هذا العام الماضي التعليق.منذ يرجى @TylerCollier وأشار لي إلى إجابة ، ومن هنا.

طريقة أخرى لكتابة مخصص UDF الدالة التي ترجع haversine المسافة من نقطتين.هذه الوظيفة يمكن أن تأخذ في الإدخال:

lat1 (real), lng1 (real), lat2 (real), lng2 (real), type (string - optinal - 'km', 'ft', 'mi')

لذا نحن يمكن أن أكتب شيئا من هذا القبيل:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2) < 40;

لجلب جميع السجلات مع مسافة أقل من 40 كم.أو:

SELECT id, name FROM MY_PLACES WHERE haversine_distance(lat1, lng1, lat2, lng2, 'ft') < 25;

لجلب جميع السجلات مع مسافة أقل من 25 قدم.

الوظيفة الأساسية هي:

double
haversine_distance( UDF_INIT* initid, UDF_ARGS* args, char* is_null, char *error ) {
    double result = *(double*) initid->ptr;
    /*Earth Radius in Kilometers.*/ 
    double R = 6372.797560856;
    double DEG_TO_RAD = M_PI/180.0;
    double RAD_TO_DEG = 180.0/M_PI;
    double lat1 = *(double*) args->args[0];
    double lon1 = *(double*) args->args[1];
    double lat2 = *(double*) args->args[2];
    double lon2 = *(double*) args->args[3];
    double dlon = (lon2 - lon1) * DEG_TO_RAD;
    double dlat = (lat2 - lat1) * DEG_TO_RAD;
    double a = pow(sin(dlat * 0.5),2) + 
        cos(lat1*DEG_TO_RAD) * cos(lat2*DEG_TO_RAD) * pow(sin(dlon * 0.5),2);
    double c = 2.0 * atan2(sqrt(a), sqrt(1-a));
    result = ( R * c );
    /*
     * If we have a 5th distance type argument...
     */
    if (args->arg_count == 5) {
        str_to_lowercase(args->args[4]);
        if (strcmp(args->args[4], "ft") == 0) result *= 3280.8399;
        if (strcmp(args->args[4], "mi") == 0) result *= 0.621371192;
    }

    return result;
}

Answer 10

سريعة وبسيطة ودقيقة (على مسافات صغيرة) تقريب يمكن القيام به مع كروية الإسقاط.على الأقل في بلدي التوجيه خوارزمية يمكنني الحصول على زيادة بنسبة 20 بالمائة مقارنة مع الحساب الصحيح.في كود جافا يبدو مثل:

public double approxDistKm(double fromLat, double fromLon, double toLat, double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
    double dLon = Math.toRadians(toLon - fromLon);
    double tmp = Math.cos(Math.toRadians((fromLat + toLat) / 2)) * dLon;
    double d = dLat * dLat + tmp * tmp;
    return R * Math.sqrt(d);
}

غير متأكد حول الخلية (آسف!).

تأكد من أنك تعرف عن الحد (الثالث المعلمة من assertEquals يعني دقة بالكيلومترات):

    float lat = 24.235f;
    float lon = 47.234f;
    CalcDistance dist = new CalcDistance();
    double res = 15.051;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 0.1, lon + 0.1), 1e-3);

    res = 150.748;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 1, lon + 1), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 1, lon + 1), 1e-2);

    res = 1527.919;
    assertEquals(res, dist.calcDistKm(lat, lon, lat - 10, lon + 10), 1e-3);
    assertEquals(res, dist.approxDistKm(lat, lon, lat - 10, lon + 10), 10);

Answer 11

هنا هو مفصل جدا وصف الجغرافية المسافة البحث مع الخلية حل يقوم على تنفيذ Haversine الصيغة إلى الخلية.الحل الكامل الوصف مع نظرية وتنفيذ المزيد من الأداء الأمثل.على الرغم من أن المكاني الأمثل جزء لا عمل صحيح في حالتي.http://www.scribd.com/doc/2569355/Geo-Distance-Search-with-MySQL

Answer 12

قراءة الجغرافية المسافة البحث مع MySQL, حل على أساس تنفيذ Haversine الصيغة إلى الخلية.هذا هو الحل الكامل الوصف مع نظرية وتنفيذ المزيد من الأداء الأمثل.على الرغم من أن المكاني الأمثل جزء لا تعمل بشكل صحيح في حالتي.

لاحظت خطأين في هذا:

1. استخدام abs في عبارة select على p8.أنا فقط حذف abs وعملت.

2. المكاني البحث المسافة الدالة على p27 لا يتم تحويل إلى راديان أو ضرب الطول من قبل cos(latitude), ، ما لم يكن له البيانات المكانية يتم تحميلها مع هذا في الاعتبار (لا أستطيع أن أقول من سياق المادة) ، ولكن على سبيل المثال p26 يشير إلى أن البيانات المكانية POINT لم يتم تحميل مع راديان أو درجة.

Answer 13

الخلية الوظيفة التي تقوم بإرجاع عدد من متر بين الإحداثيات:

CREATE FUNCTION DISTANCE_BETWEEN (lat1 DOUBLE, lon1 DOUBLE, lat2 DOUBLE, lon2 DOUBLE)
RETURNS DOUBLE DETERMINISTIC
RETURN ACOS( SIN(lat1*PI()/180)*SIN(lat2*PI()/180) + COS(lat1*PI()/180)*COS(lat2*PI()/180)*COS(lon2*PI()/180-lon1*PI()/180) ) * 6371000

لإرجاع قيمة في شكل مختلف, محل 6371000 في وظيفة مع نصف قطر الأرض في اختيارك الوحدة.على سبيل المثال, كم سيكون 6371 و كم سيكون 3959.

لاستخدام وظيفة فقط اتصل كما تفعل مع أي وظيفة أخرى في الخلية.على سبيل المثال, إذا كان لديك الجدول city, يمكنك أن تجد المسافة بين كل مدينة في كل مدينة:

SELECT
    `city1`.`name`,
    `city2`.`name`,
    ROUND(DISTANCE_BETWEEN(`city1`.`latitude`, `city1`.`longitude`, `city2`.`latitude`, `city2`.`longitude`)) AS `distance`
FROM
    `city` AS `city1`
JOIN
    `city` AS `city2`

Answer 14

أنا في حاجة إلى حل مشكلة مماثلة (تصفية الصفوف من خلال المسافة من نقطة واحدة) ومن خلال الجمع بين الأصلي سؤال مع الإجابات والتعليقات ، توصلت إلى الحل الذي يعمل تماما بالنسبة لي على كل MySQL 5.6 و5. 7.

SELECT 
    *,
    (6371 * ACOS(COS(RADIANS(56.946285)) * COS(RADIANS(Y(coordinates))) 
    * COS(RADIANS(X(coordinates)) - RADIANS(24.105078)) + SIN(RADIANS(56.946285))
    * SIN(RADIANS(Y(coordinates))))) AS distance
FROM places
WHERE MBRContains
    (
    LineString
        (
        Point (
            24.105078 + 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 + 15 / 111.133
        ),
        Point (
            24.105078 - 15 / (111.320 * COS(RADIANS(56.946285))),
            56.946285 - 15 / 111.133
        )
    ),
    coordinates
    )
HAVING distance < 15
ORDER By distance

coordinates هو حقل مع نوع POINT وقد SPATIAL مؤشر
6371 هو لحساب المسافة في كيلومتر
56.946285 هو خط وسط نقطة
24.105078 هو خط الطول المركزي نقطة
10 هو الحد الأقصى المسافة بالكيلومترات

في بلدي التجارب ، MySQL يستخدم المكانية مؤشر على coordinates الميدانية لتحديد بسرعة جميع الصفوف التي يتم داخل المستطيل ثم تحسب المسافة الفعلية لجميع تصفيتها الأماكن استبعاد الأماكن من المستطيلات الزوايا وترك فقط الأماكن داخل الدائرة.

هذا هو التصور من النتيجة:

الرمادي النجوم تصور كل نقطة على الخريطة ، النجوم الصفراء هي تلك التي يتم إرجاعها بواسطة الاستعلام الخلية.الرمادي النجوم داخل زوايا المستطيل (ولكن خارج دائرة) تم اختيارهم من قبل MBRContains() ثم إلغاء تحديد من قبل HAVING البند.

Answer 15

باستخدام mysql

SET @orig_lon = 1.027125;
SET @dest_lon = 1.027125;

SET @orig_lat = 2.398441;
SET @dest_lat = 2.398441;

SET @kmormiles = 6371;-- for distance in miles set to : 3956

SELECT @kmormiles * ACOS(LEAST(COS(RADIANS(@orig_lat)) * 
 COS(RADIANS(@dest_lat)) * COS(RADIANS(@orig_lon - @dest_lon)) + 
 SIN(RADIANS(@orig_lat)) * SIN(RADIANS(@dest_lat)),1.0)) as distance;

انظر: https://andrew.hedges.name/experiments/haversine/

انظر: https://stackoverflow.com/a/24372831/5155484

انظر: http://www.plumislandmedia.net/mysql/haversine-mysql-nearest-loc/

ملاحظة: LEAST يستخدم لتجنب قيم فارغة في التعليق اقترح على https://stackoverflow.com/a/24372831/5155484

Answer 16

$objectQuery = "SELECT table_master.*, ((acos(sin((" . $latitude . "*pi()/180)) * sin((`latitude`*pi()/180))+cos((" . $latitude . "*pi()/180)) * cos((`latitude`*pi()/180)) * cos(((" . $longitude . "- `longtude`)* pi()/180))))*180/pi())*60*1.1515  as distance FROM `table_post_broadcasts` JOIN table_master ON table_post_broadcasts.master_id = table_master.id WHERE table_master.type_of_post ='type' HAVING distance <='" . $Radius . "' ORDER BY distance asc";