خوارزمية تراكم المسافة

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

سطح التكلفة التراكمية

تعيد الخوارزمية التي تستخدمها هذه الأدوات إنشاء السطح من انحداره.

نهج إعادة إنشاء السطح

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

يجيب سطح التكلفة التراكمية عن ثلاثة أسئلة مهمة:

  • أين تزيد التكلفة بسرعة كدالة مسافة؟
  • ما الخلايا المصدر الأقرب لخلية غير مصدر معينة؟
  • ما المسار الذي يجب اتباعه من خلية غير مصدر إلى أقرب خلية مصدر؟

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

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

سطح احتكاك التكلفة البسيط المدخل

افترض أن هناك بيانات نقطية لاحتكاك تكلفة بسيطة تحتوي على قسم مركزي بتكلفة = 3، وقسم متوسط بتكلفة = 2، وقسم خارجي بتكلفة = 1.

البيانات النقطية لاحتكاك التكلفة على شكل حلقات متحدة المركز
تظهر بيانات نقطية لاحتكاك التكلفة على شكل حلقات متحدة المركز مع ظهور نقطة تشير إلى المركز.

يمكن استخدام التفسير ثلاثي الأبعاد لفهم العلاقة بين البيانات النقطية لاحتكاك التكلفة وسطح التكلفة التراكمية الناتج. يُشير ارتفاع السطح h في الخلية c إلى مجموع الانحدارات من البيانات النقطية المدخلة للتكلفة مضروبة في المسافات التي تنشط فيها تلك الانحدارات (h = 3 * d1 + 2 * d2 + 1 * d3).

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

يوضح عرض الخطة للسطح الناتج نفسه الطريقة التي توضح بها خطوط الكونتور تغير التكلفة التراكمية. يتم عرض قيم الانحدار والاتجاه أيضًا في موقع الخلية c. دائمًا ما يكون الاتجاه (اتجاه الهبوط الأكثر حدة) في زوايا قائمة على خط الكونتور.

توضح خطوط الكونتور كيف تتغير التكلفة التراكمية
توضح خطوط الكونتور كيف تتغير التكلفة التراكمية في عرض الخطة لسطح البيانات النقطية.

دمج أقل تكلفة تراكمية

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

تحتوي البيانات النقطية للتكلفة على قيمتين: 1 باللون الرمادي الفاتح و3 باللون الرمادي الداكن. نقطتا المصدر هي S1 وS2. الخلية غير المصدر D أقرب إلى S1 من حيث التكلفة التراكمية.

البيانات النقطية للتكلفة التي تحتوي على نقطتي المصدر S1 وS2 والخلية المصدر D
تتراكب نقاط المصدر المدخلة وخلية مصدر على البيانات النقطية للتكلفة المدخلة.

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

عرض الخطة لسطح التكلفة التراكمية لمصدرين
يظهر عرض الخطة لسطح التكلفة التراكمية الأقل للمصدرين (S1 وS2) من موقع غير مصدر.

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

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

مناطق التخصيص كمستجمعات مياه

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

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

سطح التكلفة التراكمية ذو خطوط الكونتور في عرض ثنائي الأبعاد
يتم عرض سطح تكلفة تراكمية ذو خطوط كونتور في عرض خطة ثنائي الأبعاد.

يظهر عرض ثلاثي الأبعاد للسطح نفسه في الصورة التالية. تمثل المنحدرات في الخلفية حواجز ناتجة عن وجود نهر.

سطح التكلفة التراكمية في عرض منظوري ثلاثي الأبعاد
يظهر عرض منظوري ثلاثي الأبعاد لسطح التكلفة التراكمية.

تتدفق مسارات التكلفة الأقل أسفل سطح التكلفة التراكمية باتجاه المصدر الذي يحدد منطقة التخصيص (مستجمع المياه)، كما هو موضح في الصورة التالية:

منظور ثلاثي الأبعاد لتدفق المسارات الأقل تكلفة
يظهر عرض منظوري ثلاثي الأبعاد لتدفق المسارات الأقل تكلفة أسفل سطح التكلفة التراكمية.

تعد خوارزمية إعادة إنشاء السطح امتدادًا لخوارزمية الشبكة

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

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

شبكة 3 × 3 مع ارتفاع خلية المركز
الشكل 4. تحسب خوارزمية إعادة إنشاء السطح ارتفاع z5 لخلية المركز عن طريق إجراء عدة تقديرات تقريبية لهذا الارتفاع باستخدام الانحدار من البيانات النقطية للتكلفة المدخلة في الخلية المركزية، إلى جانب ارتفاعات zi المعروفة المفترضة للخلايا المجاورة.

على سبيل المثال، يمكن أن يكون أحد التقديرات التقريبية لـ z5 على طول القطر بين z3 وz5، حيث z5 = z3 + 1.4 * حجم الخلية * S، كما هو موضح في الشكل التالي. في هذه الحالة، يتم تفسير S—القيمة المستمدة من البيانات النقطية للتكلفة المدخلة—على أنها انحدار المثلث abc. بالنسبة إلى كل هذه التقديرات التقريبية لنمط الشبكة، يتم استخدام الانحدار عند z5 فقط لتقريب التكلفة التراكمية عند z5. يختلف ذلك عن خوارزمية الشبكة القديمة، والتي تستخدم متوسط التكاليف من أزواج من الخلايا.

حساب الانحدار القطري لخلية واحدة
الشكل 5. يتم عرض حساب الخطوة القطرية. يتم تفسير الانحدار s من سطح احتكاك التكلفة المدخلة على أنه انحدار وتر المثلث abc.

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

