وضع الملصقات تلقائيًا

الموسوعة الحرة

يشمل وضع الملصقات التلقائي ، والذي يُطلق عليه أحيانًا وضع النصوص أو وضع الأسماء ، أساليب الحاسوب لوضع الملصقات تلقائيًا على الخريطة أو الرسم البياني. ويرتبط هذا بالتصميم الطباعي لهذه الملصقات .

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

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

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

الخوارزميات القائمة على القواعد

تحاول الخوارزميات القائمة على القواعد محاكاة رسام الخرائط البشري الخبير. فعلى مرّ القرون، طوّر رسامو الخرائط فنّ رسم الخرائط ووضع العلامات. فعلى سبيل المثال، يكرّر رسام الخرائط الخبير أسماء الطرق عدة مرات للطرق الطويلة، بدلاً من وضعها مرة واحدة، أو في حالة مدينة أوشن سيتي الموضّحة بنقطة قريبة جدًا من الشاطئ، يضع رسام الخرائط علامة "أوشن سيتي" فوق الأرض للتأكيد على أنها مدينة ساحلية. [ 1 ]

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

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

خوارزميات التحسين المحلي

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

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

تُحقق خوارزمية بسيطة - التلدين المحاكي - نتائج جيدة بأداء جيد نسبيًا. وهي تعمل مثل التحسين المحلي، ولكنها قد تُبقي على تغيير ما حتى لو أدى إلى تدهور النتيجة. احتمالية الإبقاء على هذا التغيير هيخبرة⁡-Δهـتي{\displaystyle \exp {\frac {-\Delta E}{T}}}، أينΔهـ{\displaystyle \Delta E}التغيير في دالة التقييم، وتي{\displaystyle T}تمثل درجة الحرارة . تُخفض درجة الحرارة تدريجيًا وفقًا لجدول التلدين . عندما تكون درجة الحرارة مرتفعة، يُجري التلدين المحاكي تغييرات عشوائية تقريبًا على موضع العلامات، مما يُمكّنه من تجنب الحل الأمثل المحلي . لاحقًا، عندما يتم العثور على حل أمثل محلي جيد جدًا، يتصرف التلدين بطريقة مشابهة للتحسين المحلي. تتمثل التحديات الرئيسية في تطوير حل التلدين المحاكي في اختيار دالة تقييم جيدة وجدول تلدين مناسب. بشكل عام، يؤدي التبريد السريع جدًا إلى تدهور الحل، بينما يؤدي التبريد البطيء جدًا إلى تدهور الأداء، ولكن عادةً ما يكون الجدول خوارزمية معقدة للغاية، تحتوي على أكثر من مُعامل واحد.

وهناك فئة أخرى من خوارزميات البحث المباشر وهي الخوارزميات التطورية المختلفة ، مثل الخوارزميات الجينية .

خوارزميات فرق تسد

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

خوارزميات الرضا من الدرجة الثانية

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

خوارزميات أخرى

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

البرمجة العددية الصحيحة

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

يمكن عادةً إيجاد حل قريب من الحل الأمثل لهذه المسألة متعددة الخيارات في وقت حاسوبي معقول باستخدام استرخاء لاغرانج لحل الصيغة الثنائية لمسألة التحسين. [ 5 ]

كان الحل التجاري الأول لمشكلة تسمية الخرائط، والذي تمت صياغته كمشكلة MCIP وحله عن طريق الاسترخاء اللاغرانجي، هو وضع تسميات الآبار ونقاط التفجير الزلزالي على الخرائط الأساسية لصناعة البترول. [ 6 ]

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

