خوارزمية اختبار النجاح في المستطيلات غير المتداخلة

Question

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

الإجابة الواضحة هي أن يكون لديك مصفوفة من المستطيلات وأن تبحث عنها بالتسلسل، مما يجعل البحث O(n).هل هناك طريقة ما لترتيبها حسب الموضع بحيث تكون الخوارزمية أقل من O(n)، على سبيل المثال، O(log n) أو O(sqrt(n))؟

Answer 1

يمكنك تنظيم المستطيلات الخاصة بك في شجرة رباعية أو شجرة KD.هذا يمنحك O(log n).هذه هي الطريقة السائدة.

بنية بيانات أخرى مثيرة للاهتمام لهذه المشكلة هي أشجار R.يمكن أن تكون هذه فعالة جدًا إذا كان عليك التعامل مع الكثير من المستطيلات.

http://en.wikipedia.org/wiki/R-tree

ثم هناك طريقة O(1) التي تقوم ببساطة بإنشاء صورة نقطية بنفس حجم شاشتك، واملأها بعنصر نائب لـ "بدون مستطيل" وارسم مؤشرات المستطيل في تلك الصورة النقطية.يصبح البحث بسيطًا مثل:

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

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

Answer 2

إنشاء شجرة الفاصل الزمني.الاستعلام عن شجرة الفاصل الزمني.راجع "الخوارزميات" من مطبعة معهد ماساتشوستس للتكنولوجيا.

من الأفضل تنفيذ شجرة الفاصل الزمني كشجرة حمراء-سوداء.

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

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

أيضًا، فإن معظم أشجار الفواصل الزمنية للمخزون أو "الكتب الدراسية" تتحقق فقط من فاصل زمني واحد، ولا تُرجع سوى فاصل زمني واحد (لكنك قلت "غير متداخلة"، أليس كذلك؟)

Answer 3

دفعهم في quadtree.

Answer 4

إستخدم بسب شجرة لتخزين المستطيلات.