پیاده‌سازی و ارزیابی یک روش برچسب‌گذاری ویژگی سریع منطقه با استفاده از خطوط کمکی †

خلاصه

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

کلید واژه ها:

قرار دادن برچسب ؛ پردازش بلادرنگ ؛ برچسب زدن ویژگی منطقه ; خط کمکی

۱٫ معرفی

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

دستگاه های تبلت در سال های اخیر به سرعت گسترش یافته اند. دستگاه‌های تبلت می‌توانند به راحتی روی نقشه بزرگ‌نمایی و بزرگنمایی کنند، که نیاز به تعیین سریع موقعیت‌های برچسب دارد. در کاربردهای صنعتی، یک روش برچسب‌گذاری ویژگی منطقه باید شرایط زیر را برآورده کند [ ۱ ].

قابلیت پردازش بلادرنگ در دستگاه‌های تبلت، یعنی تمام موقعیت‌های برچسب ویژگی‌های ناحیه در قاب نمایشگر باید در عرض ۱۰۰ میلی‌ثانیه تعریف شوند.
قرار دادن برچسب موثر (در هر دو قسمت نمایش داده شده کامل و جزئی)، ترجیحاً در نزدیکی مرکز یک چندضلعی محدب بزرگ در منطقه.

توجه داشته باشید که از همپوشانی برچسب ها نیز باید اجتناب شود، اگرچه همپوشانی ها را می توان با بزرگنمایی نقشه روی دستگاه تبلت از بین برد.

ویژگی های نقشه معمولاً به سه نوع طبقه بندی می شوند: ویژگی های نقطه ای، ویژگی های خطی و ویژگی های منطقه. در میان روش های متعددی که برای برچسب گذاری ویژگی های نقطه ای پیشنهاد شده است [ ۲ ، ۳ ، ۴ ، ۵ ، ۶ ، ۷ ، ۸ ، ۹ ، ۱۰ ، ۱۱ ، ۱۲ ، ۱۳ ، ۱۴ ، ۱۵ ، ۱۶ ، ۱۷ ، ۱۸ ، ۲۰ ] ، دو مدل زیر معمولا استفاده می شود.

(آ): مدل موقعیت ثابت، که هر برچسب ویژگی نقطه را قرار می دهد، به طوری که یک نقطه ثابت در مرز آن، ویژگی نقطه مربوطه را لمس می کند.
(ب): مدل لغزنده، که امکان لغزش مداوم برچسب را در یک یا چند جهت تحت یک محدودیت می دهد: مرز برچسب باید ویژگی نقطه مربوطه را لمس کند.

پردازش بلادرنگ مدل (a) انجام شده است [ ۱۲ ، ۱۳ ، ۱۴ ]. Kameda و Imai [ ۱۵ ] روش هایی را برای برچسب گذاری ویژگی نقطه و خط ارائه کردند و Zhang و Harrie [ ۱۶ ] روش های مشابهی را برای پردازش بلادرنگ توسعه دادند. روش بلادرنگ ژانگ و هری [ ۱۷ ] برچسب هایی را برای ویژگی های نقطه و خط و نمادهایی برای ویژگی ناحیه قرار می دهد. نمادها با استفاده از خطوط رهبر در مکان هایی که به طور تصادفی انتخاب شده اند قرار می گیرند.

در مقابل، تا به امروز، برچسب‌گذاری ویژگی‌های ناحیه مورد توجه کمی قرار گرفته است (توضیحات مشابه را در [ ۱۸ ، ۲۱ ] که اخیراً منتشر شده است ببینید). روش های Aonuma و همکاران. [ ۲۲ ]، Barrault [ ۲۳ ]، Dorschlag و همکاران. [ ۲۴ ]، و لو و همکاران. [ ۱۸ ] از اسکلت یک منطقه استفاده کنید. روش لو و همکاران همچنین برچسب های ویژگی نقطه و خط را قرار می دهد. اسکلت توسط نمودارهای ورونوی (یا مثلث های دلونی) به دست می آید. این روش ها برای پردازش بلادرنگ مناطق با خطوط مرزی زیاد نامناسب هستند، زیرا نمودارهای ورونوی آنها باید از تمام نقاط انتهایی خطوط مرزی A ترسیم شوند.، که زمان اجرا را به میزان قابل توجهی افزایش می دهد. کاکولیس و تولیس [ ۱۹ ] و واگنر و همکاران. [ ۲۰ ] روش‌هایی را برای قرار دادن برچسب‌های ویژگی منطقه، نقطه و خط پیشنهاد کرد. هر دو روش ابتدا چندین موقعیت برچسب نامزد (که از این پس به عنوان نامزد برچسب نامیده می شود) برای هر ویژگی ایجاد می کنند. نامزدهای برچسب مناسب برای قرار دادن برچسب موثر در این روش‌ها ضروری هستند، اما فرآیندی که نامزدهای برچسب خوبی را برای مناطق معین ایجاد می‌کند، با جزئیات شرح داده نشده است. یک روش جایگزین توسط ادمونسون و همکاران. [ ۲۵] به صورت شبه تصادفی، نامزدهای برچسب ویژگی منطقه را برای قرار دادن ویژگی های ناحیه، نقطه و خط تولید می کند. این روش مستلزم ایجاد بسیاری از نامزدهای برچسب برای برچسب گذاری ویژگی های منطقه خوب است که زمان اجرا را افزایش می دهد. روش های ون روسل [ ۲۶ ] و پینتو و فریمن [ ۲۷ ] نیز شناخته شده اند، اما زمان بر هستند. رایلوف و همکاران [ ۲۱ ] روش کارآمدی را پیشنهاد کرد که برچسب‌ها را خارج از منطقه قرار می‌دهد که با هدف ما متفاوت است.

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