ملحوظات

  1. ↑ سلوكوم، تيري (2010). رسم الخرائط الموضوعية والتصوير الجغرافي . أبر سادل ريفر، نيوجيرسي: بيرسون. ص  576. ISBN 978-0-13-801006-5.
  2. ↑ إيمهوف، إدوارد، "Die Anordnung der Namen in der Karte،" Annuaire International de Cartographie II، Orell-Füssli Verlag، Zürich، 93-129، 1962. الترجمة الإنجليزية: "تحديد موضع الأسماء على الخرائط"، رسام الخرائط الأمريكي ، المجلد 2 # 2 (1975)، الصفحات من 128 إلى 144
  3. ↑ زوراستر، ستيفن (1991). "الأنظمة الخبيرة ومشكلة وضع تسميات الخرائط" . كارتاغرافيكا . 28 (1): 1-9 . doi : 10.3138/P75V-T152-7U53-4170 . ISSN 0317-7173 . 
  4. ↑ دودي، سرينيفاس؛ ماراثي، مادهاف ف.؛ ميرزايان، آندي؛ موريه، برنارد م. إي.؛ تشو، بينهاي (1997)، "تسمية الخرائط وتعميماتها" ، وقائع الندوة الثامنة لجمعية آلات الحوسبة وجمعية الرياضيات التطبيقية والصناعية حول الخوارزميات المنفصلة (SODA) ، جمعية آلات الحوسبة، الصفحات 148-157 ، ISBN  9780898713909فورمان ، م.؛ فاغنر، ف. (1991)، "مشكلة التعبئة مع تطبيقات على كتابة الخرائط"، وقائع الندوة السابعة لجمعية آلات الحوسبة حول الهندسة الحسابية ، ص 281-288 بون ، تشونغ كيونغ؛ تشو، بينهاي؛ تشين، فرانسيس (1998)، "حل زمني متعدد الحدود لتصنيف خريطة مستقيمة"، رسائل معالجة المعلومات ، 65 (4): 201-207 ، doi : 10.1016/S0020-0190(98)00002-7فاغنر ، فرانك؛ وولف، ألكسندر (1997)، "خوارزمية عملية لتسمية الخرائط"، الهندسة الحسابية: النظرية والتطبيقات ، 7 ( 5-6 ): 387-404 ، doi : 10.1016/S0925-7721(96)00007-7.
  5. ↑ بين، جيمس سي. (1984). "خوارزمية لاغرانج لبرنامج الاختيار المتعدد للأعداد الصحيحة" . بحوث العمليات . 32 (5): 1185-1193 . doi : 10.1287/opre.32.5.1185 . ISSN 0030-364X . JSTOR 170661 .  
  6. ↑ زوراستر، ستيفن؛ باير، ستيفن. "التجربة العملية مع برنامج وضع تسميات الخرائط" (ملف PDF) . CaGIS . جمعية رسم الخرائط والمعلومات الجغرافية .

مراجع

  • فريمان، هـ.، معالجة بيانات الخرائط ومشكلة التعليقات التوضيحية، وقائع المؤتمر الإسكندنافي الثالث لتحليل الصور، تشارتويل-برات المحدودة، كوبنهاغن، 1983.
  • Ahn, J. and Freeman, H., “A program for automatic name placement,” Proc. AUTO-CARTO 6, Ottawa, 1983. 444–455.
  • فريمان، هـ.، "وضع اسم الكمبيوتر"، الفصل 29، في نظم المعلومات الجغرافية، 1، دي جيه ماغواير، إم إف غودتشايلد، ودي دبليو رايند، جون وايلي، نيويورك، 1991، 449-460.
  • خوارزميات Podolskaya NN التلقائية لإزالة التعارضات لتطبيقات الرسومات التفاعلية. تكنولوجيا المعلومات (ISSN 1684-6400)، 9، 2007، ص.  45-50. باللغة الروسية: Подольская Н.Н. خوارزميات الإنشاء التلقائي لنماذج التفاعل بين التطبيقات الرسومية. تكنولوجيا المعلومات, 9, 2007, ص. 45-50.
  • كاميدا، ت. وك. إيماي. 2003. وضع تسميات الخرائط للنقاط والمنحنيات. معاملات IEICE لأساسيات الإلكترونيات والاتصالات وعلوم الحاسوب. E86A(4):835–840.
  • ريبيرو جلايدستون ولويز لورينا. 2006. طرق استدلالية لحل مشاكل وضع العلامات على الخرائط. الحوسبة وعلوم الأرض. 32:739-748.
  • فاغنر، ف.، أ. وولف، ف. كابور، وت. ستريك. 2001. ثلاث قواعد تكفي لوضع العلامات بشكل جيد. ألغوريتميكا. 30:334–349.