قم بتخزين النقاط ثنائية الأبعاد لاسترجاعها سريعًا لتلك الموجودة داخل المستطيل

Question

لدي عدد كبير من النقاط ثنائية الأبعاد وأريد الحصول بسرعة على تلك التي تقع في مستطيل معين.دعنا نقول ". هل أي نقطة و "X" هي نقطة أريد أن أجدها داخل مستطيل يحتوي على "T" مثل Topleft و "B" كنقاط أسفل:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

لقد قمت بتجربة مجموعة std::set باستخدام عامل فرز يقوم بفرز النقطة TopLeft في البداية والنقطة BottomRight في نهاية المجموعة.عند الفرز حسب قيمة X أولاً، سيؤدي ذلك إلى العثور على النقاط التالية.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

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

ما هي الطريقة الأفضل للقيام بذلك؟

لغتي هي C++ (Windows) ولدي STL بالإضافة إلى التعزيز المتاح.

تحديث

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

Answer 1

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

في جوهرها، وشجرة المكانية يساعدك تقليم فضاء البحث.

هل يمكن أن يكون قادرا على استخدام الحل الأبسط، مثل تقسيم نقطة في نطاقات. يقول حيث x هو من 0،10 عن مجموعة واحدة، 11،20 كما آخر. أي حل يتيح لك تقليم والفضاء ابحث عن مساعدة.

Answer 2

هذا السؤال . وستوني بروك خوارزمية مستودع لديه بعض تطبيقات KDTrees في C ++، على الرغم من أنها ليست جزءا من المحكمة الخاصة بلبنان ولا دفعة.

Answer 3

والفرز مجموعة يأخذ O (<م> ن سجل <م> ن ) وقت. ببساطة التحقق من كل نقطة على حدة (بدون فرز) يأخذ O (<م> ن ) وقت.

وولهذا، مجرد الذهاب من خلال والتحقق من كل نقطة هو أسرع من الفرز. وانها أسرع من بناء quadtree جدا.

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

Answer 4

استخدم Quadtree، وسيكون لديك 3 أنواع من عقد qtree:

1. العقدة خارج المستطيل المستهدف:يتجاهل
2. العقدة داخل المستطيل المستهدف:تضمين كافة النقاط داخل العقدة
3. العقدة تقع جزئيًا خارج المستطيل:قم بفحص الحدود على النقاط داخل العقدة

Answer 5

وبعد وصلة يوفال F، ولقد وجدت نطاق البحث ، والتي يبدو أن هذا النوع المحدد من الشيء الذي تبحث عنه. تابعت بعض الروابط من هناك، وجدت CGAL ، وهو C مكتبة مفتوحة المصدر ++، الذي ينفذ بحث مجموعة، مع أمثلة هنا .

Answer 6

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