نقشه راه GIS

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

Telegram Whatsapp Youtube
کاربرد جی ای اس

 

خلاصه

قرار دادن خودکار برچسب نقطه ویژگی (PFLP) یک کار اساسی برای تجسم نقشه است. به عنوان راه حل های غالب برای مشکل PFLP، مدل های موقعیت ثابت و لغزنده به طور گسترده در تحقیقات قبلی مورد مطالعه قرار گرفته اند. با این حال، برچسب های نامزد تولید شده با این مدل ها در موقعیت های ثابت خاصی یا یک خط مسیر مشخص برای لغزش تنظیم می شوند. بنابراین، کل فضای اطراف یک ویژگی نقطه به اندازه کافی برای برچسب گذاری استفاده نمی شود. از این رو، این مقاله یک مدل برچسب جدید بر اساس منطقه قابلیت حرکت، که از نظریه تشخیص برخورد هواپیما می آید، پیشنهاد می کند. این مدل یک فضای جستجوی کامل بدون درگیری را برای قرار دادن برچسب تعریف می کند. با فرض عدم تضاد با ویژگی‌های نقطه، خط و ناحیه، مدل پیشنهادی از ناحیه اطراف ویژگی نقطه برای ایجاد موقعیت‌های برچسب نامزد استفاده می‌کند. با ترکیب با روش جستجوی اکتشافی، مدل به جایگذاری برچسب با کیفیت بالا دست می یابد. علاوه بر این، انعطاف‌پذیری مدل پیشنهادی امکان قرار دادن برچسب‌هایی با شکل دلخواه را فراهم می‌کند.
کلید واژه ها: 

قرار دادن برچسب ؛ نقطه-ویژگی ; تشخیص برخورد ؛ بدون درگیری ؛ جستجوی اکتشافی

 

1. معرفی

برچسب زدن به اشیاء گرافیکی موضوع مهمی در چندین زمینه از جمله نقشه برداری، سیستم های اطلاعات جغرافیایی و تجسم اطلاعات است. برای حفظ کیفیت نمایش بصری، یک برچسب نباید با برچسب ها یا ویژگی های دیگر همپوشانی داشته باشد [ 1 ]. بر این اساس، دو مشکل فرعی، به حداکثر رساندن تعداد برچسب و حداکثر کردن اندازه برچسب ، تعریف شده است [ 2 ]. به طور معمول، برچسب زدن غیر همپوشانی به عنوان NP-hard طبقه بندی می شود [ 3 ، 4 ، 5]. محل قرار دادن برچسب معمولا به سه وظیفه تقسیم می شود: نقاط برچسب گذاری، خطوط برچسب گذاری و مناطق برچسب زدن. از آنجا که برچسب گذاری نقاط مشکل اساسی تری است، قرار دادن برچسب نقطه ویژگی (PFLP) در سال های اخیر به طور گسترده مورد مطالعه قرار گرفته است [ 6 ، 7 ، 8 ، 9 ].
PFLP نیاز به یک مدل برچسب‌گذاری دارد که موقعیت‌های برچسب نامزد را تعریف می‌کند، که به طور مستقیم بر پیاده‌سازی و کیفیت الگوریتم‌های برچسب تأثیر می‌گذارد. دو مدل اصلی در ادبیات پیشنهاد شده است ( شکل 1 را ببینید ): (i) مدل موقعیت ثابت، که در آن هر نقطه دارای مجموعه ای از نامزدهای برچسب ثابت است [ 10 ]. و (ii) مدل لغزنده، که در آن برچسب می تواند به طور مداوم در یک یا چند جهت، تحت محدودیت که مرز آن نقطه مربوطه را لمس کند [ 11 ] بلغزد. این مدل‌ها برای مسئله برچسب‌گذاری رسمی‌سازی می‌کنند تا بتوان آن را به صورت محاسباتی حل کرد.
بیشتر کارهای قبلی در مورد برچسب‌گذاری نقشه بر روی مدل موقعیت ثابت متمرکز است که محبوب‌ترین آن مدل چهار موقعیت است [ 10 ، 12 ]. با نامزدهای برچسب محدود برای هر نقطه، PFLP را می توان به عنوان یک مسئله بهینه سازی ترکیبی تعریف کرد: تخصیص برچسب ها به موقعیت های نامزد به طوری که همه نقاط بدون همپوشانی برچسب-برچسب یا برچسب-ویژگی برچسب گذاری شوند. بر این اساس، طیف گسترده ای از رویکردهای بهینه سازی ترکیبی را می توان برای حل مسئله به کار برد، مانند حریص، نزول گرادیان، بازپخت شبیه سازی شده، برنامه ریزی اعداد صحیح، الگوریتم های ژنتیک و جستجوی تابو [3 ، 13 ، 14 ، 15 ، 16 ] . ماوری و همکاران [ 17] یک مدل برنامه ریزی خطی عدد صحیح 0-1 همراه با تجزیه و آرامش لاگرانژی برای PFLP پیشنهاد کرد. الویم و همکاران [ 18 ] یک الگوریتم برچسب گذاری ویژگی نقطه ای جدید بر اساس چارچوب POPMUSIC (فراتابتکاری بهینه سازی جزئی تحت شرایط تشدید ویژه) پیشنهاد کرد. رابلو و همکاران [ 8 ] یک فراابتکاری جستجوی خوشه بندی را به عنوان یک روش جایگزین جدید برای حل مسئله برچسب گذاری نقطه ارائه کرد.
برای الگوریتم‌های برچسب‌گذاری مبتنی بر مدل موقعیت ثابت، چارچوبی برای جستجوی یک راه‌حل بهینه تقریبی جهانی امکان‌پذیر است. با یک تابع هدف خاص، شماره برچسب بدون تعارض، اولویت نقشه برداری، و برخی دیگر از عوامل کیفیت برچسب را می توان برای به دست آوردن یک نتیجه جامع و بهینه در نظر گرفت [ 3 ، 19]]. با این وجود، مدل موقعیت ثابت دارای اشکالاتی برای برچسب زدن است. از آنجایی که موقعیت‌های برچسب پتانسیل ثابت فاقد انعطاف‌پذیری هستند، هنگام در نظر گرفتن تضاد با ویژگی‌های نقطه، خط و ناحیه، نتیجه برچسب‌گذاری تا حد زیادی تحت تأثیر این محدودیت قرار می‌گیرد. بنابراین، در بین تمام مطالعات موجود بر اساس مدل موقعیت ثابت، بیشتر آزمایش‌های برچسب‌گذاری تنها نقطه‌ای انجام شده است. با این حال، در برچسب‌گذاری نقشه عملی، اگر اطلاعات مهم یک نقطه، خط یا منطقه با هم تداخل داشته باشند، کل تجسم بی‌ارزش است [ 20 ]. علاوه بر این، موقعیت‌های نامزد ثابت نمی‌توانند کل فضای بالقوه اطراف را برای برچسب‌گذاری پوشش دهند. سپس، برچسب بهینه بدون تداخل ممکن است از قلم افتاده باشد زیرا احتمالاً در مجموعه موقعیت ثابت موجود نیست.
طبیعی‌تر از مدل موقعیت ثابت، مدل‌های لغزنده هستند که امکان حرکت پیوسته برچسب را در اطراف ویژگی نقطه‌ای خود فراهم می‌کنند [ 11 ، 21 ، 22 ]. هیرش [ 23 ] نیروهای دفع کننده را برای برچسب های همپوشانی تعریف می کند و از بردارهای ترجمه به طور مکرر برای تغییر مکان برچسب ها استفاده می کند. Doddi [ 24 ] یک مدل برچسب‌گذاری ارائه می‌کند که به هر برچسب اجازه می‌دهد تا حول ویژگی نقطه با هدف به حداکثر رساندن اندازه برچسب بچرخد. یکی دیگر از مدل های اسلایدر محبوب توسط van Kreveld و همکاران تعریف شده است. [ 11 ]، یعنی مدل یک، دو و چهار لغزنده (نشان داده شده در شکل 1). مطالعات زیر که استراتژی لغزشی را اعمال می کنند، بیشتر بر اساس این مدل هستند. Strijk و همکاران [ 25 ] مدل را به برچسب گذاری نقشه عملی، که مربوط به همپوشانی خط، همپوشانی منطقه و ارتفاع برچسب متغیر است، گسترش می دهد. پون و همکاران [ 26 ] یک الگوریتم تقریبی برای قرار دادن برچسب نقطه وزنی با مدل لغزنده پیشنهاد می کند. شوارتگز و همکاران [ 9 ] یک الگوریتم برچسب‌گذاری اکتشافی موثر با برچسب‌های کشویی برای نقشه‌های تعاملی ارائه می‌کند.
مدل لغزنده این محدودیت را حذف می کند که یک برچسب فقط در موقعیت های نامزد محدود قرار می گیرد. به خصوص وقتی که با زمینه های نقطه، خط و منطقه سروکار داریم، راه حلی بدون درگیری به دست می آید. با این حال، محدودیت ها باقی می ماند. از آنجا که لغزش یک برچسب به یک خط مسیر مشخص محدود می شود، از کل فضای برچسب گذاری بالقوه در کنار خط استفاده نمی شود. علاوه بر این، چارچوب مدل لغزنده برای به حداکثر رساندن تعداد برچسب کاربرد بیشتری دارد. برای بهینه سازی کیفیت برچسب، که تمام معیارهای کیفیت مهم (مانند ارتباط برچسب، زیبایی شناسی، و اولویت را ترکیب می کند [ 27 ، 28]])، استراتژی بهینه سازی ترکیبی، که به طور گسترده توسط مدل موقعیت ثابت استفاده می شود، ترجیح داده می شود. علاوه بر این، از آنجایی که مدل لغزنده بیشتر برای برچسب‌گذاری مستطیلی موازی محور اعمال می‌شود، کاوشی در مورد قرار دادن برچسب غیر متنی با شکل دلخواه انجام نشده است. با این حال، بیشتر تکنیک های تجسم اطلاعات از ویژگی های بصری غیر متنی برای نمایش اطلاعات استفاده می کنند [ 20 ].
در برابر این پس زمینه، این مقاله یک مدل برچسب نقطه-ویژگی جدید پیشنهاد می کند که مزایای هر دو مدل موقعیت ثابت و مدل لغزنده را گسترش می دهد. بر اساس “منطقه متحرک” از نظریه تشخیص برخورد [ 29]، این مدل امکان تولید امکان پذیر از مناطق برچسب نامزد را فراهم می کند و بر روی فضای راه حل گسسته برای بهینه سازی ترکیبی، مشابه مدل موقعیت ثابت تمرکز می کند. علاوه بر این، برچسب هایی که شکل دلخواه دارند نیز می توانند مدیریت شوند. فرآیند برچسب‌گذاری شامل سه مرحله اصلی است: (1) با محاسبه ناحیه متحرک برچسب، یک فضای پیوسته و بدون درگیری به دست آورید، سپس به طور مجزا مجموعه‌ای از موقعیت‌های برچسب نامزد برجسته را از این فضای جستجو ایجاد کنید. (2) کیفیت برچسب را برای هر موقعیت برچسب نامزد در مجموعه ارزیابی کمی کنید. و (3) برچسب‌ها را به موقعیت‌های نامزد مربوطه با روش‌های جستجوی تقریبی و اکتشافی اختصاص دهید تا کیفیت کل برچسب‌گذاری را به حداکثر برسانید. از آنجا که هر مرحله را می توان با استفاده از رویکردهای مختلف پیاده سازی کرد،
این مقاله به شرح زیر سازماندهی شده است. در بخش 2 ، شرح مفصلی در مورد منطقه متحرک و فرآیندهای برچسب گذاری ارائه شده است. آزمایش های برچسب گذاری مدل پیشنهادی برای موارد مختلف در بخش 3 آورده شده است . در نهایت، این مطالعه بحثی از نتایج و خلاصه ای از نتیجه گیری را ارائه می کند.

