هل هناك خوارزمية لتحديد المناطق ذات الألوان المتجاورة في شبكة؟

Question

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

ولدي بعض الأفكار، لكنهم جميعا نشعر عدم كفاءة فظيعة.

Answer 1

وأفضل خوارزمية الممكنة هي O (عدد الخلايا)، ولا صلة لعدد من الألوان.

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

وتحرير:

وهنا بسيط مثال رمز زائف من البحث الأول العمق، الذي هو وسيلة سهلة لتنفيذ الرسم البياني اجتياز:

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

Answer 2

وبالإضافة إلى الإجابة عودي عودي، يمكنك استخدام كومة إذا العودية بطيئة جدا:

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

Answer 3

هل يمكن أن تحاول القيام تعبئة الفيضانات في كل مربع. مع انتشار الفيضانات، وتسجيل الساحات الشبكة في صفيف أو شيء من هذا، ولون لهم في اللون غير المستخدمة، ويقول -1.

Answer 4

وهذه المادة ويكيبيديا على ملء الفيضانات قد يكون مفيدا لك هنا: HTTP: //en.wikipedia. غزاله / ويكي / Flood_fill

Answer 5

البيانات

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

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

Answer 6

إذا كنت ترغب في السيطرة الحبوب أكثر غرامة صغيرة، قد تفكر باستخدام A * خوارزمية واستخدام ارشادي لتشمل البلاط الملون بالمثل.

Answer 7

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

وبعد ذلك الموجود في كل خلية إشارة إلى قائمة تحتوي كل خلية متجاورة مع تلك الخلية. ويجمع هذا باقتدار عمل ملء فيضاني بين كل خلية. بدلا من تكرار ذلك لكل خلية. منذ لديك قوائم استبدال البيانات مع البيانات المدمجة هو مجرد بالتكرار عبر قائمة. وسيكون O (ن * ج) حيث n هو عدد الخلايا وج هو مقياس لمدى متجاورة الرسم البياني. وهناك شبكة مفككة تماما أن يكون ن الوقت. A متجاورة تماما الرسم البياني 1 اللون مع كن ن ^ 2/2.