ادامه این مقاله به شرح زیر سازماندهی شده است. بخش ۲ روش های پیشنهادی را توضیح می دهد و بخش ۳ نتایج تجربی را ارائه می دهد. بخش ۴ روش پیشنهادی را در نمایش‌های جزئی منطقه هدف نشان می‌دهد. این بخش همچنین نواحی دارای روابط شمول را در نظر می گیرد، مانند شهرهای داخل استان. نتیجه گیری در بخش ۵ ارائه شده است.

۲٫ روش پیشنهادی

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

۲٫۱٫ یک روش ساده و سریع

در رویکرد ساده و سریع، برچسب ها در مرکز حداقل مستطیل مرزی هر A قرار می گیرند . این روش غالباً در مناطقی که یک چند ضلعی محدب را تشکیل می دهند، برچسب خوبی را به دست می آورد ( شکل ۱ a)، اما در مناطقی که یک چند ضلعی مقعر را تشکیل می دهند، اغلب برچسب را در یک بخش باریک ( شکل ۱ ب) یا حتی خارج از منطقه قرار می دهد ( شکل ۱) ۱ ج).

۲٫۲٫ روش قرار دادن برچسب پیشنهادی

روش پیشنهادی برچسب‌گذاری ویژگی منطقه، فواصل بین تقاطع برخی از خطوط کمکی و خطوط مرزی A را به کار می‌گیرد . توجه داشته باشید که خطوط کمکی می توانند افقی یا عمودی باشند.

با فرض اینکه منطقه A به طور کامل نمایش داده شده است، روش پیشنهادی ابتدا حداقل مستطیل محدود R از A را پیدا می کند ( شکل ۲ را ببینید ). این فرآیند را می توان با یک مرحله پیش پردازش که نقاط انتهایی چپ، راست، بالا و پایین خطوط مرزی A را ذخیره می کند، سرعت بخشید . در شکل ۲ ، خط کمکی h (خط نقطه چین) R را به صورت افقی نصف می کند و خطوط مرزی A را در چهار نقطه قطع می کند. نقاط تقاطع تعیین شده است جساعت۱، جساعت۲، جساعت۳، و جساعت۴٫ در اینجا، k تعداد تقاطع ها و i عددی فرد کمتر از k باشد . توجه داشته باشید که k همیشه زوج است و هر پاره خط جساعتمنجساعتمن+۱¯درون A وجود دارد . سپس i با طولانی ترین زمان را پیدا می کنیمجساعتمنجساعتمن+۱¯در میان i ها، و آن را به m اختصاص دهید . توجه داشته باشید که در شکل ۲ ، متر=۱٫

در شکل ۳ ، خط عمودی v”(خط دو نقطه چین چین) مشتق شده است جساعتمترجساعتمتر+۱¯و از وسط آن کشیده می شود. اجازه دهید جv1″، جv2″، ⋯ محل تقاطع باشد v”و خطوط مرزی عمودی A ، و j عددی فرد باشد. سپس پاره خط را پیدا می کنیم جvj”جvj+1″¯که تلاقی می کند جساعتمترجساعتمتر+۱¯، و یک نامزد برچسب (مستطیل چین دار) در نقطه وسط ایجاد کنید جvj”جvj+1″¯. نامزدهای برچسب اضافی را می توان از خطوط کمکی دیگر (از جمله خطوط عمودی) به همین روش استخراج کرد.

روش پیشنهادی موقعیت برچسب نهایی را از ده نامزد برچسب انتخاب می کند. سه کاندیدا از سه خط کمکی افقی که R چهار ضلعی دارند و سه خط از سه خط عمودی که R چهار ضلعی دارند مشتق شده اند . چهار نامزد برچسب باقی مانده با در نظر گرفتن شکل A ایجاد می شوند. دو مورد از این نامزدها از دو خط کمکی افقی که از طریق چپ و راست ترین نقاط انتهایی خطوط مرزی A ترسیم شده اند، و دو مورد از دو خط عمودی که از طریق بالا و پایین ترین نقاط انتهایی خطوط مرزی کشیده شده اند، مشتق شده اند. از A . شکل ۴نمونه ای از خط کمکی را نشان می دهد که از سمت چپ ترین نقطه پایانی کشیده شده است پل. انتظار می رود که حداکثر عرض فضای R در سمت راست وجود داشته باشد پل. بنابراین، این نامزدهای برچسب اضافی ساخته می شوند زیرا فضاهای وسیعی در طرف مقابل نقاط انتهایی انتظار می رود.

اجازه دهید ساعتorلجو vهrتیلجخطوط افقی و عمودی از طریق نقطه میانی نامزد برچسب باشد لج، به ترتیب. علاوه بر این، اجازه دهید Lلجمجموعه ای از تقاطع ها باشد ساعتorلجو خطوط مرزی A در سمت چپ نقطه میانی لج. به طور مشابه، اجازه دهید آرلج، آلج، و بلجمجموعه ای از تقاطع ها در سمت راست، بالا و پایین نقطه وسط باشد لج، به ترتیب. برای انتخاب موقعیت برچسب نهایی، روش پیشنهادی فواصل زیر را برای هر نامزد برچسب محاسبه می‌کند لج.

دمنستیل: فاصله بین نقطه میانی لجو سمت راست ترین تقاطع Lلج.
دمنستیr: فاصله بین نقطه میانی لجو سمت چپ ترین تقاطع آرلج.
دمنستیآ: فاصله بین نقطه میانی لجو پایین ترین تقاطع آلج.
دمنستیب: فاصله بین نقطه میانی لجو بالاترین تقاطع از بلج.

