مقارنة Lat, Long الإحداثيات
https://stackoverflow.com/questions/35870
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لدي قائمة من أكثر من 15 ألف خط العرض و خط الطول الإحداثيات.أي إحداثيات س ، ص ، ما هي أسرع طريقة للعثور على أقرب الإحداثيات على القائمة ؟
المحلول
سوف تحتاج إلى استخدام البناء الهندسي يسمى Voronoi الرسم البياني.هذا يقسم تصل الطائرة إلى عدد من المناطق ، واحدة لكل نقطة ، التي تشمل كل النقاط التي هي الأقرب إلى كل نقاط معينة.
رمز الدقيق خوارزميات لخلق Voronoi الرسم وترتيب البيانات هيكل البحث كبيرة جدا لتناسب في مربع التحرير.:)
@Linor:هذا هو أساسا ما كنت ستفعل بعد إنشاء Voronoi الرسم البياني.ولكن بدلا من جعل شبكة مستطيلة ، يمكنك اختيار تقسيم الخطوط التي تطابق خطوط Voronoi البياني (هذه الطريقة سوف تحصل على عدد أقل من المناطق التي عبر خطوط فاصلة).إذا قمت بشكل متكرر تقسيم الخاص بك Voronoi البياني في نصف طول أفضل الخط الفاصل لكل subdiagram ، ثم يمكنك أن تفعل شجرة البحث عن كل نقطة تريد البحث عنها.وهذا يتطلب قليلا من العمل في خط الهجوم ولكن يوفر الوقت في وقت لاحق.كل بحث يكون على أمر من سجل N حيث N هو عدد من النقاط.16 مقارنات هو أفضل بكثير من 15,000!
نصائح أخرى
أنا فعلت هذا مرة واحدة لموقع ويب.أولا-هاء.العثور على تاجر داخل 50 ميلا من الرمز البريدي الخاص بك.لقد استخدمت الدائرة الكبرى الحساب العثور على الإحداثيات التي كانت على بعد 50 ميلا إلى الشمال ، 50 ميلا شرق 50 ميلا إلى الجنوب و 50 كيلومتر غرب.أن أعطاني min و max اللات و min و max طويلة.من هناك ثم لم استعلام قاعدة البيانات:
select *
from dealers
where latitude >= minlat
and latitude <= maxlat
and longitude >= minlong
and longitude <= maxlong
لأن بعض تلك النتائج سوف يكون لا يزال أكثر من 50 ميلا ، ثم استخدمت الدائرة الكبرى الفورمولا مرة أخرى على قائمة صغيرة من الإحداثيات.ثم طبعت قائمة جنبا إلى جنب مع المسافة من الهدف.
بالطبع إذا أردت البحث عن النقاط القريبة من خط التاريخ الدولي أو البولنديين من هذا لن يعمل.لكنه يعمل كبيرة بالنسبة عمليات البحث داخل أمريكا الشمالية!
المفهوم العام تصفه أنت هو أقرب الجار البحث, وهناك مجموعة كاملة من التقنيات التي تتعامل مع حل هذه الأنواع من الاستفسارات ، إما تماما أو تقريبا.الفكرة الأساسية هي استخدام التقسيم المكاني تقنية للحد من تعقيد من O(n) في الاستعلام (تقريبا) O( log n ) في الاستعلام.
دينار كويتي-الأشجار و المتغيرات دينار كويتي-الأشجار يبدو للعمل بشكل جيد جدا ، ولكن رباعية الأشجار أيضا.نوعية هذه البحث يعتمد على ما إذا كان لديك مجموعة من 15,000 نقطة بيانات ثابتة (أنت لا تضيف الكثير من نقاط البيانات إلى مجموعة مرجعية).جبل آريا العمل على التقريبية أقرب جار مكتبة على حد سواء سهلة الاستخدام وفهم ، حتى من دون أسس جيدة في الرياضيات.فإنه يتيح لك أيضا بعض المرونة في أنواع التحمل من الاستفسارات الخاصة بك.
بل يعتمد عدد المرات التي كنت تريد أن تفعل ذلك ، ما هي الموارد المتاحة - إذا كنت تفعل الاختبار مرة واحدة ، ثم O(log N) تقنيات جيدة.إذا كنت تفعل ذلك ألف مرة على الملقم إنشاء صورة نقطية جدول البحث سيكون أسرع ، أما إعطاء النتيجة مباشرة أو المرحلة الأولى.2GB من الصورة النقطية يمكن أن خريطة العالم كله اللات-الطول إلى 32bit قيمة في 0.011 درجة بكسل (على بعد 1.2 كم عند خط الاستواء) ، ينبغي أن تندرج في الذاكرة.إذا كنت تفعل سوى بلد واحد ، أو يمكن استبعاد الأقطاب, هل يمكن أن يكون أصغر خريطة أو أعلى القرار.على 15000 نقطة ربما يكون أصغر بكثير خريطة - أنا أول الحجم عنه كخطوة أولى إلى القيام اللات-لون الرمز البريدي البحث ، الذي يحتاج إلى دقة أعلى.اعتمادا على متطلبات استخدام تعيين القيمة إلى نقطة في النتيجة مباشرة ، أو قائمة قصيرة من المرشحين (التي من شأنها أن تسمح أصغر الخريطة ، ولكن يتطلب مزيدا من المعالجة اللاحقة - أنت لست في س(1) بحث أراضي أي أكثر من ذلك).
أنت لم تحدد ماذا يعني لك أسرع.إذا كنت ترغب في الحصول على الإجابة بسرعة دون كتابة أي رمز ، وأود أن تعطي gpsbabel دائرة نصف قطرها تصفية الذهاب.
على التوضيحات, وأود أن استخدام هندسي بنية البيانات مثل د. ك-شجرة أو R-شجرة.الخلية لديه نوع البيانات المكانية الذي يفعل ذلك.لغات أخرى/أطر/قواعد بيانات المكتبات لدعم هذا.في الأساس هذه البيانات هيكل يضمن النقاط في شجرة من المستطيلات و البحث الشجرة باستخدام دائرة نصف قطرها.هذا يجب أن تكون سريعة بما فيه الكفاية ، وأعتقد هو أبسط من بناء Voronoi الرسم البياني.أعتقد أن هناك بعض عتبة أعلاه والتي كنت تفضل وأضاف أداء Voronoi الرسم لذلك سوف تكون على استعداد لدفع تعقيد المضافة.
هذا يمكن حلها بطرق عدة.أود في البداية أن معالجة هذه المشكلة عن طريق توليد ديلوناي شبكة ربط أقرب نقطة إلى بعضها البعض.هذا يمكن أن يتحقق مع v. ديلوناي الأوامر في تطبيق نظم المعلومات الجغرافية مفتوحة المصدر العشب.يمكنك إكمال المشكلة في العشب باستخدام واحدة من العديد من شبكة تحليل الوحدات في العشب.بدلا من ذلك, يمكنك استخدام مجانا المكانية RDBMS PostGIS للقيام المسافة الاستعلامات.على PostGIS المكانية الاستعلامات هي إلى حد كبير أكثر قوة من تلك التي في الخلية ، كما أنها ليست مقيدة BBOX العمليات.على سبيل المثال:
SELECT network_id, ST_Length(geometry) from spatial_table where ST_Length(geometry) < 10;
منذ كنت تستخدم خطوط الطول والعرض ، ربما كنت ترغب في استخدام كروي-المسافة وظائف.مع المكاني مؤشر PostGIS جداول جيدا على مجموعات كبيرة من البيانات.
حتى إذا قمت بإنشاء voronoi الرسم, هذا لا يزال يعني تحتاج إلى مقارنة x, y إحداثيات كل 15 الف إنشاء المناطق.لجعل هذا أسهل ، أول شيء خطر في ذهني على الرغم من أن تخلق نوعا من الشبكة على القيم الممكنة, بحيث يمكنك بسهولة وضع x/y تنسيق في واحد من المربعات في الشبكة ، إذا فعلت الشيء نفسه على قائمة المناطق يجب أن يتقلص بسرعة المرشحين المحتملين للمقارنة (لأن الشبكة سيكون أكثر مستطيلة, فمن الممكن ان تكون في عدة مواقع الشبكة).
من السابق لأوانه الأمثل هو أصل كل الشرور.
15K الإحداثيات ليست من ذلك بكثير.لماذا لا تكرار أكثر من 15 ألف الإحداثيات ومعرفة ما إذا كان هذا حقا أداء المشكلة ؟ يمكنك حفظ الكثير من العمل وربما أنه لم يحصل بطيئة جدا حتى إشعار.
كيف كبيرة مساحة هذه الإحداثيات انتشرت ؟ ما latitude هم ؟ كم دقة تحتاج ؟ إذا كانوا إلى حد ما قريبة من بعضها البعض ، ربما يمكنك تجاهل حقيقة أن الأرض كروية وأن أتعامل مع هذا الديكارتي الطائرة بدلا من العبث مع كروية هندسة الدائرة الكبرى المسافات.بالطبع, كما تحصل على مزيد من خط الاستواء درجة من longitute الحصول على أصغر حجما بالمقارنة مع درجات من خط العرض ، لذلك نوعا من عامل القياس قد يكون مناسبا.
تبدأ مع بسيطة إلى حد ما المسافة صيغة القوة الغاشمة البحث و انظر كم من الوقت سيستغرق ذلك و إذا كانت النتائج غير دقيقة بما فيه الكفاية قبل أن تحصل على الهوى.
شكرا للجميع على الإجابات.
@توم @كريس Upchurch:الإحداثيات إلى حد ما قريبة من بعضها البعض ، وهم في منطقة صغيرة نسبيا من حوالي 800 كم مربع.أعتقد أنني يمكن أن تحمل على سطح مسطح.أنا بحاجة إلى عملية الطلبات مرارا وتكرارا ، و يجب أن تكون الاستجابة بشكل أسرع بما فيه الكفاية للحصول على مزيد من تجربة شبكة الإنترنت.
شبكة بسيطة جدا و سريعة جدا.انها في الاساس مجرد 2D مجموعة من القوائم.كل إدخال مجموعة تمثل النقاط التي تقع داخل شبكة الخليوي.من السهل جدا لضبط الشبكة تصل:
for each point p get cell that contains p add point to that cell's list
وأنه من السهل جدا أن ننظر إلى الأمور:
given a query point p get cell that contains p check points in that cell (and its 8 neighbors), against query point p
الجو
لمجرد أن يكون contrairian, هل يعني قريبة في المسافة أو (القيادة) الوقت ؟ في منطقة حضرية أود بكل سرور بالسيارة 5 أميال (5 دقائق) على الطريق السريع من 4 كم (20 دقيقة والتوقف عن الذهاب) في اتجاه آخر.
وهكذا لو كان 'أقرب' متري عليك, كنت أنظر في نظم المعلومات الجغرافية وقواعد البيانات مع وقت السفر المقاييس.
