تحويل المناطق المحيط بالناقلات (الحدود) إلى خريطة نقطية (شبكة بكسل)

Question

لدي خريطة يتم قطعها إلى عدد من المناطق من قبل الحدود (ملامح) مثل البلدان في خريطة العالم. كل منطقة لديها فئة سطحي معينة س (على سبيل المثال 0 للمياه، 0.03 للعشب ...). يتم تعريف الحدود من خلال:

• ما قيمة س على جانبيها (0.03 على جانب واحد، 0.0 من ناحية أخرى، في المثال أدناه)
• كم عدد النقاط التي يتكون الحدود من (ن= 7 في المثال أدناه)، و
• ن تنسيق أزواج (عاشر, Y.).

هذا مثال واحد.

0.0300      0.0000           7
2660607.5   6332685.5   2660565.0   6332690.5   2660541.5   6332794.5 
2660621.7   6332860.5   2660673.8   6332770.5   2660669.0   6332709.5 
2660607.5   6332685.5

أريد أن أقوم بعمل خريطة نقطية لكل بكسل لها قيمة س المقابلة للمنطقة التي يقع مركز البكسل فيها.

لاحظ أن الحدود تمثل خطوة تغييرات في س. وبعد مختلف القيم س تمثل فصول منفصلة (مثل العشب أو الماء)، وليس القيم التي يمكن أن يتم حسابها (أي العشب الرطب!).

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

هل يمكن لأي شخص أن يوضح لي إلى خوارزمية يمكنها القيام بذلك؟ أنا لا أريد إعادة اختراع العجلة!

Answer 1

الطريقة التي قمت بحلها هي كما يلي:

1. مارس على طول كل قطاع؛ التوقف على فترات منتظمة ل.
2. في كل محطة، ضع نقطة التتبع على الفور إلى اليسار وإلى يمين الجزء (بمسافة صغيرة معينة د من القطاع). تعزى نقاط التتبع القيمة اليسرى واليمين، على التوالي.
3. القيام الاستيفاء الأقرب إلى الجار. يعزى كل نقطة على الشبكة النقطية إلى أقرب نقطة Tracer.

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

هذه ليست خوارزمية تحليلية "مثالية". هناك اثنين من المعلمات: ل و د. وبعد الخوارزمية تعمل بشكل جميل طالما د << ل. وبعد وإلا يمكنك الحصول على عدم الدقة (عادة بكسل واحد) بالقرب من تقاطعات القطاع، وخاصة أولئك الذين لديهم زوايا حادة.

Answer 2

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

يمكن القيام بتقريب مخطط Voronoi بيانيا في OpenGL من خلال رسم كل شريحة سطر كزوج من الكواد مما يجعل شكل خيمة. يستخدم Z-Buffer لجعل أقرب رباعية تأخذ الأسبقية، وبالتالي اللون البكسل بناء على أي خط أقرب. الفرق هنا هو أنك سوف ترغب في تلوين المضلعات بناء على أي جانب من الخط الذي يتم فيه تشغيله، بدلا من الخط الذي يمثلونه. ورقة جيدة تناقش خوارزمية مماثلة هي هوف وآخرون حساب سريع من مخططات Voronoi المعممة باستخدام أجهزة الرسومات

ستبدو الهندسة ثلاثية الأبعاد شيئا مثل هذا المخطط مع 3 قطاعات حمراء / صفراء وشركة واحدة زرقاء / خضراء:

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

قمت بتطبيق هذه الخوارزمية في نص بيثون في http://www.pasteall.org/9062/pothon.. وبعد واحد تحذير مثيرة للاهتمام هو أن استخدام المخاريط لتغطية نهايات الخطوط لم تنجح دون تشويه شكل المخروط، لأن المخاريط التي تمثل نقاط النهاية للقطاعات كانت قتال Z. بالنسبة لنموذج الهندسة التي قدمتها، يشبه الإخراج هذا:

Answer 3

أود أن أوصي بك لاستخدام مكتبة خوارزمية الهندسة مثل cgal.. وبعد خاصة المثال الثاني في صفحة "Polygons 2D" من دليل الإشارة يجب أن توفر لك ما تحتاجه. يمكنك تحديد كل "حدود" كضغى وتحقق مما إذا كانت هناك نقاط معينة داخل المضلعات. لذلك أساسا سيكون شيء مثل

for every y in raster grid
  for every x in raster grid
    for each defined polygon p
      if point(x,y) is inside polygon p
        pixel[X][Y] = inside_color[p]

لست متأكدا من ما يجب القيام به مع الخارج_Color لأن المناطق الخارجية ستتداخلة، لن تكون كذلك؟ على أي حال، بالنظر إلى مثالك، يمكن أن تكون كل منطقة خارجية ماء، لذلك يمكنك فقط القيام نهائي

    if pixel[X][Y] still undefined then pixel[X][Y] = water_value

(أو كبديل، تعيين بكسل [x] [Y] إلى Water_Value قبل التكرار من خلال قائمة المضلع)

Answer 4

• أولا، قم بتحويل جميع حدودك إلى حلقات مغلقة (ربما بما في ذلك حواف خريطتك)، وتحديد اللون الداخلي. يجب أن يكون هذا ممكنا، وإلا يكون لديك تناسق في بياناتك
• استخدم خوارزمية Bresenham لجذب جميع الخطوط الحدودية على خريطتك، بلون واحد غير مستخدم
  • تخزين قائمة بجميع "بكسل الحدود" كما تفعل هذا
• ثم لكل حدود
  • Triangulate IT (Delaunay)
  • تكرر من خلال المثلثات حتى تجد المرء الذي يوجد مركزه داخل حدودك (اختبار بوينت في بوينغون)
  • غمر خرائطك في تلك المرحلة في اللون الداخلي للحدود
• بمجرد ملأت جميع المناطق الداخلية، تكررت من خلال قائمة بكسل الحدود، ورؤية اللون الذي يجب أن يكون كل منهما

Answer 5

• اختيار اثنين من الألوان غير المستخدمة كعلامات "فارغة" و "الحدود"
• ملء جميع المنطقة مع اللون "فارغ"
• ارسم جميع حدوز المنطقة حسب لون "الحدود"
• تكرر من خلال النقاط للعثور على أول واحد مع اللون "فارغ"
• حدد المنطقة التي تنتمي إليها (Google "Point Inside Poolgon"، ربما ستحتاج إلى إغلاق حدودك كما اقترح مارتن ديميلو)
• إجراء خوارزمية ملء الفيضان من هذه النقطة مع لون المنطقة
• انتقل إلى النقطة التالية "فارغة" (لا حاجة لإعادة تشغيل البحث - فقط متابعة)
• وما إلى ذلك حتى لا تبقى نقاط "فارغة"