2. روش شناسی

تشخیص برخورد، که شامل برخوردهای احتمالی، منطقه قابلیت حرکت، و مسائل مربوط به مکان برخورد اولیه است، به طور گسترده در گرافیک، شبیه‌سازی، برنامه‌ریزی حرکت ربات و فناوری واقعیت مجازی مورد مطالعه قرار می‌گیرد [30 ، 31 ] . اساساً، قرار دادن برچسب‌ها بدون همپوشانی سایر ویژگی‌های بصری نقطه، خط و ناحیه به دسته اجتناب از برخورد در تشخیص برخورد مسطح تعلق دارد. در این مقاله، با توجه به اصل منطقه متحرک، فضای پتانسیل عاری از تضاد به عنوان مبنایی برای قرار دادن برچسب نقطه-ویژگی بیشتر در رابطه با ویژگی های مختلف پس زمینه به دست می آید.

2.1. منطقه متحرک

ناحیه متحرک [ 29 ، 32 ] در تشخیص برخورد هواپیما به محدوده متحرک یک جسم در هواپیما برای جابجایی جسم صلب با فرض اجتناب از برخورد با موانع پس زمینه اشاره دارد. هنگامی که برای مشکل قرار دادن برچسب اعمال می شود، خود برچسب “شی در هواپیما” است، در حالی که ویژگی های مختلف نقشه “موانع پس زمینه” هستند. بنابراین، منطقه متحرک، فضایی عاری از تضاد را برای برچسب‌گذاری تعریف می‌کند. این مقاله یک استراتژی موثر بر اساس مورفولوژی ریاضی و ترکیبات مرزی برای به دست آوردن این منطقه پیشنهاد می‌کند.
منطقه مشکل جابجایی فرض کنید P = ( p 0 , p 1 , …, p m −1 ) یک چند ضلعی ( p به عنوان نقطه لنگر آن ) در صفحه باشد و Q = ( q 0 , q 1 , …, q n − 1 ) چند ضلعی پس زمینه (خط یا نقطه) باشد. سپس، در چه ناحیه ای چند ضلعی P می تواند خودسرانه بدون برخورد با Q حرکت کند ؟
برای حل این مشکل، ابتدا حالت ساده شده را در نظر می گیریم، که در آن شی پس زمینه Q یک نقطه است، و سپس آن را به پیچیدگی کامل مربوط به خطوط و موانع چند ضلعی گسترش می دهیم. ناحیه قابلیت حرکت برای چند ضلعی P با توجه به نقطه ساده Q در لم 1 تعیین می شود.
لم 1.

فرض کنید P یک چند ضلعی در صفحه و Q نقطه پس زمینه باشد. P از نقطه لنگر خود p دچار جابجایی جسم صلب می شود. سپس، هنگامی که p در نقطه Q قرار دارد، مجموعه مکمل چند ضلعی P’ که با چند ضلعی P در نقطه p مرکزی و متقارن است، ناحیه قابل حرکت P است که با نقطه Φ(p، P، Q نشان داده می شود ) شکل 2 را ببینید ).
همانطور که در شکل 2 نشان داده شده است ، اگر نقطه لنگر p چند ضلعی P در ناحیه سایه دار P قرار داشته باشد ، آنگاه P لزوما با نقطه Q برخورد می کند . در مقابل، اگر p در Φ ( p ، P ، نقطه Q )، مجموعه مکمل P قرار داشته باشد ، P بدون درگیری خواهد بود. بنابراین، Lemma 1 تنها منطقه قابل جابجایی را برای شی پس زمینه نقطه توصیف می کند. هنگامی که به موانع خط یا چند ضلعی گسترش می یابد، پردازش بیشتر زیر باید انجام شود.
لم 2.

