أفضل أداء الحرجة خوارزمية حل أقرب الجيران

Question

لدينا قائمة من x,y أزواج.كل زوج يمثل نقطة على 2D الفضاء.أريد أن أجد أقرب نقطة من هذه القائمة ، إلى نقطة محددة xq,yq.ما هو أفضل أداء الحرجة خوارزمية هذه المشكلة ؟ من يسب نقاط لن تتغير ؛ مما يعني أنني لا تحتاج إلى تنفيذ الإدراج والحذف.أريد فقط أن تجد أقرب جار الهدف xq,yq نقطة في هذه المجموعة.

تعديل 1:شكرا للجميع!كما Stephan202 وقد خمنت بشكل صحيح, أريد أن أفعل ذلك مرارا ؛ مثل وظيفة.وهي قائمة ليس بالضرورة فرز (في الواقع أنا لا أفهم كيف يمكن أن يكون فرز?مثل طاولة مع مفتاح أساسي من 2 الأعمدة a و y ؟ إذا كان ذلك يساعد ثم فرز).

أنا سوف بناء بنية البيانات استنادا إلى قائمة وقت واحد ، ومن ثم سوف تستخدم هذه البيانات التي تم إنشاؤها هيكل في وظيفة (إذا كانت هذه العملية نفسها هي ذات الصلة).

شكرا يعقوب;يبدو أن د. ك-شجرة هيكل البيانات هو مرشح جيد لكونه الجواب (و أشعر أنه هو.وسوف أقوم بتحديث عندما كنت الحصول على بعض النتائج ذات الصلة).

تحرير 2:لقد وجدت أن هذه المشكلة المسمى "أقرب الجيران"!

تحرير 3:الأولى عنوان "في البحث خوارزمية (المكاني-الاستعلام المكاني-الفهرسة) (أقرب جار)";لقد اختار العنوان الجديد:"أفضل أداء الحرجة خوارزمية حل أقرب الجيران".منذ أن كنت لا ترغب في إجراء الإدراج والحذف العملية على البيانات الأولية و أريد فقط أقرب منها إلى نقطة جديدة (والذي لن يكون إدراج), اخترت أن (حاليا) العمل على دينار كويتي الأشجار.شكرا للجميع!

Answer 1

كما Stephan202 لاحظ إذا كنت ترغب في العثور على أقرب مباراة على أكثر من نقطة واحدة, يجب عليك استخدام شجرة.

أنصح دينار كويتي-الشجرة, التي يمكن العثور عليها بسهولة في العديد من الباقات مثل بنسف 2.0.أو يمكنك تنفيذها بنفسك!

تحرير: سألت سؤال حول kd-شجرة تطبيقات هنا - قد يكون من المفيد.

تحرير: دينار كويتي الأشجار على نطاق واسع تستخدم بنجاح NN البحث :) - أيضا ، إذا كنت على استعداد لقبول التقريبية المباريات ، يمكنك استخدام مكتبة سريع بالنسبة التقريبية أقرب Neigbor (FLANN).على FLANN تنفيذ موجود في بنسف 2.0.

إذا كنت لا تريد إجابات تقريبية يمكنك قرص FLANN المعلمات إلى البحث الشجرة بأكملها.

Answer 2

إذا كان الاستعلام نقطة (xq, yq) يختلف القائمة لا تحتاج إلى حساب Voronoi الرسم البياني قائمة من النقاط.هذا وسوف تعطيك مجموعة من المضلعات أو "الخلايا" (التي هي غير نهائية);كل مضلع يتوافق مع نقطة من القائمة الأصلية ، يسمى "الموقع" من تلك الخلية.أي النقطة التي تقع بالكامل داخل أحد المضلع هو أقرب إلى موقع polygon من المواقع الأخرى على القائمة الأصلية.أي نقطة على الحدود بين اثنين من المضلعات يكمن بعيدة على قدم المساواة من كل موقع.

مرة واحدة كنت قد حصلت على هذا الحد ، تحتاج طريقة سهلة لمعرفة أي مضلع كنت في.هذا هو المعروف موقع نقطة المشكلة.

حقا كتاب جيد لهذا النوع من الشيء هو الهندسة الحسابية:الخوارزميات والتطبيقات.يناقشون كل Voronoi الرسم وحساب شبه منحرف لوح طريقة من موقع نقطة بالتفصيل.

إذا كنت لا تريد أن تفعل الكود بنفسك و لا يجب ، ثم محاولة الحصول على مكتبة مثل CGAL من شأنها أن تفعل أكثر من عمل لك.وهذا ربما ينطبق على دينار كويتي-شجرة الجواب كذلك ، ولكن لا أعرف على وجه التحديد.

Answer 3

وتحتاج إلى مؤشر المكانية .

إذا كنت لفة بنفسك، يمكنك أن تفعل أسوأ بكثير من التقاط R-شجرة خوارزميات رباعية شجرة.

Answer 4

واود ان اذهب مع quadtree. هذا هو الهيكل المكاني أبسط. في 2 أبعاد أنصح عموما quadtree بدلا من دينار شجرة، لأنه هو أبسط وأسرع. الجانب السلبي هو أكثر استهلاك الذاكرة إذا كان عدد من الأبعاد عالية، ولكن في حالة من 2 أبعاد والفرق ليس كبيرا.

وهناك خدعة الأمثل لطيفة إذا الإحداثيات والنقطة العائمة المطبوعة: في استعلام أولا سوف تضطر إلى العثور على أوراق العقدة التي تحتوي على نقطة الذي يطلب من النقطة الأكثر القريب. للقيام بذلك سيكون لديك للذهاب في شجرة من الجذر إلى الورقة - في كل تكرار البت فيها الطفل عقدة خطوة على. تخزين معرفات / عناوين للالعقد التابعة في مجموعة 4 الحجم في بنية عقدة. رقمنة نقطة تنسق في خوارزمية الاستعلام. فإنك سوف تكون قادرة على العثور على عقدة الفرعية المناسبة فقط عن طريق فهرسة مجموعة من 2 بت السليم للإحداثيات نقطة رقمية. رقمية سريعة: تنفيذ ذلك مع static_cast بسيط.

ولكن أولا تنفيذ quadtree دون الأمثل لأنه من السهل لجعل علة لدى عمليات قليلا. حتى من دون هذا التحسين، فإنه لا يزال سيكون أسرع حل.

Answer 5

وتكرار خلال كل نقطة أخرى باستخدام صيغة المسافة للعثور على مسافة لا تقل عن Q (XQ، YQ).

ومع ذلك، لم تعط ما يكفي من المعلومات للحصول على إجابة الأداء حرجة.

وعلى سبيل المثال، إذا Q هو نقطة مشتركة VERY، قد ترغب في حساب المسافة إلى Q وتخزينها مع كل نقطة.

والمثال الثاني، إذا كان لديك عدد كبير من النقاط، قد تنظم النقاط إلى أقسام وتبدأ نقطة فقط في نفس القسم والأقسام المجاورة للقسم الذي يحتوي Q.