في منطقة الوصول. ابحث عن المسافة من نقطة إلى منطقة ما وقم بتقليل طلبات الترميز الجغرافي العكسي

لقد اضطررت أكثر من مرة إلى تنفيذ وظيفة حساب المسافة من نقطة جغرافية معينة إلى منطقة على الخريطة - على سبيل المثال ، إلى طريق موسكو الدائري. نتيجة لذلك ، وجدت طريقتين لحل المشكلة التي أظهرت نتائج جيدة ، والآن نستخدمها بانتظام في الإنتاج. سأصفها في الجزء الأول من المقال. وفي الثاني ، سأوضح كيف يمكنك تخزين البيانات الجغرافية مؤقتًا لاستخدام برنامج الترميز الجغرافي أقل.

الجزء الأول طريقتان للعثور على المسافة من نقطة إلى منطقة على الخريطة

إذا كان تطبيق هاتفك المحمول حقيقيًا ، فهو يعمل مع إحداثيات الجهاز. يؤثر موقع المستخدم (والجهاز) على العديد من مؤشرات العمل الخاصة بالتطبيق ، مثل تكلفة التسليم ، عامل التعقيد ، إلخ.
فيما يلي سوف أعرض أمثلة على تنفيذ الخوارزميات في بيثون باستخدام مكتبات scipy وعصرية.
للترميز الجغرافي ، نستخدم خرائط Google. انها تناسب كل من وظيفة وتكلفة الاستخدام. في وقت كتابة هذا التقرير ، تسمح لك Google بتقديم أول 20 ألف طلب ترميز جغرافي شهريًا مجانًا.

الطريقة الأولى: نحسب المسار استنادًا إلى رؤوس المضلع

لنفترض أننا بحاجة إلى إيجاد المسافة من نقطة ما في مكان ما في منطقة موسكو إلى طريق موسكو الدائري. هناك حاجة إلى مسار حقيقي ، وليس مسارًا هندسيًا. لذلك ، أولاً نقوم ببناء مكب نفايات من نقاط الخروج من طريق موسكو الدائري ، ولا يتزامن ذلك مع رؤوس الخطوط العريضة للطريق على الخريطة.

exit_coordinates: List[Tuple[float, float]] latitude: float longitude: float 

للعمل مع الهندسة ، نستخدم المكتبة الأنيقة. من خلال مساعدتها ، من السهل تحديد ما إذا كانت نقطة الاهتمام بالنسبة لنا تقع داخل المضلع أم لا. إذا كان كذلك ، فمن الواضح أن المسافة 0.

 from shapely.geometry import Polygon, Point polygon = Polygon(exit_coordinates) polygon.contains(Point(latitude,longitude)) 

نحن مهتمون بالحالة عندما تكون النقطة خارج المضلع. تعتبر مهمة العثور على أقرب الكائنات (الخروج من MKAD) إلى نقطة البداية نموذجية تمامًا في الرياضيات. عادة ما يتم حلها باستخدام شجرة KD. لذلك دعونا نفعل ذلك. في الثعبان ، يتم تنفيذ الشجرة في مكتبة scipy. سوف نجد أقرب القمم من المخارج من طريق موسكو الدائري إلى وجهة نظرنا.

 from scipy.spatial import KDTree kd_tree = KDTree(exits_coordinates) dists, indexes = kd_tree.query((latitude, longitude), k=3) nearest_coordinates = list() for _, index in zip(dists, indexes): nearest_coordinates.append(exits_coordinates[index]) 

يجب ألا يكون الرقم k - عدد القمم - صغيرًا جدًا ، لأن أقرب مخرج من الطريق الدائري في موسكو قد يتم حظره مؤقتًا. أو قد يكون في مكان ما خارج النهر وليس له طريق مباشر إلى وجهة نظرنا. ك كبير جدا هو أيضا عديمة الفائدة بالنسبة لنا ، لأنه يوجد مخرج مناسب في عدة قمم قريبة. الآن دعنا ننتقل إلى خدمة خرائط Google. لديه بالفعل وظيفة للعثور على مسافات من مجموعة من النقاط إلى نقطة محددة - API Matrix Distance.
تحديث: خدمة API مصفوفة المسافة فواتير الطريق إلى كل ذروة أقرب على حدة. وبالتالي ، هذه الطريقة أغلى من الثانية ، الموضحة أدناه. شكرا sovetnikov

 import googlemaps gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) gmaps_client.distance_matrix( origins=nearest_coordinates, destinations=(latitude, longitude), mode='driving', ) 

يمكننا فقط تحليل الجواب. عادة ما يكون لديه عدة طرق ، والأول ليس دائمًا الأقصر. لذلك ، نختار القيمة المناسبة.

الطريقة 2. نحسب الطريق من مركز المكب

