تغيير الفيضان-الجوريتمية للحصول على أراضي فورونوي لنقطتين بيانات؟

Question

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

كيف يمكنني تغيير هذه الخوارزمية للقيام بـ "الفيضان" لكلا النقطتين Simaltaneuosly أو واحد على الأقل تلو الآخر؟

Answer 1

ماذا تقصد بـ "يمكن أن تصل كل نقطة قبل الآخر"؟

يبدو لي وكأنك بحاجة إلى بحث BF. استخدم قائمة انتظار FIFO مثل:

دع P1 و P2 يكونان مواقع النقطتين.

دع F يكون العنصر الأول في قائمة الانتظار والآخر. في البداية f = 0 ، l = 1. دع Q يكون قائمة الانتظار.

Q[f] = p1
Q[l] = p2
while ( f <= l )
{
   poz = Q[f];
   ++f;

   for each neighbour poz' of poz
      if poz' hasn't been marked yet
      {
         mark poz'
         add poz' to Q: Q[++l] = poz
      }
}

ستحتاج Q إلى أن يكون حجم شبكتك (الصفوف X Cols). يمكنك استخدام اثنين من المصفوفات: أحدهما مع المواضع التي يمكن أن تصل إليها P1 والآخر مع المواضع التي يمكن أن تصل إليها P2 ، أو يمكنك استخدام مصفوفة واحدة ووضع علامة على المربعات P1 مع أرقام إيجابية وتصل المربعات P2 بأرقام سالبة. إذا كنت مهتمًا بالمكان الذي يجتمعون فيه ، فأنت بحاجة فقط إلى التحقق مما إذا كنت على وشك وضع علامة إيجابية من قيمة سالبة (POZ سلبية و POZ إيجابية) أو العكس. سيؤدي ذلك بشكل أساسي إلى الفيضانات الخاصة بك بالدوران: تدفق مربع واحد من P1 ، ثم من P2 ، ثم من P1 ، ثم من P2 وما إلى ذلك.