نسبت های دمنستیلو دمنستیrبه عرض برچسب و نسبت های دمنستیآو دمنستیببه ارتفاع برچسب نیز محاسبه می شوند. کوچکترین نسبت از این چهار نسبت، انعطاف پذیری نامزد برچسب را مشخص می کند. در روش پیشنهادی، نامزد برچسب با حداکثر انعطاف به عنوان موقعیت برچسب نهایی انتخاب می شود.

شکل ۵ نمونه ای از نامزدهای برچسب را نشان می دهد. روش پیشنهادی ده نامزد برچسب ایجاد می کند. با این حال، برای سادگی، ما فقط چهار نامزد برچسب را نشان می دهیم لج۱،لج۲،لج۳، و لج۴در شکل زیرا لج۲بسیار کوچک دارد دمنستیr، با تقسیم بسیار کوچک به انعطاف پذیری بسیار کمی دست می یابد دمنستیrبا عرض برچسب به همین ترتیب، لج۴با تقسیم بسیار کوچک به انعطاف پذیری بسیار کمی دست می یابد دمنستیببا ارتفاع برچسب بنابراین، نادر است که نامزدهای ایجاد مناطق نزدیک به مرز A به عنوان موقعیت های برچسب نهایی انتخاب شوند. زیرا دمنستیل،دمنستیr،دمنستیآ، و دمنستیباز لج۳همه بزرگتر از آنها هستند لج۱، روش پیشنهادی انتخاب می شود لج۳به عنوان موقعیت برچسب نهایی در مثال در این شکل. بنابراین، نامزدهای ایجاد شده در نزدیکی مرکز چندضلعی محدب بزرگ در A معمولا به عنوان موقعیت برچسب نهایی انتخاب می شوند. توجه داشته باشید که چون ارتفاع برچسب و عرض برچسب هنگام محاسبه انعطاف پذیری نامزدهای برچسب مقسوم علیه هستند، چند ضلعی های محدب بلند افقی (عمودی) برای موقعیت های برچسب بلند افقی (عمودی) انتخاب می شوند.

۲٫۳٫ مراحل پیش پردازش

این بخش فرعی دو مرحله پیش پردازش را توضیح می دهد که تشخیص تقاطع را سرعت می بخشد. اولین مرحله پیش پردازش، نقاط میانی خطوط مرزی A را محاسبه می کند . خطوط مرزی به ترتیب مختصات افقی و عمودی نقاط میانی خود ذخیره می شوند. برای یک مثال بسیار ساده، در شکل ۶ ، افقی (پ۱پ۴¯،پ۱پ۲¯،پ۳پ۴¯،پ۲پ۳¯)و عمودی (پ۳پ۴¯،پ۱پ۴¯،پ۲پ۳¯،پ۱پ۲¯)پیشرفت ها ایجاد می شود.

با اجرای یک جستجوی دودویی روی این دو پیشروی، اگر خطوط کمکی خطوط مرزی A را قطع کنند، تلاقی‌های منفرد به سرعت پیدا می‌شوند . مرحله دوم پیش پردازش از طریق خطوط مرزی A تکرار می شود. برای هر خط مرزی بلاز A ، این مرحله تمام خطوط مرزی A را که تا حدی در محدوده افقی و عمودی قرار دارند ذخیره می کند.بل. به عنوان مثال، در شکل ۷ ، خطوط مرزی پ۵پ۶¯، پ۶پ۷¯، پ۱۰پ۱۱¯، و پ۱۱پ۱۲¯تا حدودی در محدوده افقی خط مرزی قرار می گیرند پ۱پ۲¯، بنابراین اینها برای ذخیره می شوند پ۱پ۲¯در جهت افقی در بیشتر موارد، تعداد خطوط مرزی ذخیره شده به طور قابل توجهی کمتر از تعداد کل خطوط مرزی است. با جستجوی دودویی برای تقاطع ها و تنها در نظر گرفتن خطوط مرزی ذخیره شده A ، می توانیم تمام تقاطع ها را خیلی سریع تشخیص دهیم.

۲٫۴٫ توضیحات الگوریتم

الگوریتم روش پیشنهادی در زیر توضیح داده شده است.

(۱)

مراحل پیش پردازش زیر را اجرا کنید.

(۱-a): سمت چپ، راست، بالا و پایین ترین نقاط انتهایی خطوط مرزی A را ذخیره کنید.
(۱-b): خطوط مرزی A را به ترتیب مختصات افقی و عمودی نقاط میانی آنها ذخیره کنید.
(۱-c): برای هر خط مرزی بلاز A ، تمام خطوط مرزی A را که اشتراک جزئی با آن دارند ذخیره کنیدبلدر جهت افقی و عمودی

(۲)

برای هر خط کمکی مراحل زیر را انجام دهید.

(۲-a): یک تقاطع خط کمکی و خطوط مرزی A را با جستجوی دودویی بدست آورید.
(۲-b): تمام تقاطع ها را فقط با در نظر گرفتن خطوط مرزی ذخیره شده در مرحله (۱-c) تشخیص دهید.
(۲-c): یک نامزد برچسب ایجاد کنید.

(۳)

نامزد برچسب با حداکثر انعطاف را به عنوان موقعیت برچسب نهایی انتخاب کنید.