مدخلات خطوة إيكونال
الخطوة 6. يتم عرض مدخلات خطوة إيكونال: الارتفاعان، z6 وz8، معروفان.

يتم حساب مقدار تدرج المستوى.

القياس S هو مقدار تدرج المستوى
الشكل 7. يُشير القياس S من البيانات النقطية للتكلفة إلى مقدار تدرج المستوى الذي يمر عبر الارتفاعين المعروفين z8 وz6 والارتفاع غير المعروف z5

يتم حساب اتجاه التدرج.

اتجاه التدرج هو قيمة الاتجاه (الاتجاه الخلفي)
الشكل 8. اتجاه التدرج هو قيمة الاتجاه (الاتجاه الخلفي) للخلية z5.

تستعيد خطوة إيكونال أيضًا معلومات الاتجاه في z5، والذي يُسمى بالاتجاه الخلفي.

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

تتكرر هذه العملية للخلية في كل مرة يتم فيها الحصول على قيمة ارتفاع جديدة لإحدى الخلايا المجاورة لها. في النهاية، تتوقف قيم الارتفاع عن التغير وتنتهي الخوارزمية. توفر المصادر الارتفاعات الأولية: وهي تساوي صفرًا أو قيمة التراكم الأولي لكل مصدر. يتم تعيين قيم الارتفاع الأولية الأخرى على ما لا نهاية. ترد التفاصيل في Sethian (1999). يمثل تطبيق Esri لهذا مزيجًا من التقنيات الموضحة في Sethian (1999) وZhao (2004).

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

مسارات التكلفة الأقل

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

في الأشكال التالية، يظهر مسار التكلفة الأقل المنحني بدءًا من الخلية الزرقاء غير المصدر d في الجزء العلوي الأيمن وينتقل إلى الخلية المصدر السفلية s. في حين أن d أقرب هندسيًا إلى المصدر الأعلى، سيكون الانتقال إلى s باتباع المسار المنحني أقل تكلفة نظرًا إلى ارتفاع التكلفة حول هذا المصدر.

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

توضح الدوائر إنشاء المسار الأقل تكلفة
الشكل 9. يظهر إنشاء المسارات الأقل تكلفة باستخدام سطح التكلفة التراكمية الذي تم إنشاؤه من سطح احتكاك تكلفة المدخل من الشكل 3.

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

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

موقع منطقة الدراسة المميز بمربع
يتم تمييز موقع منطقة الدراسة بالمربع.

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

شبكة متشابكة لقيم الخلايا للبيانات النقطية للاتجاه الخلفي
يظهر عرض شبكي لكيفية تفسير قيم الخلية في البيانات النقطية للاتجاه العكسي.

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

حساب الانحدار الفعلي

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

  • إدخال احتكاك التكلفة، C
  • إدخال السطح، S
  • مضاعف تكلفة المصدر، M
  • دالة العامل الأفقي، HF
  • دالة العامل الرأسي، VF

يحتوي الانحدار الفعلي الذي تستخدمه خوارزمية إعادة الإنشاء على هذا النموذج العام:

الانحدار الفعلي = C * S * M * HF * VF

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

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

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

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

تتصل الحواجز بالحافة

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

تستخدم خوارزمية إعادة إنشاء السطح جميع المجاورات الثمانية للخلية للعثور على تقدير ارتفاعها. لن تمنع مجاورات الحاجز المتصل الزوايا استخدام المجاور القطري للحصول على تقدير ارتفاع. في الصورة أدناه التالية، يمكن الحصول على تقدير ارتفاع لـ z5 من z3، حتى لو كانت الخليتان z2 وz6 حاجزين.

الشبكة ذات الحواجز المتصلة الزوايا

إذا كان من المفترض أن تكون z2 وz6 جزأين من معلم الحاجز الخطي، مثل قناة أو نهر، فإن هذا السلوك سيقوض الغرض من الحاجز. وللحيلولة دون ذلك، تميل خوارزمية إعادة إنشاء السطح إلى ربط الخلايا الحاجزة بدلاً من ربط الخلايا غير الحاجزة. هذا يعني أنه يتم إدخال خلايا NoData إضافية في البيانات النقطية للتكلفة لضمان مشاركة جميع الخلايا الحاجزة الموجودة في الحافة. في الصورة أعلاه، ستصبح الخلية z5 أو الخلية z3 أيضًا خلية حاجزة.

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

‏‏مراجع

دوغلاس دي "مسار أقل تكلفة في نظم GIS باستخدام سطح تكلفة متراكم وخطوط انحدار"، كارتوجرافيكا: المجلة الدولية للمعلومات الجغرافية والتصوير الجغرافي، 1994، مجلد 31، رقم 3، DOI: 10.3138/D327-0323-2JUT-016M

جودشايلد، إم إف "تقييم الحلول الشبكية لمشكلة موقع الممر"، البيئة والتخطيط أ: الاقتصاد والفضاء، 1977، مجلد 9، الصفحات 727-738

سيثيان، جيه ايه طرق تحديد المستوى وطرق التحرك السريع (واجهات متطورة في الشكل الهندسي الحسابي وميكانيكا الموائع والرؤية الحاسوبية وعلوم المادة)، النسخة الثانية، إصدار جامعة كامبريدج، النسخة الثانية (1 يونيو 1999)

وارنتز، دبليو "النقل والطبيعة الاجتماعية وقانون الانكسار"، عالم الجغرافيا المحترف، 1957، مجلد 9 رقم 4، الصفحات 2-7.

تشاو اتش، "الطريقة الأسرع اكتساحًا لمعادلات إيكونال"، الرياضيات والحساب، 2004، مجلد 74، رقم 250، الصفحات 603-627