فرض کنید P یک چند ضلعی در صفحه و Q خط پس زمینه باشد. P از نقطه لنگر خود p دچار جابجایی جسم صلب می شود. P’ چند ضلعی متقارن مرکزی با P در حدود نقطه p است. سپس، هنگامی که نقطه لنگر p در امتداد خط Q حرکت می کند، کل ناحیه ای که P′ از آن عبور کرده است به عنوان رد P′ شناخته می شود و مجموعه مکمل آن ناحیه قابل حرکت برای P است که با Φ(p, P, Q نمایش داده می شود. خط ) ( شکل 3 را ببینید ).
لم 2 تولید ناحیه متحرک با یک مانع خط را توصیف می کند و توسعه لم 1 است. ایده اصلی این است که خط را به عنوان مجموعه ای از نقاط در نظر بگیریم که مشکل منطقه متحرک با مانع خط را به یک عملیات ترکیبی تبدیل می کند. از مناطق متحرک با موانع نقطه ای که در لمای 1 توضیح داده شده است. موردی که مانع Q یک چند ضلعی است را می توان به همین ترتیب مدیریت کرد. با این حال، از آنجا که ترکیب برای رد P ‘ آسان نیست، از نظریه و روش زیر برای تشکیل یک راه حل کامل برای مشکل منطقه حرکت استفاده می شود.
تعریف 1

(اضافه مینکوفسکی [ 33 ]) . فرض کنید P و Q دو مجموعه دلخواه در فضای Rd باشند . مجموعه حاصل S با قرار دادن P در هر نقطه از Q به دست می آید، یعنی به صورت برداری تمام نقاط P را با نقاط Q اضافه می کنیم. این فرآیند را می توان به صورت زیر نشان داد:

اس=پ“⊕س={ب+تی:ب∈پ“،تی∈س}

که در آن “⊕” مخفف جمع Minkowski است، که در ابتدا مورفولوژی ریاضی را برای پردازش بسط تصویر باینری اعمال می کند. هنگامی که به محاسبات گرافیک برداری بسط داده می شود، این فرآیند به عنوان مجموع مناطقی تعریف می شود که P’ از نقطه لنگر خود p در تمام مناطق مجموعه Q عبور کرده است (همانطور که در شکل 4 نشان داده شده است ). قوش و همکاران یک قضیه جمع مرزی متناظر از چندضلعی ها را برای به دست آوردن نتیجه جمع مینکوفسکی [ 33 ، 34 ] پیشنهاد کرد. نتیجه محاسباتی در شکل 4 نشان داده شده است .

از لمای 1 و 2 و تعریف 1، یک راه حل کامل برای منطقه مشکل جابجایی با موانع نقطه، خط یا چندضلعی در استنتاج 1 ارائه شده است. بنابراین، فضای برچسب‌گذاری بدون درگیری را می‌توان بر اساس آن به دست آورد.
استنباط 1.

فرض کنید P یک چند ضلعی در صفحه و Q نقطه پس زمینه، خط یا چندضلعی آن باشد. P از نقطه لنگر p دچار جابجایی جسم صلب می شود و P’ چندضلعی متقارن P با نقطه p به عنوان مرکز است. سپس، Φ(p، P، Q)، منطقه قابل حرکت برای P، را می توان به عنوان مجموعه مکمل P’ ⊕ Q بیان کرد (همانطور که در شکل 4 نشان داده شده است ).

2.2. فرآیند قرار دادن برچسب

ناحیه متحرک پایه خوبی برای قرار دادن برچسب فراهم می کند. همانطور که قبلا ذکر شد، استراتژی برچسب‌گذاری ما ترجیح می‌دهد PFLP را به عنوان یک مسئله بهینه‌سازی ترکیبی در نظر بگیرد، که نیاز به تعریف دو جزء دارد: یک فضای جستجوی گسسته و یک تابع هدف [ 28 ]. سپس، می توان با استفاده از انواع تقریب ها و رویکردهای جستجوی اکتشافی، مشکل را حل کرد. بر اساس این استراتژی، فرآیند برچسب گذاری را می توان به سه مرحله اساساً مستقل تقسیم کرد [ 35 ]:

(1)
ایجاد موقعیت های نامزد : با توجه به یک ویژگی نقطه، فضای بدون تضاد (منطقه قابلیت جابجایی) را برای برچسب بدست آورید. سپس، این فضای جستجوی پیوسته را به تعدادی موقعیت نامزد مجزا اصلاح کنید.
(2)
ارزیابی موقعیت های نامزد : با توجه به یک برچسب، امتیازی را محاسبه کنید که کیفیت آن را با توجه به عوامل مختلف ارزیابی نشان می دهد.
(3)
انتخاب موقعیت‌های برچسب : با توجه به مجموعه‌ای از موقعیت‌های برچسب نامزد برای هر ویژگی نقطه، یک موقعیت برچسب را از هر مجموعه انتخاب کنید تا کیفیت کلی برچسب‌گذاری، همانطور که در مرحله ارزیابی اندازه‌گیری می‌شود، به حداکثر برسد.

2.2.1. ایجاد موقعیت های نامزدی

در مرحله اول قرار دادن برچسب، فضای جستجوی بدون درگیری برای هر برچسب تولید می شود. سپس، مجموعه‌ای از موقعیت‌های برچسب نامزد مطلوب به طور مجزا بر اساس این فضا انتخاب می‌شوند. برای سهولت توضیح، این فرآیند فقط برای برچسب‌گذاری مستطیلی موازی محور توضیح داده شده است، زیرا سایر برچسب‌های با شکل دلخواه را می‌توان به روشی مشابه مدیریت کرد.
طبیعی تر از مدل موقعیت ثابت یا مدل لغزنده، نکته کلیدی مدل ما این است که منطقه اطراف یک ویژگی نقطه برای قرار دادن برچسب استفاده می شود. همانطور که از شکل 5 مشاهده می شود ، فضای جستجوی سه مدل اصلی برچسب گذاری ارائه شده است (تعریف شده توسط محل نقطه میانی برچسب). برای مدل موقعیت ثابت با هشت نامزد، فضای جستجو در شکل 5 a با هشت نقطه نشان داده شده است، و خط مستطیلی در شکل 5 b نشان دهنده فضای جستجو برای مدل لغزنده است. فضای جستجوی مدل ما در شکل 5 ج با یک مستطیل گرد نشان داده شده است. بنابراین، برای هر برچسب در این فضا، فاصله آن تا ویژگی نقطه کمتر از مقدار آستانه r است، و با ویژگی نقطه همپوشانی ندارد. فضاهای جستجوی مدل موقعیت ثابت و مدل لغزنده توسط فضای جستجوی مدل ما وجود دارد. نتیجه برچسب‌گذاری از فضای جستجوی گسترده و کامل بهره می‌برد.

(i) نسل فضای جستجوی نامزد

با توجه به تعریف اولیه و محاسبات هندسی منطقه متحرک ارائه شده در بخش 2.1 ، فضای جستجوی بدون درگیری برای یک برچسب مستطیلی را می توان به دست آورد. به طور خاص، جعبه متن برچسب مستطیلی به عنوان چند ضلعی P در استنتاج 1 در نظر گرفته می شود، و نقطه میانی جعبه متن به عنوان نقطه لنگر p انتخاب می شود . از آنجا که جعبه متن برچسب با نقطه p متقارن است ، سپس P = P است . مناطق “تحرک” برای نقطه اصلی، خط و ویژگی منطقه در جدول 1 نشان داده شده است .
سپس، فضای جستجوی نامزد بدون درگیری یک ویژگی نقطه ای با گرفتن مجموعه مکمل این مناطق غیرحرکتی ایجاد می شود. نمودار جریان دقیق این فرآیند در شکل 6 نشان داده شده است، که در آن (الف) نمودار شماتیک ویژگی نقطه، اندازه جعبه متن برچسب، و کل فضای جستجوی اطراف برای برچسب زدن را نشان می دهد (همانطور که قبلا در شکل 5 توضیح داده شده است.ج). سپس، یک مورد قرار دادن برچسب در (ب) نشان داده می‌شود، که نقطه نشان‌دهنده ویژگی نقطه‌ای است که باید برچسب‌گذاری شود، در حالی که سایر نقاط، خطوط و مناطق ویژگی‌های مانع مجاور هستند. ناحیه مربوط به عدم حرکت در (c) نشان داده شده است که با ناحیه سایه‌دار مشخص می‌شود. در نهایت، کل فضای برچسب‌گذاری بدون تضاد در (d) به دست می‌آید، همانطور که با ناحیه خاکستری در جعبه چین نشان داده شده است. تنها در صورتی که نقطه میانی برچسب در این ناحیه قرار داشته باشد، هیچ تضادی با این ویژگی های پس زمینه وجود ندارد.