اکنون پیچیدگی های زمانی مراحل (۲) و (۳) را که در پردازش بلادرنگ دخیل هستند در نظر می گیریم. مرحله (۲-a) در زمان O(log n ) اجرا می شود، جایی که n تعداد کل بلس اجازه دهید ستیبلتعداد خطوط مرزی ذخیره شده برای هر کدام باشد بلو مترآایکسستیحداکثر تعداد آن باشد. مرحله (۲-b) در O( مترآایکسستی) زمان و مرحله (۲-c) در O( مترآایکسستیورود به سیستم مترآایکسستی) زمان چون تقاطع ها باید مرتب شوند. اگرچه اندازه مترآایکسستیO( n ) است، در بیشتر موارد، مترآایکسستیبه طور قابل توجهی کوچکتر از n است. در همین حال، اگر یک خط کمکی a را قطع کند بلکه برای آن خطوط مرزی زیادی ذخیره شده است، بخش نزدیک به خط کمکی معمولاً برای قرار دادن برچسب مناسب نیست. یک مثال معمولی در شکل ۸ نشان داده شده است . در این شکل، خط کمکی افقی h خطوط مرزی را قطع می کندپآپب¯و پجپد¯، که خطوط مرزی زیادی برای آن ذخیره شده است. بنابراین، مجاورت h پیچیده و برای قرار دادن برچسب نامناسب است. برای حذف این وضعیت، اگر مرحله (۲-a) یک تقاطع با خط مرزی بیش از تیساعتخطوط مرزی ذخیره شده، که در آن تیساعتیک آستانه است، یک نامزد برچسب برای آن خط کمکی ایجاد نشده است. تحت این درمان، که تأثیر نامطلوب کمی بر جایگذاری برچسب دارد، مترآایکسستیبه یک پارامتر مرتبه ثابت تبدیل می شود، بنابراین پیچیدگی زمانی کل مرحله (۲) O(log n ) است. تعداد نامزدهای برچسب یک پارامتر مرتبه ثابت است. بنابراین، پیچیدگی زمانی مرحله (۳) O (log n + ) استمترآایکسستی) اگر تقاطع ها به روشی مشابه مراحل (۲-a) و (۲-b) پیدا شوند، و اگر برخورد فوق الذکر مربوط به تیساعتاستفاده می شود.

۳٫ آزمایشات محاسباتی

اثربخشی روش پیشنهادی در آزمایش‌های محاسباتی تأیید شد. این بخش شرایط آزمایشی، روش ارزیابی و نتایج روش پیشنهادی را توضیح می‌دهد.

۳٫۱٫ شرایط آزمایشی

به عنوان ورودی، ما از پانزده ناحیه به‌دست‌آمده از داده‌های زمین مکانی بنیادی ارائه‌شده توسط سازمان اطلاعات مکانی ژاپن [ ۲۸ ] استفاده کردیم. هر ناحیه شامل تورفتگی یا بخش های باریک است، بنابراین برای قرار دادن برچسب با روش ساده توضیح داده شده در بخش ۲٫۱ نامناسب بودند . در اینجا، دو اندازه برچسب به شرح زیر تنظیم شد:

(آ): ارتفاع برچسب روی ۵ درصد ارتفاع ناحیه مربوطه تنظیم شد. عرض برچسب روی بار ارتفاع تنظیم شد لهتی/۲، جایی که لهتیتعداد حروف در برچسب است.
(ب): ارتفاع برچسب روی ۱۰ درصد ارتفاع ناحیه مربوطه تنظیم شد. عرض برچسب روی بار ارتفاع تنظیم شد لهتی/۳٫

آزمایش ها در زبان برنامه نویسی C بر روی پردازنده Core i7-7700 اینتل اجرا شد. برای بررسی رفتار در یک رایانه با کارایی پایین، مانند دستگاه تبلت، سرعت ساعت را روی ۱٫۰ گیگاهرتز تنظیم کردیم.

۳٫۲٫ ارزیابی

ما از روشی استفاده کردیم که چند ضلعی های محدب را در داخل یک ویژگی ناحیه A برمی شمارد ، که به زمان محاسباتی قابل توجهی نیاز دارد تا عملکرد روش پیشنهادی را ارزیابی کنیم.

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

سپس، با شروع از یک نقطه پایانی یک خط مرزی، سایر نقاط انتهایی به ترتیب در جهت عقربه های ساعت توسط بخش های خط به هم متصل می شوند. نقطه پایانی شروع را با علامت گذاری می کنیم پسو فرض کنید که تمام نقاط پایانی پ۱، پ۲، پ۳، ⋯، پس-۱، پس، پس+۱، ⋯، پn-2، پn-1، و پnبه ترتیب عقربه های ساعت هستند اگر سه یا چند نقطه پایانی نسبت به پس، روش بررسی می کند که آیا

(من): نقاط انتهایی متصل در داخل منطقه وجود دارد آ”و
(II): نقاط انتهایی متصل یک چند ضلعی محدب را تشکیل می دهند.

اگر هر یک از شرط ها نقض شود، روش آخرین نقطه پایانی ارزیابی شده را کنار گذاشته و نقطه پایانی بعدی را ارزیابی می کند. به عنوان مثال، فرض کنید که نقطه پایانی پ۱در شکل ۹ a نقطه پایانی شروع است پس. روش ابتدا نقطه پایانی را ارزیابی می کند پ۲، به دنبال پ۳٫ سپس چند ضلعی را بررسی می کند پ۱پ۲پ۳٫ همانطور که در شکل ۹ ب، چند ضلعی مشاهده می شودپ۱پ۲پ۳هر دو شرط (i) و (ii) بالا را برآورده می کند. بعد، روش ارزیابی می کند پ۴، اما به صورت چند ضلعی پ۱پ۲پ۳پ۴شرایط (ii) بالا را نقض می کند ( شکل ۹ ج)، پ۴دور انداخته می شود. پ۵نیز به دلیل چند ضلعی کنار گذاشته می شود پ۱پ۲پ۳پ۵هر دو شرایط (i) و (ii) بالا را نقض می کند ( شکل ۹ د).