الآن ، بالإضافة إلى رؤوس المضلع ، نحدد نقطة ما داخله ، والتي سنقوم من خلالها ببناء جميع طرق خرائط Google. سنستخدم واجهة برمجة تطبيقات الاتجاهات ، التي ستنشئ طرقًا لنا ، واختر أقصرها.

 start_point: Tuple[float, float], destination: Tuple[float, float] polygon: shapely.geometry.Polygon gmaps_client = googlemaps.Client(key=settings.GOOGLE_MAPS_API_KEY) driving_path = gmaps_client.directions(start_point, destination) 

نبدأ مكررًا من النهاية لإضافة أطوال مقاطع المسار حتى يصبح تنسيق بداية المقطع داخل المضلع (تم حذف التحليل):

 for step in reversed(driving_path): start_point = step['start_location']['lat'], step['start_location']['lng'] if is_inside_polygon(start_point, self.polygon): end_point = step['end_location']['lat'], step['end_location']['lng'] distance += get_part_outside_polygon( get_line(start_point, end_point), polygon ) * step['distance']['value'] break distance += step['distance']['value'] 

يمكننا فقط إضافة جزء من الجزء خارج المضلع. للقيام بذلك ، باستخدام المكتبة الأنيقة ، نقوم ببناء خط هندسي بين إحداثيات بداية ونهاية المسار ونجد كم طوله خارج المضلع. يتم حساب نفس النسبة المئوية من الطول للجزء الذي تم الحصول عليه من المسار.

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

 from shapely.geometry import LineString, Polygon line = LineString(point1, point2) part_outside_len = float(line.difference(polygon).length) / float(line.length) 

بصراحة ، لم أقارن هاتين الطريقتين. لقد تم استخدامها لأكثر من عام ، وكلاهما يعمل دون إخفاقات. قررت عدم رسم تنفيذها بالتفصيل. بدلاً من ذلك ، فتح الوصول إلى مكتبته الجغرافية. يمكن لـ Liba أيضًا استخدام الترميز الجغرافي المنتظم ، بما في ذلك التخزين المؤقت الفعال. القضايا وطلبات السحب هي موضع ترحيب!

الجزء الثاني حفظ عكس الترميز الجغرافي الطلبات

غالبًا ما نحتاج إلى تحديد عناوين النقاط القريبة والمتوافقة مع كائن واحد في العالم الحقيقي. في كل مرة ، لا يكون طلب نظام الترميز الجغرافي الخارجي أمرًا رائعًا ، وهنا تنشأ مسألة التخزين المؤقت بشكل معقول.
عادة ، يرسل العميل الإحداثيات بدقة مفرطة ، على سبيل المثال ، 59.80447691 ، 30.39570337. ولكن كم عدد العلامات في الجزء الكسري ستكون مهمة بالنسبة لنا؟
بالنسبة للكسول وفي عجلة من أمره ، فإن الجواب هو أربعة. للجميع ، انظر التفسير أدناه.

أولا ، الجغرافيا قليلا.

• يبلغ خط الاستواء 40،075.696 كم ، وهو خط عرض صفري.
• خطوط الطول هي خطوط الطول ، عمودي على خطوط الطول. يبلغ طول أي خط طول 40،008.55 كم
• درجة خط العرض - 40،008.55 كم / 360 = 111.134861111 كم. لذلك ، يعطي المائة مائة تغييرًا تقريبًا حوالي كيلومتر ، ويعطي المائة ألف تغييرًا قدره 10 أمتار.
• ينخفض ​​محيط خط العرض من خط الاستواء ، ويضربه جيب التمام بزاوية خط العرض ، لذلك ، بالنسبة إلى 60 درجة من خط العرض (خط العرض سانت بطرسبرغ) ، يكون الطول أقل من مرتين بالضبط. ثم تكون درجة الطول 40.075.696 * 0.5 / 360 = 55.66066888 كم ، أو عشرة آلاف هي 5 أمتار.

خطأ من 1/10000 درجة يعطي مستطيل الخطأ من 5-10 في 10 أمتار. هذا سيسمح لنا بالضبط "الدخول" إلى المبنى ، كما المبنى أكبر بكثير من هذه النقطة. وإذا لم تقع النقطة في المبنى بسبب خطأ ما ، فستظل Google تحدد الأقرب إليها.
تقريب ما يصل إلى ثلاثة أحرف أمر محفوف بالمخاطر ، وقد تم تقليل الدقة بالفعل بشكل كبير. وحتى خمسة - لا معنى لذلك ، لأن دقة أجهزة إرسال GPS لا تتجاوز بضعة أمتار.

وبالتالي ، إذا كانت هناك قيمة في ذاكرة التخزين المؤقت تحتوي على المفتاح "العنوان: 59.8045،30.3957" ، فإن كل الإحداثيات ، عند تقريبها إلى 4 أحرف ، يتم الحصول على نفس المفتاح ، تتوافق مع عنوان واحد تم ترميزه جغرافيًا. نحن نقدم عددًا أقل من الطلبات - نعمل بشكل أسرع وندفع مقابل استخدام خدمة الترميز الجغرافي. الربح!