(ب) انتخاب موقعیت برچسب نامزد

منطقه برچسب نامزد مجموعه کاملی از فضای بدون درگیری را برای قرار دادن برچسب فراهم می کند. در این مرحله، فضای جستجوی پیوسته به تعداد معینی، n ، از موقعیت‌های برچسب نامزد اصلاح می‌شود. برای انتخاب n موقعیت، اولویت مکان برچسب در نظر گرفته می شود که شامل دو عامل اصلی است: فاصله برچسب-ویژگی و اولویت جهت برچسب. برای ترکیب این عوامل، تحقیق با انتخاب نقاط گسسته روی جعبه متن برچسب به عنوان مرجع برای محاسبه فاصله، تمام n موقعیت برچسب را از جهات مختلف در منطقه برچسب نامزد به دست می‌آورد. سپس n موقعیت به دست آمده به عنوان موقعیت نامزد انتخاب می شود. همانطور که در شکل 7 نشان داده شده است، فرآیندهای دقیق زیر به کار گرفته می شوند:
(1)
همانطور که در شکل 7 الف نشان داده شده است، طرح کلی جعبه متن برچسب را به طور مساوی با فواصل افقی و عمودی w و h تقسیم کنید تا n نقطه گسسته به عنوان نقاط مرجع برای محاسبه فاصله ایجاد شود .
(2)
نقطه M را به عنوان نقطه مرجع از n نقطه گسسته انتخاب کنید. سپس، در داخل منطقه برچسب نامزد، موقعیتی را که نقطه M از آن نزدیک به ویژگی نقطه است، پیدا کنید تا موقعیت برچسب نامزد باشد، همانطور که در شکل 7 ب نشان داده شده است.
(3)
مرحله 2 را تکرار کنید تا تمام نقاط مرجع دیگر برای n موقعیت برچسب نامزد انتخاب شود. (زمانی که ویژگی های نقشه بیش از حد شلوغ هستند، موقعیت های نامزد به دلیل محدود بودن منطقه برچسب نامزد ایجاد نمی شوند؛ بنابراین، موقعیت های پیش فرض در مدل موقعیت ثابت استفاده می شود.)
از آنجا که مدل موقعیت ثابت با چهار نامزد معمولاً در تحقیقات قبلی برای برچسب‌گذاری نقشه استفاده می‌شود، به عنوان مقایسه، وقتی w و h برابر با عرض و ارتفاع جعبه متن برچسب تنظیم می‌شوند، چهار نامزد تولید شده توسط مدل ما نشان داده می‌شوند. شکل 8 . چهار نقطه مرجع برای محاسبه فاصله در شکل 8 الف نشان داده شده است. چهار موقعیت برچسب نامزد ایجاد شده برای مورد بدون مانع و مورد با مانع در شکل 8 b,c ارائه شده است (خطوط و مناطق مانع با خطوط نقطه چین در شکل نشان داده شده اند). برای مدل موقعیت ثابت و مدل لغزنده، نامزدهای بدون درگیری در شکل 8ج از دست رفته است.

2.2.2. ارزیابی سمت های کاندیدا

برای مقایسه راه حل های مختلف برچسب زدن، یک امتیاز کمی برای نشان دادن کیفیت برچسب گذاری مورد نیاز است. معیارهای کیفیت برچسب‌گذاری توسط نقشه‌برداران، به ویژه توسط ایمهوف و یولی [ 1 ، 19 ، 27 ] مورد مطالعه قرار گرفته است. چندین عامل اساسی بیشتر در هنگام برچسب گذاری مورد توجه قرار می گیرند:

  • تضاد یا همپوشانی بین برچسب ها و ویژگی های گرافیکی.
  • ترجیحات پیشینی در میان مجموعه ای از موقعیت های برچسب نامزد.
  • ارتباط بین برچسب و ویژگی مربوط به آن.
بر اساس این معیارهای کیفیت برچسب، توابع هدف مختلفی برای بهینه‌سازی ترکیبی برچسب‌گذاری استفاده می‌شود. انتخاب تابع هدف بر زیبایی شناسی طرح و کارایی جستجو تأثیر می گذارد. در این مقاله تابع هدف به صورت زیر تعریف می شود:

∑من=1ن(w1⋅پoسپrهfهrهnجه(من)+w2⋅پoسسیonfلمنجتی(من))

که در آن N به تعداد کل ویژگی نقطه اشاره دارد، و i نشان دهنده برچسب ویژگی نقطه i است ، به صورت 1 ≤ i ≤ N . توابع PosPreference () و PosConflict () به ترتیب اولویت و فاکتورهای تضاد برچسب را با w 1 و w 2 به عنوان وزن تعیین می کنند. اگر w 1 = 0، ترجیح موقعیت برچسب در نظر گرفته نمی شود.

همانطور که در شکل 9 نشان داده شده است، در مورد ترجیح موقعیت برچسب PosPreference ()، یک پسوند از مدل موقعیت ثابت را می توان پیاده سازی کرد [ 36 ]، همانطور که در شکل 9 نشان داده شده است، که در آن موقعیت برچسب نامزد به هشت بخش با رتبه های ترجیحی متفاوت اختصاص داده شده است.
برای سهولت توضیحات برای نتیجه برچسب‌گذاری، فقط تعداد برچسب‌های بدون تداخل در بخش آزمایش‌های برچسب‌گذاری بعدی در نظر گرفته شده است. اولویت در نظر گرفته نمی شود، بنابراین w 1 = 0; بر این اساس، w 2 = 1 و PosConflict () به صورت زیر تعریف می شود. در نتیجه، تابع هدف برای حداکثر کردن تعداد برچسب بدون تضاد تنظیم می شود.