اجازه دهید پداولین نقطه پایانی حذف شده باشد که شرط (i) را برآورده می کند، اما شرط (ii) را برآورده نمی کند. در شکل ۹ ، نقطه پد، که برای چند ضلعی محدب بعدی که باید شمارش شود ذخیره می شود، می باشد پ۴٫ پس از ارزیابی نقاط پایانی تا پس-۱(تا پnاگر س=۱، این روش اندازه چند ضلعی محدب بدست آمده را محاسبه می کند. این چند ضلعی اولین چند ضلعی است که شمارش شده است. برای چند ضلعی محدب بعدی، روش متصل می شود پسو پد-۱( پnاگر د=۱). اگر پسپد-۱¯در داخل وجود دارد آ”، سپس پد”=پد-۱٫ در غیر این صورت، روش فراتر از نقطه پایانی را بررسی می کند پد-۱تا زمانی که نقطه پایانی را پیدا کند پد”برای کدام پسپد”¯در داخل نهفته است آ”. پس از یافتن پد”، روش فراتر از نقطه پایانی را بررسی می کند پد”و در حین انجام بررسی های فوق، چند ضلعی های محدب ایجاد می کند. به عنوان مثال، در شکل ۹ ، پد”است پ۳، بنابراین روش چند ضلعی را بررسی می کند پ۱پ۳پ۴٫ در طول این سری از امتحانات، پدهمانطور که در بالا توضیح داده شد برای چند ضلعی محدب بعدی که قرار است شمارش شود ذخیره می شود. توجه داشته باشید که نامزدهای جدید پد_nهwبرای پدمحدود به د_nهw>دیا ۱<د_nهw<س-۱٫ شمارش نقطه پایانی شروع پسزمانی که جدید نباشد خاتمه می یابد پدذخیره می شود، یا زمانی که نقاط پایانی برای تشکیل چند ضلعی بین آنها بسیار کم است پد”و پس. این فرآیند تکرار می شود و هر کدام را به صورت متوالی تنظیم می کنیم پ۱، پ۲، پ۳، ⋯، پnبه عنوان نقطه پایانی شروع پس.

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

۳٫۳٫ نتایج تجربی

اجازه دهید دمنستیفاصله بین مرکز از جلو موقعیت مرکزی برچسب به دست آمده با روش پیشنهادی و دمنآgطول مورب حداقل مستطیل مرزی باشد آ”. نتایج تجربی برای اندازه های برچسب (A) و (B) تعریف شده در بخش ۳٫۱ به ترتیب در جدول ۱ و جدول ۲ نشان داده شده است.

چه زمانی جل/جمتربالا است، روش پیشنهادی یک برچسب را در داخل چند ضلعی محدب بزرگ قرار می دهد. در ضمن وقتی دمنستی/دمنآgکوچک است، روش پیشنهادی یک برچسب را در نزدیکی مرکز قرار می دهد جل. تأثیر اندازه برچسب در قرار دادن برچسب کم بود. توجه داشته باشید که زمان اجرا شامل مراحل پیش پردازش نمی شود. روش پیشنهادی به سرعت اجرا شد و بیش از ده هزار موقعیت برچسب را در ۱۰۰ میلی ثانیه تعیین کرد، محدودیت زمانی درخواست شده توسط کارمندان شرکت داون. توجه داشته باشید که در ۲۳ مورد از ۳۰ مورد، جل/جمتربه ۱۰۰ درصد رسید.

حداقل جل/جمتر۴۸٫۲ درصد و حداکثر بود دمنستی/دمنآg15.29 درصد بود. انتظار می رود استفاده از خطوط کمکی بیشتر باعث بهبود کیفیت موقعیت برچسب ها شود. روش پیشنهادی از شش خط کمکی که در فواصل مساوی و چهار خط کمکی ترسیم شده با در نظر گرفتن شکل A ، همانطور که در بخش ۲٫۲ توضیح داده شده است، استفاده می کند. موقعیت برچسب ۲۸ مورد از ۳۰ نمونه از خطوط کمکی با فاصله مساوی مشتق شده است. دو موقعیت برچسب باقی مانده از خطوط کمکی مبتنی بر شکل به دست آمدند. این نشان می دهد که در نظر گرفتن تنوع موقعیت ها مفید است.

شکل ۱۰ ، شکل ۱۱ و شکل ۱۲ قرارگیری برچسب را در حالی که از روش پیشنهادی برای اندازه برچسب (A) در Aisai-shi (واقع در استان Aichi، ژاپن)، Ajigasawa-cho (واقع در استان Aomori، ژاپن) و Neyagawa- نشان می دهد. شی (به ترتیب در استان اوزاکا، ژاپن واقع شده است). منطقه آیسای شی دارای ۲۲۵۵ خط مرزی است جل/جمترو دمنستی/دمنآgبه ترتیب ۱۰۰% و ۰٫۵۰% محاسبه شدند. همانطور که در شکل ۱۰ مشاهده می شود ، روش پیشنهادی موقعیت برچسب معقولی را برای Aisai-shi، یک ناحیه نامنظم با فرورفتگی های زیاد و بخش های باریک پیدا کرد. منطقه Ajigasawa-cho دارای ۶۵۶۸ خط مرزی است جل/جمترو دمنستی/دمنآgبه ترتیب ۱۰۰% و ۹٫۹۱% محاسبه شدند. قرار دادن برچسب بد نیست. با این حال، دمنستی/دمنآgتا حدی زیاد است و یک برجستگی جزئی برچسب مشاهده می شود، همانطور که در شکل ۱۱ مشاهده می شود . قرار دادن برچسب Neyagawa-shi (با ۳۵۸۶ خط مرزی) از جدول ۱ و جدول ۲ مستثنی شده است ، زیرا این ناحیه دارای تورفتگی های کمی است و برای قرار دادن برچسب ساده مناسب است. روش پیشنهادی همچنین موقعیت برچسب معقولی را در این ناحیه کمتر پیچیده پیدا کرد ( شکل ۱۲ ). شکل ۱۳ محل قرارگیری برچسب برای اندازه برچسب (B) را در Otsu-shi (واقع در استان شیگا، ژاپن) نشان می دهد. ارزش آن جل/جمتر۴۸٫۲٪ است که به طور قابل توجهی بد است. همانطور که در شکل ۱۴ نشان داده شده است، با افزایش تعداد خطوط کمکی افقی و عمودی برای تقسیم منطقه به هشت قسمت مساوی، یک برچسب خوب به دست آمد .

در نهایت، ما محل قرارگیری برچسب را در ۲۳ بخش توکیو در شکل ۱۵ نشان می دهیم . ورودی از منابع آموزشی باز GIS [ ۲۹ ] به دست آمد. ارتفاع همه برچسب‌ها روی ۵% ارتفاع Ota-ku تنظیم شد که بیشترین ناحیه در شکل پایین است. عرض هر برچسب روی بارهای ارتفاع تنظیم شد لهتی/۲، جایی که لهتیتعداد حروف در برچسب مربوطه است. تعداد کل خطوط مرزی ۲۳ منطقه ۲۱۴۳۸ و زمان اجرا بدون احتساب پیش پردازش ۰٫۱۳ میلی ثانیه بود. قرار دادن برچسب بد نیست و برچسب ها همپوشانی ندارند. با این حال، یک برجستگی برچسب کمی وجود دارد.

۴٫ گسترش روش پیشنهادی

این بخش قرار دادن برچسب را در مناطقی که فقط تا حدی قابل مشاهده است یا در مناطقی با روابط گنجاندن در نظر می گیرد.

۴٫۱٫ قرار دادن برچسب در یک منطقه جزئی

با توجه به شرایط زیر، می‌توانیم تعیین کنیم که آیا A در داخل قاب نمایش وجود دارد، فقط تا حدی نمایش داده می‌شود یا خارج از قاب نمایش وجود دارد.

(من): آیا خطوط مرزی A قاب نمایش را قطع می کنند؟
(II): آیا یک نقطه دلخواه p در A در داخل قاب نمایشگر قرار دارد؟

شرایط (i) را می توان به سرعت توسط مراحل پیش پردازش توضیح داده شده در بخش ۲٫۳ تعیین کرد. اگر هر تقاطع وجود داشته باشد، منطقه تا حدی نمایش داده می شود. اگر هیچ تقاطعی وجود نداشته باشد و شرط (ii) برآورده شود (راضی نباشد)، A در داخل (خارج) قاب نمایش وجود دارد. شرط (ii) را می توان با کشیدن نیم خط از p در یک جهت و شمارش تعداد تقاطع های این خط با قاب نمایشگر به سرعت تعیین کرد. اگر تعداد تقاطع ها زوج باشد، p در خارج از قاب نمایش وجود دارد. برعکس، اگر تعداد تقاطع ها فرد باشد، p درون قاب نمایشگر وجود دارد.

هنگامی که یک ناحیه A تا حدی در قاب نمایش D قرار دارد ( شکل ۱۶ را ببینید )، روش پیشنهادی ابتدا محل قطع خطوط مرزی A را با قاب نمایش D پیدا می کند. به عنوان مثال، سمت پایین قاب D را در نظر می گیریم . همانطور که در نشان داده شده است شکل ۱۶ نشان داده شده است ، سمت پایین D به عنوان یک خط کمکی افقی h گسترش یافته است. تقاطع ها جساعت۱، جساعت۲, ⋯ سپس، همانطور که در بخش ۲٫۲ توضیح داده شد، شناسایی شدند ، اما تقاطع های خارج از D را حذف کردند . گوشه‌های D در h (به استثنای آن‌هایی که خارج از A هستند ) نیز شناسایی شدند و با تقاطع‌های h و خطوط مرزی یکسان برخورد کردند. توجه داشته باشید که در شکل ۱۶ ، گوشه سمت راست پایین به عنوان تقاطع در نظر گرفته شده است جساعت۲٫ پس از کشیدن یک خط عمودی v”یک نامزد برچسب همانطور که در بخش ۲٫۲ توضیح داده شد ایجاد شد ( شکل ۱۷ را ببینید ). توجه داشته باشید که با توجه به v”، تقاطع ها با مرزهای D نیز مشخص می شوند و تقاطع ها زمانی که خارج از منطقه همپوشانی A و D قرار می گیرند حذف می شوند .

۴٫۲٫ برچسب قرار دادن ویژگی های منطقه با روابط گنجاندن

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

۵٫ نتیجه گیری ها

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

ما آزمایش‌های محاسباتی را برای تأیید اثربخشی روش پیشنهادی انجام دادیم. آزمایش‌ها در زبان برنامه‌نویسی C پیاده‌سازی شدند و بر روی یک CPU با کلاک پایین انجام شدند تا رفتار یک رایانه با کارایی پایین مانند یک دستگاه تبلت را بررسی کنند. نتایج تجربی اثربخشی و کاربرد بلادرنگ روش پیشنهادی را نشان می‌دهد. در کار آینده، با طراحی موقعیت خطوط کمکی، نامزدهای برچسب موثرتری ایجاد خواهیم کرد.

منابع

اوکاموتو، اس. ساکاگوچی، آر. (شرکت داون، کوبه، ژاپن). ارتباطات شخصی، ۲۰۱۵٫
Hirsch, SA الگوریتمی برای قرار دادن خودکار نام در اطراف داده های نقطه ای. صبح. کارتوگر. ۱۹۸۲ ، ۹ ، ۵-۱۷٫ [ Google Scholar ] [ CrossRef ]
کریستنسن، جی. مارکس، جی. Shieber, S. یک مطالعه تجربی از الگوریتم‌ها برای قرار دادن برچسب نقطه ویژگی. ACM Trans. نمودار ۱۹۹۵ ، ۱۴ ، ۲۰۳-۲۳۲٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
ون کرولد، ام. استریجک، تی. Wolff, A. برچسب گذاری نقطه ای با برچسب های کشویی. محاسبه کنید. Geom. تئوری کاربردی ۱۹۹۹ ، ۱۳ ، ۲۱-۴۷٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
فوناکاوا، ک. آبه، ن. یاماگوچی، ک. ماسودا، اس. الگوریتم‌های مسئله برچسب‌گذاری نقشه با اولویت‌ها. IEICE Trans. سرمایه. الکترون. اشتراک. محاسبه کنید. علمی ۲۰۰۵ ، J88-A ، ۶۷۷-۶۸۱٫ (به ژاپنی) [ Google Scholar ]
بکوس، MA; کافمن، ام. سیمونیکس، ا. Wolff، A. برچسب‌گذاری مرزی: مدل‌ها و الگوریتم‌های کارآمد برای نقشه‌های مستطیلی. محاسبه کنید. Geom. تئوری کاربردی ۲۰۰۷ ، ۳۶ ، ۲۱۵-۲۳۶٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
الویم، ACF; Taillard، É.D. POPMUSIC برای مشکل قرار دادن برچسب ویژگی نقطه. یورو جی. اوپر. Res. ۲۰۰۹ ، ۱۹۲ ، ۳۹۶-۴۱۳٫ [ Google Scholar ] [ CrossRef ]
لی، ال. ژانگ، اچ. زو، اچ. کوای، ایکس. Hu, W. یک مدل برچسب‌گذاری بر اساس منطقه متحرک برای قرار دادن برچسب نقطه‌ای. ISPRS Int. J. Geo-Inf. ۲۰۱۶ ، ۵ ، ۱۵۹٫ [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
هاونرت، جی.-اچ. Wolff, A. Beyond Maximum Independent Set: An Extended Integer Programming Formulation for Point Labeling. ISPRS Int. J. Geo-Inf. ۲۰۱۷ ، ۶ ، ۳۴۲٫ [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
مارین، ای. Pelegrín، M. به سوی برچسب گذاری نقشه بدون ابهام – رویکرد برنامه نویسی عدد صحیح و الگوریتم اکتشافی. سیستم خبره Appl. ۲۰۱۸ ، ۹۸ ، ۲۲۱-۲۴۱٫ [ Google Scholar ] [ CrossRef ]
Wolff, A. کتابشناسی نقشه-برچسب زدن. در دسترس آنلاین: https://i11www.iti.kit.edu/map-labeling/bibliography/ (در ۲۶ اوت ۲۰۲۰ قابل دسترسی است).
روی، اس. باتاچارجی، اس. داس، اس. Nandy، SC یک الگوریتم سریع برای مسئله برچسب گذاری نقطه. در مجموعه مقالات هفدهمین کنفرانس کانادایی هندسه محاسباتی، ویندزور، ON، کانادا، ۱۰-۱۲ اوت ۲۰۰۵٫ صص ۱۵۵-۱۵۸٫ [ Google Scholar ]
یاماموتو، ام. کامارا، جی. Lorena, L. الگوریتم سریع قرار دادن برچسب نقطه-ویژگی برای نقشه های صفحه نمایش زمان واقعی. در مجموعه مقالات هفتمین سمپوزیوم برزیل در زمینه ژئوانفورماتیک، Campos do Jordão، برزیل، ۲۰-۲۳ نوامبر ۲۰۰۵٫ صص ۱-۱۳٫ [ Google Scholar ]
Mote, K. قرار دادن سریع برچسب ویژگی نقطه ای برای تجسم های پویا. Inf. Vis. ۲۰۰۷ ، ۶ ، ۲۴۹-۲۶۰٫ [ Google Scholar ] [ CrossRef ]
کامدا، تی. Imai، K. قرار دادن برچسب نقشه برای نقاط و منحنی ها. IEICE Trans. سرمایه. الکترون. اشتراک. محاسبه کنید. علمی ۲۰۰۳ ، E86-A ، ۸۳۵-۸۴۰٫ [ Google Scholar ]
ژانگ، کیو. Harrie, L. برچسب گذاری نقشه بلادرنگ برای برنامه های موبایل. محاسبه کنید. Emviron. سیستم شهری ۲۰۰۶ ، ۳۰ ، ۷۷۳-۷۸۳٫ [ Google Scholar ] [ CrossRef ]
ژانگ، کیو. Harrie, L. قرار دادن برچسب متن و نماد به طور همزمان. کارتوگر. Geogr. Inf. علمی ۲۰۰۶ ، ۳۳ ، ۵۳-۶۴٫ [ Google Scholar ] [ CrossRef ]
لو، اف. دنگ، ج. لی، اس. دنگ، اچ. ترکیبی از تکامل دیفرانسیل و الگوریتم ژنتیک برای مسئله قرار دادن برچسب ویژگی های جغرافیایی چندگانه. ISPRS Int. J. Geo-Inf. ۲۰۱۹ ، ۸ ، ۲۳۷٫ [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
کاکولیس، KG; Tollis, IG یک رویکرد واحد برای برچسب زدن ویژگی های گرافیکی. در مجموعه مقالات چهاردهمین سمپوزیوم سالانه هندسه محاسباتی، مینیاپولیس، MH، ایالات متحده آمریکا، ۷ تا ۱۰ ژوئن ۱۹۹۸٫ صص ۳۴۷-۳۵۶٫ [ Google Scholar ]
واگنر، اف. ولف، ا. کاپور، وی. Strijk, T. سه قانون برای قرار دادن برچسب خوب کافی است. الگوریتمیکا ۲۰۰۱ ، ۳۰ ، ۳۳۴-۳۴۹٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
رایلوف، م. Reimer, A. یک الگوریتم عملی برای حاشیه نویسی خارجی ویژگی های ناحیه. کارتوگر. J. ۲۰۱۷ ، ۵۴ ، ۶۱-۷۶٫ [ Google Scholar ] [ CrossRef ]
آئونوما، اچ. ایمای، اچ. توکویاما، تی. برخی از نمودارهای ورونوی برای مشکلات قرار دادن کاراکترها در پایگاه داده های نقشه. IPSJ SIG Tech. Rep. ۱۹۸۹ , ۸۹-AL-10-5 , ۱-۷٫ (به ژاپنی) [ Google Scholar ]
Barrault, M. روشی برای قرار دادن و ارزیابی برچسب های نقشه منطقه. محاسبه کنید. Emviron. سیستم شهری ۲۰۰۱ ، ۲۵ ، ۳۳-۵۲٫ [ Google Scholar ] [ CrossRef ]
دورشلاگ، دی. پتزولد، آی. Plümer, L. قرار دادن خودکار اشیا در مناطق نقشه. در مجموعه مقالات بیست و یکمین کنفرانس بین المللی کارتوگرافی، دوربان، آفریقای جنوبی، ۱۰-۱۶ اوت ۲۰۰۳٫ ص ۲۶۹-۲۷۵٫ [ Google Scholar ]
ادمونسون، اس. کریستنسن، جی. مارکس، جی. Shieber, S. یک الگوریتم برچسب گذاری نقشه برداری عمومی. Cartographica ۱۹۹۶ ، ۳۳ ، ۱۳-۲۳٫ [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
Van Roessel, W. الگوریتمی برای مکان یابی جعبه های برچسب گذاری نامزد در یک چند ضلعی. صبح. کارتوگر. ۱۹۸۹ ، ۱۶ ، ۲۰۱-۲۰۹٫ [ Google Scholar ] [ CrossRef ]
پینتو، آی. فریمن، اچ. رویکرد بازخورد برای قرار دادن متن منطقه ای نقشه برداری. در پیشرفت در شناخت الگوی ساختاری و نحوی . Springer: نیویورک، نیویورک، ایالات متحده آمریکا، ۱۹۹۶; صص ۳۴۱-۳۵۰٫ [ Google Scholar ]
داده های بنیادی زمین مکانی توسط سازمان اطلاعات مکانی ژاپن. در دسترس آنلاین: https://www.gsi.go.jp/kiban/ (در ۲۶ اوت ۲۰۲۰ قابل دسترسی است).
منابع آموزشی باز GIS. در دسترس آنلاین: https://gis-oer.github.io/gitbook/book/index.html (در ۲۶ اوت ۲۰۲۰ قابل دسترسی است).

شکل ۱٫ قرار دادن برچسب با روش ساده: ( الف ) قرار دادن صحیح در یک شکل ساده. ( ب ) قرار دادن نامناسب در شکلی با ناحیه باریک. و، ( ج ) قرار گرفتن در خارج از یک منطقه با یک تورفتگی بزرگ. اشکال جامد و خطوط مستطیل نقطه چین به ترتیب مرزهای منطقه و برچسب را مشخص می کنند.

شکل ۲٫ خط کمکی h خطوط مرزی A را قطع می کندجساعت۱، جساعت۲، جساعت۳، و جساعت۴٫

شکل ۳٫ نامزد برچسب تعیین شده توسط روش پیشنهادی.

شکل ۴٫ خط کمکی افقی که از سمت چپ ترین نقطه پایانی کشیده شده است پل.

شکل ۵٫ نمونه ای از نامزدهای برچسب.

شکل ۶٫ خطوط مرزی که باید به ترتیب مختصات افقی و عمودی نقاط میانی آنها ذخیره شوند. دایره های سفید نقطه میانی هر خط مرزی را نشان می دهد.

شکل ۷٫ خطوط مرزی که باید در جهت افقی ذخیره شوند به صورت پررنگ مشخص شده اند.

شکل ۸٫ مثالی از یک خط کمکی که یک خط مرزی را قطع می کند که خطوط مرزی ذخیره شده زیادی دارد.

شکل ۹٫ شمارش چند ضلعی های محدب: ( الف ) بخشی از مرز مساحت. شروع از نقطه پایان پ۱، روش چند ضلعی ( b ) را بررسی می کندپ۱پ۲پ۳، ( ج ) چند ضلعی پ۱پ۲پ۳پ۴، و ( d ) چند ضلعی پ۱پ۲پ۳پ۵٫