پoسسیonfلمنجتی(من)={1اگر برچسب است تعارض رایگان با دیگر برچسب ها و امکانات0دیگر.

2.2.3. انتخاب موقعیت های برچسب

با مجموعه‌ای از موقعیت‌های نامزد تولید شده برای هر برچسب و یک تابع هدف کلی، انتخاب موقعیت‌ها برای همه برچسب‌ها برای به حداکثر رساندن تابع هدف سراسری یک مسئله بهینه‌سازی ترکیبی است. اگرچه بسیاری از تقریب ها و اکتشافی های مختلف برای این مشکل ارائه شده است، روش مبتنی بر بازپخت شبیه سازی شده در این مقاله ترجیح داده شده است. به عنوان یک روش بهینه‌سازی با راندمان بالا و انعطاف‌پذیر، بازپخت شبیه‌سازی شده به طور گسترده برای حل مسائل بهینه‌سازی بزرگ، از جمله قرار دادن برچسب استفاده می‌شود [ 2 ، 8 ، 19 ، 36 ، 37 ]. فرآیندهای اصلی بازپخت شبیه سازی شده به شرح زیر است [ 3 ]:

  • برای هر ویژگی نقطه، برچسب آن را به طور تصادفی در هر یک از موقعیت های نامزد قرار دهید.
  • درجه حرارت T را به مقدار اولیه بالا T o مقداردهی کنید .
  • مراحل زیر را تکرار کنید تا دمای T به زیر مقدار آستانه معین Tc کاهش یابد :

    (آ)
    دمای T را طبق برنامه زمانبندی بازپخت کاهش دهید.
    (ب)
    به طور تصادفی یک برچسب را انتخاب کنید و آن را به یک موقعیت نامزد انتخابی جدید منتقل کنید.
    (ج)
    ΔE را محاسبه کنید ، تغییر تابع هدف ناشی از حرکت دادن برچسب.
    (د)
    اگر برچسب‌گذاری جدید بدتر است، تغییر موقعیت برچسب را با احتمال خنثی کنید پ=1.0–ه–ΔE/تی.
اجرای بازپخت شبیه سازی شده استاندارد به چهار جزء نیاز دارد: پیکربندی اولیه، تابع هدف، تغییرات پیکربندی، و برنامه بازپخت [ 3 ]. و پارامترهای مختلفی برای کنترل فرآیند بازپخت استفاده می شود، مانند دمای اولیه T o ، دمای آستانه Tc ، سرعت خنک شدن دمای A ، زمان تغییر مکان M برای هر مرحله آنیلینگ، و حداکثر بار پذیرفته شده K برای کاهش فوری دما. در فرآیند برچسب‌گذاری ما، این پارامترها مشابه مقادیر مورد استفاده در تحقیقات قبلی [ 3 ، 8 ] تنظیم می‌شوند. مقادیر پارامتر در نشان داده شده استجدول 2 (که در آن N تعداد ویژگی های نقطه است).
با سه مرحله اساساً مستقل ذکر شده در بخش 2.2 شرح داده شده در بالا ، کل رویه برچسب‌گذاری نقطه-ویژگی مبتنی بر قابلیت جابجایی مانند الگوریتم 1 است.
الگوریتم 1 منطقه برچسب‌گذاری نقطه-ویژگی مبتنی بر قابلیت جابجایی 
ورودی:
     U: ویژگی های نقطه ای که باید برچسب گذاری شوند (با عرض و ارتفاع برچسب مربوطه)
     O: موانع نقطه
     L: موانع خط
     P: موانع چند ضلعی
شروع: 
(1)   تکرار 
(2) یک نقطه u را از U انتخاب کنید و چند ضلعی جعبه متنی آن را با توجه به عرض و ارتفاع بدست آورید.
(3) فضای جستجوی اصلی g را برای نقطه u با توجه به t و مقدار آستانه فاصله مشخصه برچسب محاسبه 
کنید (4) موانع را از O، L و P که ناحیه برچسب‌گذاری g را مسدود می‌کنند، دریافت کنید 
(5) بر اساس این موانع، ناحیه متحرک بودن s برای نقطه u را با جمع Minkowski محاسبه کنید
(6) مجموعه نقطه مرجع V جعبه متن را دریافت کنید t 
(7)       تکرار کنید 
(8) یک نقطه مرجع v را از V انتخاب کنید
(9) موقعیت برچسب نامزد c را در ناحیه s پیدا کنید ، که فاصله بین نقطه مرجع v و نقطه u را کوتاه‌ترین می‌کند.
(10) c را به مجموعه موقعیت برچسب نامزد C u برای نقطه u 
(11)      اضافه کنید تا زمانی که موقعیت برچسب نامزد برای هر نقطه مرجع از V ایجاد شود.
(12) C u را به مجموعه موقعیت برچسب نامزد C اضافه کنید
(13) تا زمانی که مجموعه موقعیت برچسب نامزد برای هر نقطه در U ایجاد شود
(14) مقداردهی اولیه به طور تصادفی موقعیت برچسب را از C برای هر نقطه انتخاب کنید تا راه حل برچسب گذاری مقداردهی شود z 
(15) تکرار 
(16) حل z را با فرآیند بازپخت شبیه سازی شده بهبود دهید.
(17) تا زمانی که دمای بازپخت شبیه سازی شده به زیر مقدار آستانه معین کاهش یابد
(18) لایه نتیجه برچسب گذاری R را مطابق راه حل z ایجاد کنید 
خروجی: 
     R: لایه نتیجه برچسب زدن

3. آزمایشات

منطقه توصیف شده مدل برچسب‌گذاری مبتنی بر قابلیت جابجایی در سی شارپ پیاده‌سازی شده است و بر روی رایانه شخصی با پردازنده مرکزی Intel Core i5 3.2 گیگاهرتز و 4 گیگابایت رم اجرا می‌شود. برای بررسی اثربخشی مدل برچسب‌گذاری پیشنهادی، آزمایش‌های مقایسه‌ای با مدل موقعیت ثابت و مدل لغزنده انجام می‌شود. برای مدل لغزنده، مدل چهار لغزنده [ 22 ] در آزمایش ها اعمال می شود. در مورد مدل موقعیت ثابت، از مدل چهار موقعیت استفاده می شود زیرا این مدل محبوب ترین مدل برچسب گذاری در تحقیقات قبلی است. مدل چهار موقعیت نیز با بازپخت شبیه سازی شده با همان مقادیر پارامتری که در بخش 2.2.3 برای مقایسه توضیح داده شده است، ترکیب شده است.
آزمایش‌های برچسب‌گذاری برای چندین مجموعه داده معمولی انجام می‌شود. مجموعه داده‌های برچسب‌گذاری به سه گروه تقسیم می‌شوند: (i) برچسب‌گذاری تنها با ویژگی‌های نقطه‌ای. (ii) برچسب‌گذاری با ویژگی‌های نقطه، خط و ناحیه. و (iii) قرار دادن برچسب‌هایی با شکل دلخواه. اطلاعات دقیق در مورد این موارد در جدول 3 نشان داده شده است . نتایج مربوط به برچسب زدن در بخش زیر ارائه شده است. برای مقایسه بهتر نتایج برچسب‌گذاری، حذف برچسب‌های متضاد در آزمایش‌های برچسب‌گذاری گنجانده نشده است.

3.1. برچسب زدن با ویژگی های فقط نقطه

برای اکثر مطالعات قبلی، آزمایش‌های برچسب‌گذاری که فقط به ویژگی‌های نقطه‌ای مربوط می‌شوند، انجام شده‌اند. مجموعه داده‌ها برای برچسب‌گذاری آزمایش‌ها تنها با ویژگی‌های نقطه‌ای از تحقیقات نماینده قبلی [ 2 ، 38 ]، یعنی نمونه‌های RandomRect، RandomMap و VariableDensity هستند. و آنها در وب سایت برچسب زدن [ 39 ] در دسترس هستند. اولین نمونه در RandomRect، RandomMap و VariableDensity به ترتیب با 500، 500 و 1000 امتیاز برای مقایسه برچسب‌گذاری انتخاب می‌شوند. نتایج برچسب گذاری در شکل 10 ، شکل 11 و شکل 12 ارائه شده است ، و برچسب های متضاد رنگ روشن تری دارند و با مستطیل های نقطه چین مشخص شده اند.
RandomRect توسط n نقطه به طور یکنواخت در مربعی به اندازه n × 25 n توزیع شده است که طول هر دو لبه به طور مستقل تحت توزیع نرمال ایجاد شده است [ 2 ]. نتایج برچسب گذاری برای نمونه RandomRect انتخاب شده در شکل 10 نشان داده شده است . برای این سه مدل برچسب‌گذاری، مدل چهار موقعیت و مدل چهار لغزنده 339 و 380 برچسب بدون تداخل تولید می‌کنند. مدل برچسب‌گذاری ما با 450 برچسب بدون تداخل، با بهبود 111 و 70 برچسب بدون درگیری در مقایسه با مدل‌های قبلی، به نتیجه می‌رسد.
RandomMap به روشی مشابه RandomRect تولید می شود، اما با اندازه های برچسب واقعی تر برای تقلید از یک نقشه واقعی [ 2 ]. نتایج برچسب گذاری مربوطه برای نمونه انتخاب شده در شکل 11 نشان داده شده است . همانطور که از این شکل مشخص است، 224 برچسب بدون تداخل توسط مدل چهار حالته و 205 برچسب بدون تداخل توسط مدل چهار لغزنده تولید شده است. برای مدل ما، نتیجه به 358 برچسب بدون تداخل، با 134 و 153 برچسب بیشتر در مقایسه با مدل چهار موقعیت و مدل چهار لغزنده، به دست می‌آید.
VariableDensity توسط نقاطی تشکیل می شود که به طور یکنواخت روی مستطیلی به اندازه 792 × 612 با اندازه برچسب برابر 30 × 7 توزیع شده اند [ 2 ]. نتایج برچسب گذاری برای این نمونه در شکل 12 نشان داده شده است . مدل چهار حالته، مدل چهار لغزنده و مدل ما به ترتیب دارای برچسب های 833، 925 و 960 بدون درگیری هستند.
نتایج برچسب‌گذاری و زمان اجرا برای این سه نمونه در جدول 4 آورده شده است. تنها با در نظر گرفتن موانع نقطه‌ای، منطقه مدل برچسب‌گذاری مبتنی بر قابلیت جابجایی، نتیجه برچسب‌گذاری بهتری را تضمین می‌کند و در مقایسه با مدل‌های قبلی به بهبود کارآمدی دست می‌یابد. مدل چهار لغزنده نتایج بهتری را برای RandomRect و VariableDensity نسبت به مدل چهار موقعیت دریافت می کند، زیرا از لغزش انعطاف پذیر برای برچسب بهره می برد. با این حال، نتیجه برای نقشه تصادفی با مدل چهار لغزنده کمی بدتر از مدل چهار موقعیت است. دلیل آن این است که RandomMap دارای تراکم بسیار بالایی از نقاط و برچسب ها است و فضای زیادی برای لغزش باقی نمی گذارد. بنابراین، اگر مدل لغزنده سود کمی از برچسب‌های لغزنده دریافت کند، مدل موقعیت ثابت ممکن است با استراتژی بهینه‌سازی ترکیبی نتیجه بهتری بگیرد.
از آنجایی که محاسبات هندسی درگیر است، مدل ما بیشتر از مدل چهار موقعیت و مدل چهار لغزنده اجرا می شود. با این وجود، از دست دادن کارایی قابل قبول است زیرا نگرانی اصلی مدل پیشنهادی کیفیت برچسب‌گذاری برای تولید نقشه است.

3.2. برچسب‌گذاری با ویژگی‌های نقطه، خط و ناحیه

آزمایش‌های برچسب‌گذاری فوق فرض می‌کنند که مجموعه نقطه‌ای که باید برچسب‌گذاری شود، عاری از زمینه است، بنابراین هیچ ویژگی دیگری به جز نقاط و برچسب‌ها لازم نیست نشان داده شود. با این حال، در برچسب گذاری نقشه عملی، خطوط و مناطق مهم ضروری هستند و همچنین باید عاری از تضاد باشند. بنابراین، برچسب گذاری یک مورد با ویژگی های نقطه، خط و مساحت کاربردی مورد بررسی قرار می گیرد. مجموعه داده RoadResident برای این آزمایش استفاده می شود. این از خطوط جاده عملی، مناطق مسکونی و نقاط تولید تصادفی تشکیل شده است. نتایج برچسب گذاری برای این نمونه در شکل 13 ارائه شده است . برچسب های متضاد رنگ روشن تری دارند و با مستطیل های نقطه چین مشخص می شوند و برچسب های بدون تداخل به زبان چینی هستند و با مستطیل ها با خطوط ثابت مشخص می شوند.
با فرض عدم تضاد با نقاط، خطوط یا مناطق، مدل چهار موقعیت و مدل چهار لغزنده 209 و 290 برچسب بدون درگیری دریافت می کنند. و مدل پیشنهادی به 351 برچسب بدون درگیری دست می یابد که دارای 142 و 61 برچسب بیشتر از مدل های قبلی است. مقایسه های دقیق مربوطه در مناطق مستطیلی در شکل 14 نشان داده شده است . همانطور که از این شکل مشاهده می شود، فضای خالی نقشه بر اساس ناحیه قابلیت جابجایی به اندازه کافی مورد استفاده قرار می گیرد، در حالی که برای بسیاری از نقاطی که باید برچسب گذاری شوند، نامزدهای مدل موقعیت ثابت یا مسیرهای لغزشی از مدل کشویی در تضاد هستند. زمینه نقشه
علاوه بر این، برخی از موارد برچسب‌گذاری نماینده مدل پیشنهادی در شکل 15 نشان داده شده‌اند که مدیریت آن‌ها توسط مدل موقعیت ثابت و مدل لغزنده دشوار است، زیرا برچسب‌های به‌دست‌آمده در موقعیت‌های ثابت خاصی نیستند یا محدود به یک خط مسیر کشویی نیستند. . بنابراین، بر اساس منطقه قابل جابجایی، هنگامی که یک فضای خالی در ناحیه اطراف ویژگی نقطه وجود دارد، می توان یک برچسب بدون درگیری قرار داد.
حتی با وجود منطقه مدل مبتنی بر قابلیت جابجایی، هنوز 207 برچسب به دلیل موانع شلوغ در تضاد هستند. برای اکثر این برچسب‌ها، هیچ فضایی در منطقه اطراف برای برچسب‌گذاری وجود ندارد، بنابراین نمی‌توان موقعیت برچسب بدون درگیری را به دست آورد. برخی از موارد برچسب زدن متناقض با مدل پیشنهادی در شکل 16 نشان داده شده است .

3.3. قرار دادن برچسب های خودسرانه

تا کنون فقط برچسب گذاری مستطیلی شکل مورد بحث قرار گرفته است. مدل پیشنهادی را می توان برای قرار دادن برچسب هایی با شکل دلخواه گسترش داد. نمونه WeatherMap در این آزمایش برچسب‌گذاری استفاده می‌شود که شرایط آب و هوایی مراکز استان‌ها را در چین نشان می‌دهد. همانطور که از نتیجه برچسب‌گذاری در شکل 17 مشاهده می‌شود، بیشتر نمادهای آب‌وهوا با شکل دلخواه با فرض عدم تضاد با ویژگی‌های زمینه نقشه، با موفقیت به نقاط اختصاص داده می‌شوند. برخی از برچسب های موجود در این شکل را نمی توان به راحتی با مدل موقعیت ثابت یا مدل لغزنده کنترل کرد.

4. نتیجه گیری

مدل برچسب گذاری بر اساس منطقه قابلیت جابجایی یک استراتژی جدید برای قرار دادن برچسب ارائه می دهد. مدل به اندازه کافی از منطقه خالی نقشه استفاده می کند و فضای جستجو را گسترش می دهد، که برچسب های نامزد در برخی از موقعیت های ثابت هستند یا در امتداد یک مسیر مشخص می لغزند. با این بهبود، آزمایش‌های برچسب‌گذاری عملکرد خوب منطقه مدل مبتنی بر قابلیت حرکت را نشان می‌دهند. به خصوص هنگامی که بدون درگیری با ویژگی‌های بافت پیچیده در نظر گرفته می‌شود، مدل پیشنهادی با موفقیت قرار دادن برچسب‌هایی را تکمیل می‌کند که رسیدگی به آنها در مدل‌های موقعیت ثابت و لغزنده دشوار است. علاوه بر این، برچسب‌های خودسرانه را می‌توان تحت این استراتژی مدیریت کرد.
در این مقاله فقط برچسب گذاری نقطه-ویژگی در نظر گرفته شده است. بنابراین، گسترش به خط و برچسب گذاری ویژگی منطقه ممکن است در تحقیقات بیشتر انجام شود. حتی با مدل پیشنهادی، اگر برچسب‌های نزدیک یا ویژگی‌های موانع بیش از حد شلوغ باشند، گاهی اوقات قرار دادن برچسب‌های بدون درگیری غیرممکن است. از این رو، یک استراتژی حذف برای این برچسب‌ها بدون فضای برچسب‌گذاری کافی باید بررسی شود. نتایج چندین جهت برای کار آینده ارائه می دهد.

منابع

  1. Imhof، E. تعیین موقعیت نام ها بر روی نقشه ها. صبح. کارتوگر. 1975 ، 2 ، 128-144. [ Google Scholar ] [ CrossRef ]
  2. واگنر، اف. Wolff، A. چارچوب ترکیبی برای برچسب گذاری نقشه. در ترسیم نمودار ; Whitesides, SH, Ed. Springer: برلین، آلمان، 1998; صص 316-331. [ Google Scholar ]
  3. کریستنسن، جی. مارکس، جی. Shieber, S. یک مطالعه تجربی از الگوریتم‌ها برای قرار دادن برچسب نقطه ویژگی. ACM Trans. نمودار. 1995 ، 14 ، 203-232. [ Google Scholar ] [ CrossRef ]
  4. ایتوریاگا، سی. Lubiw, A. NP-Hardness of some map Labeling Problems ; دانشگاه واترلو: واترلو، ON، کانادا، 1997. [ Google Scholar ]
  5. مارکس، جی. شیبر، SM پیچیدگی محاسباتی قرار دادن برچسب کارتوگرافی ; دانشگاه هاروارد: کمبریج، MA، ایالات متحده آمریکا، 1991. [ Google Scholar ]
  6. ریبیرو، جنرال موتورز; موری، GR; Lorena، LAN تجزیه لاگرانژی برای حداکثر مسئله مجموعه مستقل اعمال شده برای برچسب زدن نقشه. اپراتور Res. 2011 ، 11 ، 229-243. [ Google Scholar ] [ CrossRef ]
  7. Gomes، SP; ریبیرو، جنرال موتورز; لورنا، پراکندگی LAN برای مشکل قرار دادن برچسب کارتوگرافی نقطه-ویژگی. سیستم خبره Appl. 2013 ، 40 ، 5878-5883. [ Google Scholar ] [ CrossRef ]
  8. Rabello, RL; موری، GR; ریبیرو، جنرال موتورز; Lorena، LAN یک فراابتکاری جستجوی خوشه‌بندی برای مسئله مکان‌یابی برچسب نقشه‌برداری نقطه‌ای. یورو جی. اوپر. Res. 2014 ، 234 ، 802-808. [ Google Scholar ] [ CrossRef ]
  9. شوارتگز، ن. Haunert، JH; ولف، ا. Zwiebler, D. برچسب‌گذاری نقطه‌ای با برچسب‌های کشویی در نقشه‌های تعاملی. در اتصال اروپای دیجیتال از طریق مکان و مکان ؛ انتشارات بین المللی Springer: چم، سوئیس، 2014; صص 295-310. [ Google Scholar ]
  10. Do Nascimento، HAD; Eades، P. نکات کاربر برای برچسب زدن نقشه. J. Vis. لنگ محاسبه کنید. 2008 ، 19 ، 39-74. [ Google Scholar ] [ CrossRef ]
  11. ون کرولد، ام. استریجک، تی. Wolff, A. برچسب گذاری نقطه ای با برچسب های کشویی. محاسبه کنید. Geom. تئوری کاربردی 1999 ، 13 ، 21-47. [ Google Scholar ] [ CrossRef ]
  12. کلاو، GW; Mutzel, P. برچسب‌گذاری بهینه ویژگی‌های نقطه‌ای در مدل‌های برچسب‌گذاری مستطیلی. ریاضی. برنامه. 2003 ، 94 ، 435-458. [ Google Scholar ] [ CrossRef ]
  13. Raidl, GR یک الگوریتم ژنتیک برای برچسب زدن ویژگی های نقطه. در مجموعه مقالات کنفرانس بین المللی علوم، سیستم ها و فناوری تصویربرداری، لاس وگاس، NV، ایالات متحده آمریکا، ژوئیه 1998; ص 189-196.
  14. یاماموتو، ام. کامارا، جی. Lorena، LAN Tabu جستجوی اکتشافی برای قرار دادن برچسب نقشه‌کشی با ویژگی نقطه‌ای. Geoinformatica 2002 ، 6 ، 77-90. [ Google Scholar ] [ CrossRef ]
  15. کراوو، جی ال. ریبیرو، جنرال موتورز; Nogueira Lorena، LA یک روش جستجوی تصادفی تطبیقی ​​حریصانه برای قرار دادن برچسب کارتوگرافی با ویژگی نقطه‌ای. محاسبه کنید. Geosci. 2008 ، 34 ، 373-386. [ Google Scholar ] [ CrossRef ]
  16. ریبیرو، جنرال موتورز; لورنا، آرامش لاگرانژی LAN با خوشه‌ها برای مشکلات قرار دادن برچسب کارتوگرافی نقطه‌ای. محاسبه کنید. اپراتور Res. 2008 ، 35 ، 2129-2140. [ Google Scholar ] [ CrossRef ]
  17. موری، GR; ریبیرو، جنرال موتورز; Lorena، LAN یک مدل ریاضی جدید و یک تجزیه لاگرانژی برای مسئله مکان‌یابی برچسب کارتوگرافی نقطه‌ای. محاسبه کنید. اپراتور Res. 2010 ، 37 ، 2164-2172. [ Google Scholar ] [ CrossRef ]
  18. الویم، ACF; Taillard، ED Popmusic برای مشکل قرار دادن برچسب ویژگی نقطه. یورو جی. اوپر. Res. 2009 ، 192 ، 396-413. [ Google Scholar ] [ CrossRef ]
  19. واگنر، اف. ولف، ا. کاپور، وی. Strijk, T. سه قانون برای قرار دادن برچسب خوب کافی است. الگوریتمیکا 2001 ، 30 ، 334-349. [ Google Scholar ] [ CrossRef ]
  20. لوبوشیک، م. شومان، اچ. Cords, H. برچسب‌گذاری مبتنی بر ذرات: برچسب‌گذاری سریع نقطه‌ای بدون پنهان کردن سایر ویژگی‌های بصری. IEEE Trans. Vis. محاسبه کنید. نمودار. 2008 ، 14 ، 1237-1244. [ Google Scholar ] [ CrossRef ] [ PubMed ]
  21. کامدا، تی. Imai، K. قرار دادن برچسب نقشه برای نقاط و منحنی ها. IEICE Trans. فاندم الکترون. اشتراک. محاسبه کنید. علمی 2003 ، E86A ، 835-840. [ Google Scholar ]
  22. ابنر، دی. کلاو، GW; Weiskircher، R. به حداکثر رساندن عدد برچسب در مدل لغزنده (چکیده گسترده). در ترسیم نمودار ; Springer: New York, NY, USA, 2004; صص 144-154. [ Google Scholar ]
  23. Hirsch, SA الگوریتمی برای قرار دادن خودکار نام در اطراف داده های نقطه ای. صبح. کارتوگر. 1982 ، 9 ، 5-17. [ Google Scholar ] [ CrossRef ]
  24. دادی، س. Marathe، MV; میرزائیان، ع. مورت، بی.ام. ژو، بی. برچسب گذاری نقشه و تعمیم های آن. در مجموعه مقالات هشتمین سمپوزیوم سالانه ACM-SIAM در مورد الگوریتم های گسسته (SODA’97)، نیواورلئان، لس آنجلس، ایالات متحده آمریکا، 13 تا 23 دسامبر 1997. صص 148-157.
  25. استریجک، تی. ون کرولد، ام. توسعه های عملی برچسب گذاری نقطه در مدل لغزنده. Geoinformatica 2002 ، 6 ، 181-197. [ Google Scholar ] [ CrossRef ]
  26. پون، SH; شین، CS; استریجک، تی. یونو، تی. Wolff, A. برچسب زدن به نقاط با وزنه. الگوریتمیکا 2004 ، 38 ، 341-362. [ Google Scholar ] [ CrossRef ]
  27. Yoeli, P. منطق حروف خودکار نقشه. کارتوگر. J. 1972 , 9 , 99-108. [ Google Scholar ] [ CrossRef ]
  28. رایلوف، MA; Reimer، AW بهبود کیفیت قرار دادن برچسب با در نظر گرفتن جزئیات نقشه پایه با رویکردی مبتنی بر شطرنجی. GeoInformatica 2014 ، 19 ، 463-486. [ Google Scholar ] [ CrossRef ]
  29. ساک، J.-R. Toussaint، GT ترجمه چند ضلعی در هواپیما. در Stacs 85: دومین سمپوزیوم سالانه جنبه‌های نظری علوم کامپیوتر زاربروکن، 3 تا 5 ژانویه 1985 . مهلهورن، ک.، ویرایش. Springer: برلین، آلمان، 1985; صص 310-321. [ Google Scholar ]
  30. لین، ام. Gottschalk، S. تشخیص برخورد بین مدل های هندسی: یک بررسی. در مجموعه مقالات کنفرانس IMA در ریاضیات سطوح، بیرمنگام، بریتانیا، 31 اوت تا 2 سپتامبر 1998. ص 602-608.
  31. کوکارا، س. هالیک، تی. اقبال، ک. بایراک، سی. Rowe, R. تشخیص برخورد: یک بررسی. در مجموعه مقالات کنفرانس بین المللی IEEE در مورد سیستم ها، انسان و سایبرنتیک، مونترال، QC، کانادا، 7 تا 10 اکتبر 2007. صفحات 4046-4051.
  32. ساک، J.-R. Toussaint، GT جداسازی جفت چند ضلعی از طریق ترجمه های منفرد. Robotica 1987 ، 5 ، 55-63. [ Google Scholar ] [ CrossRef ]
  33. Ghosh، PK راه حلی برای مهار چند ضلعی، برنامه ریزی فضایی، و سایر مشکلات مرتبط با استفاده از عملیات minkowski. محاسبه کنید. Vis. نمودار. فرآیند تصویر 1990 ، 49 ، 1-35. [ Google Scholar ] [ CrossRef ]
  34. Ghosh, PK جبری از چندضلعی ها از طریق مفهوم اشکال منفی. CVGIP Image Underst. 1991 ، 54 ، 119-144. [ Google Scholar ] [ CrossRef ]
  35. ادمونسون، اس. کریستنسن، جی. مارکس، جی. Shieber, SM یک الگوریتم برچسب گذاری نقشه برداری عمومی. کارتوگر. بین المللی جی. جئوگر. Inf. جئوویس. 1996 ، 33 ، 13-24. [ Google Scholar ]
  36. ژانگ، Q. Harrie, L. قرار دادن برچسب متن و نماد به طور همزمان: روشی بلادرنگ. کارتوگر. Geogr. Inf. علمی 2006 ، 33 ، 53-64. [ Google Scholar ] [ CrossRef ]
  37. Zoraster, S. نتایج عملی با استفاده از بازپخت شبیه سازی شده برای قرار دادن برچسب ویژگی نقطه ای. کارتوگر. Geogr. Inf. سیستم 1997 ، 24 ، 228-238. [ Google Scholar ] [ CrossRef ]
  38. کاپور، وی. کول، دی. Wolff, A. آموزشی برای طراحی الگوریتم های هندسی انعطاف پذیر. الگوریتمیکا 2002 ، 33 ، 52-70. [ Google Scholar ] [ CrossRef ]
  39. Wolff، A. برچسب گذاری نقشه عمومی. در دسترس آنلاین: http://i11www.iti.uni-karlsruhe.de/~awolff/map-labeling/general/ (در 27 اوت 2016 قابل دسترسی است).
Ijgi 05 00159 g001 1024
شکل 1. ( الف ) مدل چهار موقعیت. ( ب ) 5-8 موقعیت از مدل هشت موقعیت. ( ج ) مدل چهار لغزنده.
Ijgi 05 00159 g002 1024
شکل 2. ناحیه قابل حرکت برای چند ضلعی P با نقطه Q به عنوان ویژگی پس زمینه.
Ijgi 05 00159 g003 1024
شکل 3. ناحیه قابلیت جابجایی برای چند ضلعی P با خط Q به عنوان ویژگی پس زمینه.
Ijgi 05 00159 g004 1024
شکل 4. نمودار شماتیک جمع چندضلعی ها مینکوفسکی.
Ijgi 05 00159 g005 1024
شکل 5. نمودار شماتیک فضاهای جستجو از سه مدل برچسب گذاری. ( الف ) مدل موقعیت ثابت با هشت نامزد. ( ب ) مدل چهار لغزنده. ( ج ) مدل پیشنهادی.
Ijgi 05 00159 g006 1024
شکل 6. نمودار جریان تولید منطقه برچسب نامزد. ( الف ) ویژگی نقطه، جعبه متن برچسب، و فضای جستجو. ( ب ) جعبه قرار دادن برچسب. ( ج ) منطقه ایجاد شده از غیر متحرک. ( د ) فضای برچسب‌گذاری بدون درگیری.
Ijgi 05 00159 g007 1024
شکل 7. نمودار شماتیک انتخاب موقعیت های برچسب نامزد. ( الف ) نقاط مرجع برای محاسبه فاصله. ( ب ) موقعیت برچسب نامزد ایجاد شده برای نقطه مرجع M.
Ijgi 05 00159 g008 1024
شکل 8. نمودار شماتیک موقعیت های برچسب نامزد تولید شده. ( الف ) چهار نقطه مرجع؛ ( ب ) موقعیت های برچسب نامزد تولید شده بدون مانع. ( ج ) موقعیت‌های برچسب نامزد تولید شده با موانع خط و ناحیه.
Ijgi 05 00159 g009 1024
شکل 9. پسوند از رتبه اولویت برچسب در مدل موقعیت ثابت.
Ijgi 05 00159 g010 1024
شکل 10. نتیجه برچسب زدن برای نمونه RandomRect با 500 امتیاز. ( الف ) مدل چهار موقعیت: 339 برچسب بدون درگیری. ( ب ) مدل چهار لغزنده: 380 برچسب بدون درگیری. ( ج ) مدل پیشنهادی: 450 برچسب بدون درگیری.
Ijgi 05 00159 g011 1024
شکل 11. نتیجه برچسب گذاری برای نمونه RandomMap با 500 امتیاز. ( الف ) مدل چهار موقعیت: 224 برچسب بدون درگیری. ( ب ) مدل چهار لغزنده: 205 برچسب بدون درگیری. ( ج ) مدل پیشنهادی: 358 برچسب بدون درگیری.
Ijgi 05 00159 g012a 1024 Ijgi 05 00159 g012b 1024
شکل 12. نتیجه برچسب گذاری برای نمونه VariableDensity با 1000 امتیاز. ( الف ) مدل چهار موقعیت: 833 برچسب بدون درگیری. ( ب ) مدل چهار لغزنده: 925 برچسب بدون درگیری. ( ج ) مدل پیشنهادی: 960 برچسب بدون درگیری.
Ijgi 05 00159 g013 1024
شکل 13. نتیجه برچسب گذاری برای نمونه RoadResident با 558 امتیاز. و کلمات چینی اسامی جغرافیایی هستند که باید بدون تضاد برچسب گذاری شوند. ( الف ) مدل چهار موقعیت: 209 برچسب بدون درگیری. ( ب ) مدل چهار لغزنده: 290 برچسب بدون درگیری. ( ج ) مدل پیشنهادی: 351 برچسب بدون درگیری.
Ijgi 05 00159 g014 1024
شکل 14. مقایسه دقیق در مناطق مستطیلی برای نمونه RoadResident. کلمات چینی اسامی جغرافیایی هستند که بدون تضاد برچسب گذاری می شوند. ( الف ) مدل چهار موقعیتی؛ ( ب ) مدل چهار لغزنده؛ ( ج ) مدل پیشنهادی.
Ijgi 05 00159 g015 1024
شکل 15. موارد برچسب گذاری نماینده برای نمونه RoadResident. و کلمات چینی اسامی جغرافیایی هستند که باید بدون تضاد برچسب گذاری شوند.
Ijgi 05 00159 g016 1024
شکل 16. موارد برچسب زدن متناقض برای نمونه RoadResident.
Ijgi 05 00159 g017 1024
شکل 17. برچسب گذاری نمادهای وضعیت آب و هوا برای مراکز استان ها در چین. و برخی از موارد برچسب زدن نماینده ارائه شده است.
جدول
جدول 1. مناطق “تحرک” برای نقطه اصلی، خط، و ویژگی های منطقه.
جدول
جدول 2. مقادیر پارامتر برای آزمایش های برچسب گذاری.
جدول
جدول 3. اطلاعات نمونه هایی برای آزمایش های برچسب گذاری.
جدول
جدول 4. نتایج برچسب گذاری و زمان اجرا برای سه مدل.

;کاربردهای GISمقالات

آموزش کاربردی ArcGISالهام ابراهیم زادهکاربرد جی ای اسکاربرد جی ای اس در زمین شناسی

بدون نظر

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

همواره حمایت دانشجویان عزیزمان همراه ما بوده و این سببب شده که گامی محکم به‌سوی ایجاد یک مرجع برای آموزش GIS برداریم. با این امید که بتوانیم قدردان حمایت شما بزرگواران باشیم.

  • خانه
  • آموزش
  • فیلم آموزشی
  • تماس با ما
  • درباره ما
  • وبلاگ
  • سمنان /خیابان کاشانی/ساختمان فناوری اطلاعات/پ 8
  • 09120049370