خلاصه

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

کلید واژه ها:

شبکه جاده ای ؛ ساده سازی ؛ الگوریتم Opheim بهبود یافته است . کاهش دقت ؛ رابطه جهتی فضایی ; الگوریتم ژنتیک

1. معرفی

تحقیق در مورد ساده سازی خطوط در زمینه های گرافیک کامپیوتری و کارتوگرافی ارزشمند است زیرا بیش از 80 درصد عناصر روی نقشه ها خطوط هستند [ 1 ]. الگوریتم کلاسیک داگلاس-پیکر (DP) [ 2 ] اساساً فرآیندی برای استخراج بازگشتی نقاط معتبر است. الگوریتم هنگام انتخاب نقاط، ویژگی های محلی و همچنین جهانی را در نظر می گیرد. در الگوریتم ساده سازی Opheim [ 3 ، 4 ]، محدودیت های حداکثر و حداقل فاصله، ناحیه جستجو را تعیین می کنند، در نتیجه نقاط اولیه میانی، به جز اولین و آخرین نقاط، در ناحیه جستجو حذف می شوند. Visvalingam و Whyatt [ 5] ابتدا یک الگوریتم با استفاده از ناحیه به عنوان یک شاخص ساده شده پیشنهاد کرد. مساحت تشکیل شده توسط هر نقطه اولیه میانی و دو نقطه کارآمد مجاور آن محاسبه می شود. سپس، نقطه اصلی میانی با کوچکترین ناحیه موثر را می توان حذف کرد تا اطمینان حاصل شود که شکل خط ساده شده حداقل تغییر می کند. با این حال، این الگوریتم های اساسی رابطه توپولوژیکی فضایی را در طول ساده سازی در نظر نمی گیرند. بر این اساس این الگوریتم ها بهبود یافته اند. بر اساس الگوریتم اصلی DP، Saalfeld [ 6 ] تضادهای توپولوژیکی موجود را با به روز رسانی پویا ساختار داده بدنه محدب شناسایی و حذف کرد. مانند جاده اصلی، خط ساده شده همچنان می تواند رابطه توپولوژیکی صحیح را با اشیاء فضایی مجاور حفظ کند. پالرو [ 7] الگوریتم DP را بهبود بخشید و یک الگوریتم ساده سازی خط قوی را پیشنهاد کرد که به طور موثر رابطه توپولوژیکی چند خط ساده شده را حفظ می کند و از الگوریتم DP اصلی کارآمدتر است. تینا و همکاران [ 8 ] یک مدل زمینه ای بر اساس الگوریتم DP توسعه داد. این مدل به صورت تدریجی به چند خط اصلی با رئوس مشخصه مربوطه می‌پیچد تا ساده‌سازی ثابتی را حفظ کند. با توجه به دانش فضایی مربوط به خطوط، گوو و همکاران. [ 9 ] یک الگوریتم ساده‌سازی خط مترقی را برای جلوگیری از تقاطع خود خطوط تعمیم‌یافته پیشنهاد کرد. پارک و یو [ 10] روشی را برای بخش بندی خطوط و ساده کردن هر بخش با الگوریتم ساده سازی مناسب تری نسبت به هر الگوریتم دیگر ارائه کرد که خطاهای موقعیتی کمتری بر اساس زاویه و طول ایجاد می کند.
در مقایسه با حذف یک نقطه غیر مشخصه یا حفظ یک نقطه مشخصه در یک زمان، سایر الگوریتم های ساده سازی پیچیدگی ساختار خط را بر اساس حفظ ساختار خط اصلی کاهش می دهند [11 ] . چنین کاهشی با حذف برخی از نقاط به دست می آید و در نتیجه بهترین خط ساده شده خط اصلی ایجاد می شود. نماینده ترین مدل مثلث دلونی محدود برای ساده سازی خط است [ 12 ، 13 ، 14 ، 15 ]. با توجه به شکل خط ساحلی و محدودیت های مناطق خاص، Ai و همکاران. [ 16] الگوریتمی را پیشنهاد کرد که از ساختار منحنی درختان چند شاخه برای ساده‌سازی خط ساحلی استفاده می‌کند. به این ترتیب، شکل اصلی خط ساحلی حفظ شد و سازگاری توپولوژیکی حفظ شد. آی و همکاران [ 17 ] الگوریتم نورد دایره ε پرکال [ 18 ] را شبیه سازی کرد و ساختار پوششی یک خط را بر اساس مثلث سازی دلونی پیشنهاد کرد که برای مقایسه اتصالات مختلف در ناحیه پاکت استفاده می شود. الگوریتم ساده سازی Li-Openshaw [ 19 ] می تواند نتایج ساده سازی خطی مشابه نتایج تعمیم دستی بر اساس اصل طبیعی تعمیم عینی تولید کند. علاوه بر این، الگوریتم را می توان در حالت های شطرنجی، برداری و شطرنجی-بردار استفاده کرد.
با توسعه فناوری رانندگی خودکار وسایل نقلیه و بهبود روش‌های جمع‌آوری اطلاعات نقشه، بسیاری از نقشه‌های شبکه جاده‌ای با دقت بالا برای رانندگی خودکار به طور مداوم جمع‌آوری و اعمال می‌شوند که به یکی از موضوعات داغ در تحقیقات تبدیل شده است. با این حال، دقت نقشه‌های شبکه جاده‌ای برای نرم‌افزار ناوبری سنتی ضروری که در اختیار خودروسازان قرار می‌گیرد، نسبتاً پایین است. طول و عرض جغرافیایی که موقعیت مکانی با دقت بالا را نشان می دهد، داده های نقشه را تا رتبه هفتم بعد از اعشار حفظ می کند، در حالی که طول و عرض جغرافیایی در داده های نقشه برای نرم افزار ناوبری سنتی تنها تا مکان پنجم پس از اعشار حفظ می شود. به عنوان مثال، (15.1234567°، 16.1234567°) نشان دهنده محل یک نقطه مسطح است که در آن 15.1234567 درجه طول جغرافیایی و 16 است. 1234567 درجه عرض جغرافیایی است. مقدار 15.1234567° عددی با هفت رقم اعشار است. هنگام کاهش دقت داده های جاده، (15.1234567 درجه، 16.1234567 درجه) باید تا پنج رقم اعشار گرد شود، به عنوان مثال، (15.12346 درجه، 16.12346 درجه). در کاربردهای واقعی، نقشه‌های شبکه جاده‌ای با دقت پنج رقمی از قبل الزامات دقت داده‌های نقشه ناوبری معمولی را برآورده می‌کنند. به دست آوردن داده های نقشه با دقت پایین برای نقشه های ناوبری معمولی زمان بر و پرهزینه است. هنگامی که داده‌های شبکه جاده‌ای با دقت بالا در یک منطقه خاص جمع‌آوری می‌شوند، باید مستقیماً به نقشه‌های شبکه راه با دقت پنج رقمی مورد نیاز نرم‌افزار ناوبری مرسوم از طریق تعمیم نقشه‌برداری تبدیل شوند تا از بررسی و نقشه‌برداری مکرر داده‌های شبکه جاده‌ای در منطقه جلوگیری شود. همان منطقه این فرآیند تعمیم شبکه جاده‌ای شامل تبدیل دقت داده‌ها در نقشه‌های شبکه راه است و الزامات تولید خاصی دارد، مانند فاصله بین رئوس در جاده‌ها، جهت جاده‌ها، رابطه جهت فضایی بین جاده‌های متصل به گره و فضایی. رابطه توپولوژیکی شبکه راه بنابراین، الگوریتم‌های ساده‌سازی خطوط فوق را نمی‌توان مستقیماً در این تعمیم شبکه جاده اعمال کرد. مطالعات اندکی بر استخراج شبکه های جاده ای با دقت پنج رقمی از شبکه های با دقت هفت رقمی متمرکز شده اند. بنابراین، یک الگوریتم کامل نیاز به پیاده سازی دارد، به ویژه تنظیم بهینه رابطه جهت فضایی بین جاده ها در گره های شبکه راه. رابطه جهت فضایی بین جاده های متصل به گره و رابطه توپولوژیکی فضایی شبکه راه. بنابراین، الگوریتم‌های ساده‌سازی خطوط فوق را نمی‌توان مستقیماً در این تعمیم شبکه جاده اعمال کرد. مطالعات اندکی بر استخراج شبکه های جاده ای با دقت پنج رقمی از شبکه های با دقت هفت رقمی متمرکز شده اند. بنابراین، یک الگوریتم کامل نیاز به پیاده سازی دارد، به ویژه تنظیم بهینه رابطه جهت فضایی بین جاده ها در گره های شبکه راه. رابطه جهت فضایی بین جاده های متصل به گره و رابطه توپولوژیکی فضایی شبکه راه. بنابراین، الگوریتم‌های ساده‌سازی خطوط فوق را نمی‌توان مستقیماً در این تعمیم شبکه جاده اعمال کرد. مطالعات اندکی بر استخراج شبکه های جاده ای با دقت پنج رقمی از شبکه های با دقت هفت رقمی متمرکز شده اند. بنابراین، یک الگوریتم کامل نیاز به پیاده سازی دارد، به ویژه تنظیم بهینه رابطه جهت فضایی بین جاده ها در گره های شبکه راه. مطالعات اندکی بر استخراج شبکه های جاده ای با دقت پنج رقمی از شبکه های با دقت هفت رقمی متمرکز شده اند. بنابراین، یک الگوریتم کامل نیاز به پیاده سازی دارد، به ویژه تنظیم بهینه رابطه جهت فضایی بین جاده ها در گره های شبکه راه. مطالعات اندکی بر استخراج شبکه های جاده ای با دقت پنج رقمی از شبکه های با دقت هفت رقمی متمرکز شده اند. بنابراین، یک الگوریتم کامل نیاز به پیاده سازی دارد، به ویژه تنظیم بهینه رابطه جهت فضایی بین جاده ها در گره های شبکه راه.
در مقایسه با جاده‌های با دقت بالا، شکل جاده‌های با دقت پنج رقمی ممکن است به‌طور قابل‌توجهی تغییر کند زمانی که دقت نشان‌دهنده مختصات یک راس جاده کاهش می‌یابد ( شکل 1 ). به عنوان مثال، پس از کاهش مستقیم دقت، نقطه A در موقعیت 3 قرار دارد، در حالی که انحراف آزیموت ناشی از موقعیت 2 کوچکتر است. بنابراین، ما بر دو مشکل تمرکز کردیم: ساده‌سازی جاده‌ها، حفظ رابطه جهت فضایی بین جاده‌ها، و به‌ویژه چگونگی به حداقل رساندن تغییر جهت مکانی جاده‌ها پس از کاهش دقت. مساحت موثر، فاصله عمودی، شعاع بافر و غیره، معیارهای رایج در الگوریتم‌های نقطه مستقل [ 20 ]، روال‌های پردازش محلی 21] هستند.، 22 ، 23 ، 24 ] یا روتین های جهانی [ 25 ، 26 ، 27 ] برای ساده سازی خط. به عنوان یک الگوریتم ساده سازی خط کلاسیک، الگوریتم Opheim می تواند محدودیت فاصله بین رئوس را در شبکه های جاده ای بیان کند. با این حال، محدودیت های دیگر مانند زوایای چرخش جاده را در نظر نمی گیرد. بنابراین، برای ساده‌سازی جاده، الگوریتم Opheim باید بهبود یابد.
هنگامی که دقت داده‌های جاده‌ها از هفت رقم به پنج رقم کاهش می‌یابد، رابطه جهت فضایی جاده‌های ساده شده باید مطابق با الزامات ناوبری شبکه‌های جاده‌ای تنظیم شود، زیرا کاهش دقت داده‌ها باعث تغییر در رابطه جهت فضایی بین جاده‌ها می‌شود. روش ارزیابی شباهت بر اساس محاسبه شباهت بین ماتریس های رابطه جهتی است که توسط گویال و اگنهوفر [ 28 ] پیشنهاد شده است. این بر اساس محاسبه فاصله جهت اصلی نمودار همسایگی مفهومی است که برای ارزیابی شباهت صحنه مفید است. با در نظر گرفتن روابط جهت بین دو شی در سطوح مختلف جزئیات، گویال و اگنهوفر [ 29] مدل ماتریس جهت – رابطه را گسترش داد و مدل‌های رابطه جهتی فضایی را برای جفت‌های دلخواه نقطه در تعمیم نقشه مطالعه کرد. تانگ و همکاران [ 30 و 31 ] اندازه‌گیری شباهت گرافیکی بین جاده‌های خطی را مورد مطالعه قرار داد و یک مدل اندازه‌گیری برای داده‌های فضایی خطی مشابه بر اساس ادغام نمای فاصله و نمای مجموعه ویژگی‌ها، که نماهایی برای شناخت شباهت استفاده می‌شوند، پیشنهاد کرد. با تئوری توسعه یافته صحنه های فضایی پیچیده، مدل های دیگری برای توصیف صحنه فضایی و معیارهای شباهت آنها پیشنهاد شد [ 32 ، 33 ]. یان و همکاران [ 34] بر بیان کمی از ویژگی های روابط شباهت فضایی در فضاهای نقشه متمرکز شده است. لوئیس و اگنهوفر [ 35 ] مدلی را برای توصیف صحنه فضایی با استفاده از دنباله‌ای از تقاطع‌های فضایی دقیق و مهار اشیا ایجاد کردند، و ارتباطات بین اشیاء فضایی پیچیده را ثبت کردند. باتنفیلد [ 36 ] الگوریتمی را ارائه کرد که ویژگی های هندسی و توپولوژیکی را حفظ می کند در حالی که به تدریج مختصات برداری را منتقل می کند. با این حال، این مطالعات کاهش دقت را در طول ساده‌سازی شبکه جاده‌ای در نظر نگرفتند. گوو و همکاران [ 37] الگوریتمی را برای تنظیم رابطه جهت فضایی در گره های شبکه های جاده ای تنها با در نظر گرفتن راه حل بهینه محلی پیشنهاد کرد. در این تحقیق، ما از یک الگوریتم هوشمند برای یافتن راه‌حل بهینه جهانی در فرآیند تنظیم رابطه جهت فضایی بین جاده‌ها در گره‌های شبکه راه‌ها استفاده کردیم.
هنگامی که دقت داده ها پنج رقمی است، از نظر ریاضی، تمام نقاط جاده باید در تقاطع شبکه های مربعی با یک واحد طول باشند، بنابراین مدل شبکه در این رویکرد استفاده می شود. ما از هر دو الگوریتم Opheim بهبود یافته و حفظ رابطه جهتی فضایی شبکه‌های جاده‌ای برای تولید نقشه‌های شبکه جاده‌ای با دقت پایین که الزامات تولید و جلوه‌های بصری را برآورده می‌کند، استفاده کردیم. ما به ویژه بر تغییر شکل جاده و رابطه جهت فضایی در گره ها تمرکز کردیم. مشارکت های زیر توسط این کار ارائه شده است:
(1) یک الگوریتم Opheim بهبود یافته همراه با نگهداری شکل محلی جاده ها.
(2) در فرآیند ساده سازی جاده و تنظیم رابطه جهتی فضایی، حفظ سازگاری روابط توپولوژیکی برای جلوگیری از خطاهای توپولوژیکی در نظر گرفته می شود.
(3) اگر یک گره مستقیماً به نقطه‌ای متصل باشد که یکی از گره‌های دیگر نیست، این گره یک گره عمومی نامیده می‌شود ( شکل 2 ). هنگامی که دقت داده‌های جاده کاهش می‌یابد، رابطه جهتی فضایی بین بخش‌های جاده متصل در هر گره عمومی به طور بهینه تنظیم می‌شود. تغییر در رابطه جهت فضایی در هر گره عمومی پس از کاهش دقت کوچکترین است.
(4) اگر دو یا چند گره مستقیماً به هم متصل شوند، این گره ها گره های ویژه نامیده می شوند ( شکل 2 ). الگوریتم ژنتیک با استراتژی نخبگان (e-GA) برای تنظیم رابطه جهت فضایی در گره‌های خاص اعمال می‌شود که به یافتن هوشمندانه راه‌حل بهینه جهانی کمک می‌کند. پس از کاهش دقت داده‌های جاده در تعمیم شبکه جاده، تغییرات کلی در جهت‌های فضایی بخش‌های جاده متصل در یک زیر گروه از گره‌های ویژه می‌تواند تا حد امکان کوچک باشد.
مراحل اصلی روش ما شامل دو گردش کار برای مدیریت داده های جاده است ( شکل 2 ). اولین مورد ساده سازی جاده با حفظ رابطه جهت فضایی جاده های متصل به رئوس است که شامل محدودیت های بخش 2 ، روش استخراج ویژگی های توپوگرافی جاده در بخش 3 و الگوریتم بهبود یافته Opheim در بخش 4 است . دومین گردش کار، حفظ رابطه جهتی فضایی یک زیر گروه از شبکه راه است که با گره های ویژه یا یک گره عمومی متصل است که در بخش 5 توضیح داده شده است . ما نتایج آزمایش‌ها را در بخش 6 تجزیه و تحلیل می‌کنیم و نتایج خود را در آن ارائه می‌کنیمبخش 7 تجزیه و تحلیل می‌کنیم .

2. محدودیت های تعمیم جاده برای ناوبری

2.1. مدل داده ای جاده ها

در مدل داده های جاده برای ناوبری، مجموعه ای از نقاط { P 0 , …, P i , …, P m − 1 } مجموعه ای از نقاط متوالی در جاده را نشان می دهد. گره های V j = P 0 و V k = P m − 1 نقطه پایانی یا نقطه تقاطع مجازی سه بعدی جاده را نشان می دهند و نقطه P i ( i ≠ 0, i ≠ m − 1 ) راس جاده را نشان می دهد. در شکل 3 نشان داده شده استآ. نقاط تقاطع مجازی سه بعدی و نقاط انتهایی مطابق با پرچم ویژگی نقاط متمایز می شوند. اگر پرچم = 0 باشد، آنگاه نقطه تقاطع مجازی سه بعدی است که در آن دو جاده پیش بینی شده در فضای دوبعدی تلاقی می کنند اما در فضای سه بعدی نه. اگر پرچم = 2 باشد، آنگاه نقطه پایان است. اگر flag = 1 باشد، این راس را نشان می دهد.
شبکه جاده در فضای دو بعدی را می توان به عنوان یک ساختار نمودار G متشکل از مجموعه ای از گره های V با یک پرچم مشخصه و مجموعه ای از لبه های E مشاهده کرد و همانطور که در شکل 3 ب نشان داده شده است به صورت G = ( V , E ) نشان داده شده است . در شبکه راه در این مطالعه، یک لبه، بخش جاده بین دو گره و قطعه جاده، مقطع بین دو نقطه متوالی باشد. در شکل 3 الف، بخش جاده پ1پ2با گره V j مرتبط است و نقاط P 2 و P 3 نقاط مجاور هستند. بنابراین، سه نوع نقطه در شبکه راه ها وجود دارد: نقاط تقاطع، نقاط انتهایی و رئوس. لبه ها در نقاط انتهایی یا نقاط تقاطع به هم متصل می شوند. بنابراین، گره ها ممکن است نقاط انتهایی یا نقاط تقاطع باشند، همانطور که در شکل 3 ب نشان داده شده است. فرض کنید V i ∈ V ( G )، و تعداد یال های مرتبط با نقطه V i در G را درجه V i می نامند [ 38 ]. در شکل 3 ب، درجه گرهV 1 3 است و درجه گره V 2 4 است.

2.2. محدودیت در تعمیم جاده

مختصات مسطح نقاط در جاده ها را می توان با ( ψ , r ) نشان داد که ψ طول جغرافیایی و r عرض جغرافیایی است. به عنوان مثال، (15.1234567°، 16.1234567°) نشان دهنده محل یک نقطه مسطح است که در آن 15.1234567 درجه طول جغرافیایی و 16.1234567 درجه عرض جغرافیایی است. مقدار 15.1234567° عددی با هفت رقم اعشار است. هنگام کاهش دقت داده های جاده، (15.1234567 درجه، 16.1234567 درجه) باید تا پنج رقم اعشار گرد شود، به عنوان مثال، (15.12346 درجه، 16.12346 درجه). مدل شبکه برای نشان دادن جاده های دقیق مختلف استفاده می شود. در شکل 1خط آبی نشان دهنده یک جاده با دقت هفت رقمی و خط نارنجی نشان دهنده همان جاده با دقت پنج رقمی است. هنگامی که یک شبکه جاده ای با دقت هفت رقمی به دقت پنج رقمی تعمیم می یابد، چهار محدودیت در تعمیم جاده به شرح زیر است:
(1) محدودیت دقت موقعیت: نقاط تقاطع و نقاط پایانی را نمی توان حذف کرد، در حالی که رئوس ممکن است حذف شوند. در طول نگهداری شکل محلی، محدودیت حرکت نقطه d ≤ √2 δ است ، که در آن d فاصله از نقطه با مختصات هفت رقمی تا نقطه با مختصات پنج رقمی است و δ دقت مختصاتی است که توسط کاربران تعریف شده است.
(2) محدودیت فاصله: آستانه حداقل فاصله بین دو نقطه مجاور در یک جاده به ε , و ε ≤ | P i − P i + 1 | ≤ k × ε ( ε > √2 ، k > 1، که توسط کاربران تعریف می شود، و P i و P i + 1 دو نقطه مجاور هستند).
(3) محدودیت برای تشابه جهت فضایی: آزیموت بخش جاده، زاویه بین آن و جهت شمال است. در شکل 4 a، A i آزیموت بخش جاده است Vمنپمن+1با دقت هفت رقمی و A’i آزیموت قطعه جاده استVمنپمن+1″با دقت پنج رقمی رابطه جهت فضایی بین دو بخش جاده متوالی در یک جاده با زاویه چرخش توصیف می شود. در شکل 4 b، T i زاویه چرخش دو بخش جاده در راس P i با دقت هفت رقمی است و T’i زاویه گردش همان بخش جاده در راس P i با دقت پنج رقمی است.

گره کلی V m در شبکه جاده تحت تأثیر تنظیم گره های دیگر در حفظ رابطه جهتی فضایی قرار نمی گیرد. به عبارت دیگر، هیچ گره دیگری با آن متصل نیست (گره V m ، شکل 5 a). همانطور که در شکل 5 الف نشان داده شده است، ابتدا تمام موقعیت های ممکن پنج رقمی تمام بخش های جاده مرتبط با گره V m محاسبه می شود. سپس می‌توانیم حداقل مجموع را در تمام تغییرات آزیموت ممکن انتخاب کنیم. هر چه تغییرات آزیموت کل کوچکتر باشد، جهت فضایی مشابه تر است. شباهت هر تغییر آزیموت ( τ ) در گره V mرا می توان با استفاده از رابطه (1) محاسبه کرد، که در آن η 1 آستانه تغییرات آزیموت یک بخش جاده بین دو نقطه مجاور است:

اسمنمترمنلآrمنتیyVمتر(τ)={0،∀|آمن-آمن”(j،ک)|>η1یا توپولوژی خطا1-∑من=0م-1|آمن-آمن”(j،ک)|η1×م،|آمن-آمن”(j،ک)|≤η1

که در آن SimilarityV m شباهت آزیموت تمام بخش‌های جاده مرتبط با گره V m است ، M درجه گره V m ، A i آزیموت قطعه جاده l i ( l i با گره V m مرتبط است ) با هفت رقم است. دقت، A’i آزیموت l i با دقت پنج رقمی است، و j و k موقعیت اختیاری گره و نقطه مجاورت آن را با دقت پنج رقمی در این بخش جاده l نشان می دهند.i به ترتیب از اعداد صحیح 0 تا 3 متغیر است.

اگر یک گره حداقل با یک گره دیگر توسط یک قطعه مستقیم متصل شود، این گره ها گره های ویژه نامیده می شوند (به عنوان مثال، گره 1~4، 6، 8~10 در شکل 6 ) . گره های ویژه متصل به گره های مجاور باید به عنوان یک کل به نام زیر گروه محلی G در نظر گرفته شوند . برای زیرگروه‌های محلی G در شبکه‌های جاده‌ای، شباهت جهت فضایی هر وضعیت تغییر شده ممکن ( τ ) از بخش‌های جاده متصل در گره‌های G را می‌توان با استفاده از رابطه (2) محاسبه کرد. مکان های پنج رقمی گره های ویژه زمانی انتخاب می شوند که SimilarityG ( τ ) بزرگترین در تمام حالت های ممکن باشد.

اسمنمترمنلآrمنتیyجی(τ)={0،∀|بمن-بمن”(j،ک)|>η1یا توپولوژی خطا1-∑من=0ن-1|بمن-بمن”(j،ک)|η1×ن،|بمن-بمن”(j،ک)|≤η1

که در آن SimilarityG تشابه آزیموت بخش‌های جاده را در مجموعه L مرتبط با گره‌های ویژه در G پس از کاهش دقت نشان می‌دهد. مجموعه L بخش های جاده متصل به هر گره را در G ذخیره می کند ، جایی که داده ها تکراری نیستند. N تعداد بخش های جاده در L است . B i آزیموت l i ( l i ∈ L ) با دقت هفت رقمی است. B’ i آزیموت l i با دقت پنج رقمی است. و j و kموقعیت اختیاری دو گره مرتبط با l i را نشان می دهد که از عدد صحیح 0 تا 3 متغیر است.

فرض کنید P i راس جاده باشد و رابطه جهت مکانی در راس P i با زاویه چرخش اندازه گیری می شود. همانطور که در شکل 5 b نشان داده شده است ، Pi – 1 ، Pi و Pi + 1 می توانند در چهار موقعیت اختیاری هنگام کاهش دقت قرار گیرند. هنگامی که اختلاف زاویه چرخش از دقت هفت تا پنج رقمی در راس P i کوچکترین باشد، شباهت رابطه جهت فضایی در راس P i بزرگترین است، همانطور که در رابطه (3) نشان داده شده است. η 2آستانه تغییر زاویه چرخش در راس P i است .

اسمنمترمنلآrمنتیyپمن={0،∀|تیمن-تیمن”(j)|>η2یا توپولوژی خطا1-|تیمن-تیمن”(j)|η2،|تیمن-تیمن”(j)|≤η2

جایی که SimilarityP i شباهت جهت فضایی جاده را در راس P i نشان می دهد ، i ( i ∈{0,1, …, m − 1}) نشان دهنده i مین راس در جاده است، T i زاویه چرخش در i است. راس راس قبل از تنظیم شکل محلی، T’i زاویه چرخش در راس i با دقت پنج رقمی پس از تنظیم شکل محلی، m تعداد رئوس موجود در جاده است، و j نشان دهنده یکی از موقعیت های اختیاری راس P’iو یک عدد صحیح از 0 تا 3 است.

(4) محدودیت‌های سازگاری توپولوژیکی: اگر راس P i حذف یا جابه‌جا شود، آن‌گاه ممکن است رابطه توپولوژیکی اصلی از بین برود، همانطور که در شکل 7 نشان داده شده است . در فرآیند حذف راس، می‌توان قضاوت کرد که آیا نقاط همسایگی در مثلث در حال حذف هستند یا خیر. سپس می دانیم که حذف نقطه P i توپولوژی را از بین می برد، همانطور که در شکل 7 a نشان داده شده است، به عنوان مثال، چند خط L 1 یا چند خط L 1 که با چندخط L 2 قطع می شود در هنگام حذف نقطه P i ، توپولوژی را از بین می برد.. در حفظ رابطه جهت فضایی، همانطور که در شکل 7 ب نشان داده شده است، گره V i و هر دو بخش جاده مرتبط (به عنوان مثال، l 1 و l 2 ) یک بخش مثلثی S را تشکیل می دهند . ما قضاوت می‌کنیم که آیا این تنظیم منجر به از دست دادن سازگاری توپولوژیکی می‌شود یا خیر با قضاوت در مورد اینکه آیا نقاط (به عنوان مثال، نقطه Pj ) در بخش S در بخش S هستند که توسط گره V’ i و دو بخش جاده با دقت پنج رقمی پس از تعمیر تشکیل شده‌اند. رابطه جهتی فضایی به طور همزمان، موقعیت های نسبی l 1 ،l 2 , l 3 , l 4 بدون تغییر باقی می مانند.

3. استخراج ویژگی های توپوگرافی در یک بخش جاده

3.1. استخراج ویژگی 3D Terrain

شیب ویژگی توپوگرافی را توصیف می کند، که اطلاعات مهمی در ناوبری برای یک جاده سه بعدی است. علائم مثبت و منفی شیب به ترتیب سربالایی و سرازیری را منعکس می کند. آستانه α 1 و α 2 داده شده است ( α 1 < α 2 )، که α 1 نشان دهنده حد بالایی شیب جاده صاف است و α 2 نشان دهنده حد پایین شیب تند است. شیب i ،1 شیب بخش جاده است پمن-1پمنو شیب i ,2 شیب بخش جاده است پمنپمن+1. اگر و فقط اگر | شیب i ,1 | ≤ α 1 و | شیب i ,2 | ≤ α 1 ، سپس یک جاده صاف جزئی در P i وجود دارد. در غیر این صورت، تغییر شیب رخ می دهد.

تغییر شیب در راس P i را می توان با Δ شیب i بیان کرد ، که در آن Δ شیب i = | شیب i ,1 − شیب i ,2 | که مربوط به دو بخش جاده مرتبط با P i است . با توجه به آستانه β در زمانی که Δ شیب i > β ، تغییر شیب در Pi زیاد است و Pi به عنوان یک نقطه زمین بحرانی تعریف می شود. شش نوع نقطه بحرانی زمین (انواع ①–⑥) در یک جاده در شکل 8 نشان داده شده است . محورy نشان دهنده ارتفاع ( z ) رئوس در یک جاده و محور x نشان دهنده طول ( x ) بخش جاده از یک راس تا گره در امتداد جاده است. Origin O یک گره از جاده است. روشهای شناسایی متناظر نقاط حیاتی زمین پیشنهادی در این مطالعه در رابطه (4) نشان داده شده است.

{اگر اسلoپهمن،1>α2&&|اسلoپهمن،2|<α1سپس نوع①اگر اسلoپهمن،1<-α2&&|اسلoپهمن،2|<α1سپس نوع②اگر |اسلoپهمن،1|<α1&&اسلoپهمن،2>α2سپس نوع③اگر |اسلoپهمن،1|<α1&&اسلoپهمن،2<-α2سپس نوع④اگر اسلoپهمن،1>α2&&اسلoپهمن،2<-α2سپس نوع⑤اگر اسلoپهمن،1<-α2&&اسلoپهمن،2>α2سپس نوع⑥

3.2. استخراج یک جاده طولانی، مستقیم و هموار

برای نقشه های شبکه راه، بخش های طولانی، مستقیم و مسطح جاده اطلاعات معنایی مهمی را ارائه می دهند. آستانه طول یک خط بلند، مستقیم و مسطح به صورت γ تعریف می شود و نواری با عرض کوچک μ [ 23 ] برای استخراج آن از چند خط، همانطور که در شکل 9 نشان داده شده است، استفاده می شود . نقطه اولیه P j در مرکز نوار قرار دارد. جهت اولیه نوار موازی با بخش جاده است که از نقطه اولیه و نقطه بعدی آن تشکیل شده است. نوار در جهت اولیه جابه‌جا می‌شود تا زمانی که نوار از چند خط فاصله بگیرد. مجموعه نقطه { P j , P j + 1 , …, P j + m } که نوار از آن عبور کرده است، یک خط مستقیم را تشکیل می دهد. اگر طول L خط مستقیم بزرگتر از γ باشد ، آنگاه دو نقطه انتهایی این بخش جاده از Pj تا Pj + m به عنوان نقاط توپوگرافی بحرانی برای یک بخش جاده طولانی، مستقیم و مسطح مشخص می‌شوند . P j + m نقطه اولیه بعدی چند خط باقی مانده در جاده است و همین روند تا زمانی که نوار از انتهای چند خط عبور کند تکرار می شود. در نهایت، تمام بخش های جاده طولانی، مستقیم و مسطح استخراج می شود.

4. ساده سازی راه

4.1. الگوریتم اوفیم

همانطور که در شکل 10 نشان داده شده است ، الگوریتم Opheim ناحیه جستجو را با عرض بیشتر μ به عنوان نوار در شکل 9 ، و همچنین محدودیت فاصله حداقل و حداکثر تعریف می کند. تمام رئوس در ناحیه جستجو که شعاع آنها حداقل فاصله است حذف می شوند. به جز آخرین راس ( P 3 در شکل 10 سمت چپ) در ناحیه جستجو که شعاع آن حداکثر فاصله است، سایر رئوس در این ناحیه جستجو نیز حذف می شوند. سپس، این راس حذف نشده ( P 3 در شکل 10 ، سمت راست) مرکز ناحیه جستجوی بعدی و راس P5 در شکل 10 است.حق پیدا می شود منطقه جستجو در امتداد خط اصلی حرکت می کند تا نقطه پایانی دیگری از این خط انتخاب شود.

4.2. الگوریتم Opheim بهبود یافته است

حذف رئوس در یک جاده طولانی، مستقیم و هموار ساده است و نباید رابطه توپولوژیکی را از بین ببرد. هنگامی که یک بخش جاده طولانی، مستقیم و مسطح جستجو می شود، دو نقطه پایانی این بخش جاده نباید حذف شوند. رئوس بین دو نقطه پایانی معمولا حذف می شوند، اما برخی از رئوس بین این نقاط پایانی باید مطابق با الزامات ناوبری حفظ شوند. فاصله بین دو راس متوالی حفظ شده باید بزرگتر از آستانه تعریف شده توسط مدل نقشه شبکه راه باشد. در این مطالعه، از الگوریتم ساده سازی خط اوفیم [ 3 ] برای حذف رئوس بین دو نقطه انتهایی یک بخش جاده طولانی، مستقیم و صاف استفاده شد.
حذف رئوس در جاده های منحنی شبیه به آن در جاده های مستقیم است. با این حال، پیچیده تر است، زیرا تمام نقاط بحرانی و موقعیت های مختلف ممکن باید در نظر گرفته شود. حداقل آستانه محدودیت فاصله ε است . ناحیه جستجو با نقطه اولیه به عنوان مرکز دایره و آستانه محدودیت فاصله ε به عنوان شعاع تعیین می شود. قبل از حذف رئوس، رئوس و گره های مهم بحرانی در شبکه راه برای ناوبری نباید حذف شوند. مقدار مشخصه Rank i هر نقطه در نقاط مشخصه توپوگرافی جاده به صورت Rank i = 1 تعریف می شود. Rank i سایر رئوس= 0. در فرآیند حذف راس، اگر حذف راس P i باعث تعارض توپولوژیکی شود، رتبه i = 2 است. روش قضاوت درگیری های توپولوژیکی در بخش 2 توضیح داده شد .

یک جاده R = { P 0 , P 1 , …, P i , …, P m − 1 } را فرض می کنیم که m نشان دهنده تعداد رئوس است. فرض کنید P i -1 نقطه اولیه باشد. طول از پمن-1پمنبه صورت D i ،1 و طول نشان داده می شودپمنپمن+1به صورت D i ،2 نشان داده می شود . هر رأس P i در جاده دارای یک ویژگی Remove i است که برای نشان دادن حذف شدن راس استفاده می شود. Remove i = 0 به این معنی است که راس P i نه حذف می شود و نه به عنوان یک نقطه مشکل علامت گذاری می شود. Remove i = 1 یعنی راس P i حذف خواهد شد. Remove i = 2 به این معنی است که راس P i حذف نمی شود، اما به عنوان یک نقطه مشکل برای رسیدگی بیشتر علامت گذاری می شود زیرا حذف راس P iباعث تضاد توپولوژیکی می شود. با توجه به آستانه زاویه θ ، اگر مقدار مطلق زاویه چرخش T i در راس P i کوچکتر از آستانه θ باشد ، راس P i باید حذف شود. الگوریتم تعیین اینکه آیا راس P i باید حذف شود در شکل 11 نشان داده شده است و شبه کد به عنوان الگوریتم 1 ارائه شده است.

الگوریتم 1 : نشانگر حذف راس ( R , i )
ورودی : یک جاده R با m راس ( P 0 , …, P i , …, Pm − 1 ) و حداقل تحمل فاصله ε
خروجی : نقطه P i با مقدار انتساب Remove /* Remove i */
1.  اگر D i ، 1 < ε ( شکل 11 a)
2.   اگر رتبه i = 0 باشد
3.     سپس TopologicalConflict ( رتبه i ) را فراخوانی کنید.
4.     اگر رتبه i = 2 باشد
5.      سپس i را حذف کنید ← 2
6.      else حذف i ← 1
7.   else ( شکل 11 ب)
8.     اگر D i ، 2 ≥ ε ( شکل 11 ج)
9.      سپس i ← 0 را حذف کنید
10.      else ( شکل 11 د)
11.       اگر D i + 1 ، 2 ≥ ε ( شکل 11 e)
12.        پس اگر | T i | <= | T i + 1 | ( شکل 11 گرم)
13.          سپس TopologicalConflict ( رتبه i ) را فراخوانی کنید.
14.          اگر رتبه i = 2 باشد
15.            سپس Remove i ← 2
16.            else حذف i ← 1
17.      else ( شکل 11 f)
18.        اگر | T i | < θ یا | T i | <= | T i + 1 | ( شکل 11 i,j)
19.         سپس TopologicalConflict ( رتبه i ) را فراخوانی کنید.
20.         اگر رتبه i = 2 باشد
21.          سپس Remove i ← 2
22.          else حذف i ← 1
23.  پایان اگر
24.  بازگشت حذف i
پس از پردازش داده های جاده طبق الگوریتم 1، رئوس علامت گذاری شده به عنوان نقاط مشکل در این جاده باید به طور تکراری بر اساس همان محدودیت ها مدیریت شوند تا زمانی که هیچ نقطه مشکلی در جاده وجود نداشته باشد یا نقاط مشکل حذف نشوند. سپس، ما تمام جاده‌ها را با استفاده از الگوریتم 1 مدیریت کردیم. الگوریتم Opheim بهبودیافته پیشنهاد شده در این مقاله تاکید می‌کند که در فرآیند حذف رئوس یک به یک، نتایج هر مرحله پردازش باید سعی کند تا حد امکان رابطه فضایی را از بین ببرد. اگر رابطه فضایی آسیب ببیند، باید مشکلات را شناسایی کرد و باید به طور مکرر با این نقاط برخورد کرد تا زمانی که قابل رسیدگی نباشد و یا به آنها رسیدگی نشود.

4.3. نگهداری شکل محلی در حالی که دقت را کاهش می دهد

همانطور که در شکل 1 نشان داده شده است، همانطور که دقت داده های شبکه جاده کاهش می یابد، شکل جاده باید تغییر کند . در مدل شبکه ای، هر نقطه با دقت هفت رقمی به نقطه ای با دقت پنج رقمی تبدیل می شود که دارای چهار موقعیت اختیاری است. تغییر در زاویه چرخش در نقطه P i در این مطالعه برای توصیف تغییر شکل جاده استفاده شده است. شباهت جهت فضایی SimilarityP i در نقطه P i شباهت شکل محلی را نشان می دهد. آستانه زاویه θ داده شد و مقدار مطلق زاویه چرخش T i در راس P i در آستانه θنشان دهنده یک خط مستقیم است. جهت جاده در راس P i دو احتمال دیگر دارد: اگر T i > θ , سپس به چپ بپیچید. اگر T i < – θ , سپس به راست بپیچید.
نگهداری شکل محلی باید دو شرط زیر را برآورده کند: (1) تغییر جهت کم باشد و (2) موقعیت بهینه باشد. یک موقعیت بهینه به این معنی است که با انتخاب موقعیت چهار موقعیت اختیاری راس P i می‌توان شکل محلی را شبیه‌ترین شکل به شکل اصلی کرد، که مقدار SimilarityP i را به حداکثر می‌رساند . همانطور که در شکل 4 ب نشان داده شده است، فرض می شود که مکان بهینه P i – 1 انتخاب شده باشد. مکان بهینه راس P i نه تنها به راس P i − 1 بلکه به راس P i + 1 نیز مربوط می شود.. فرآیند انتخاب مکان بهینه آن به شرح زیر است:
(1) موقعیت غیرممکن راس P i مطابق با SimilarityP i – 1 با دقت پنج رقمی حذف می شود. اولاً، موقعیت‌های با دقت پنج رقمی می‌توانند محدودیت دقت را برآورده کنند و نمی‌توانند باعث خطای توپولوژیکی شوند. ثانیا، SimilarityP i – 1 می تواند برای حذف مکان های به خصوص ضعیف بر اساس محدودیت های ناوبری استفاده شود.
(2) موقعیت بهینه راس P i بر اساس SimilarityP i انتخاب می شود . پس از کاهش دقت، از نظر تئوری 16 موقعیت اتصال ممکن برای رئوس P i و P i + 1 وجود دارد . پس از حذف موقعیت های غیرممکن با دقت پنج رقمی، موقعیت با کمترین تشابه P i در موقعیت های ممکن با دقت پنج رقمی راس P i به عنوان بهینه انتخاب می شود.
از نظر تئوری، در طول نگهداری شکل محلی جاده، زمانی که خطاهای توپولوژیکی در تمام موقعیت های اختیاری یک راس رخ می دهد، موقعیتی که جاده تنظیم شده را به شکل اصلی جاده نزدیک می کند انتخاب می شود و خطاهای توپولوژیکی در نتیجه مشخص می شوند. پس از نگهداری شکل جاده، رئوس جاده‌ای که محدودیت‌های زیر دقت پنج رقمی را برآورده نمی‌کنند، باید حذف شوند. روش تفصیلی در بخش 4.1 توضیح داده شد .

5. حفظ رابطه جهتی فضایی در گره ها

5.1. تنظیم رابطه جهتی فضایی در یک گره عمومی

اگر یک گره با یک جاده مستقیم متصل شود، این گره یک گره عمومی نیست و در اینجا به عنوان یک گره خاص نامیده می شود. این جاده مستقیم فقط از دو گره تشکیل شده است. بنابراین، گره عمومی فقط در مجاورت رئوس است. موقعیت های حفظ رابطه جهتی فضایی در یک گره کلی در شکل 12 نشان داده شده است . عملکرد نشان دادن بهترین وضعیت در فرآیند حفظ روابط فضایی در هر گره عمومی به شرح زیر است:

حداکثر اسمنمترمنلآrمنتیyVمتر(τ).
الگوریتم به شرح زیر است:
(1) هنگامی که دقت کاهش می یابد، تمام موقعیت های اتصال ممکن بین گره V m و رئوس مجاور آن در نظر گرفته می شود و انحرافات آزیموت هر موقعیت اتصال ( τ ) محاسبه می شود.
(2) موقعیت‌های اتصالی که با رابطه توپولوژیکی اصلی ناسازگار هستند و موقعیت‌های اتصال که در آن‌ها تغییرات آزیموت بیشتر از آستانه داده‌شده η1 است، حذف می‌شوند، همانطور که در شکل 12 a نشان داده شده است .
(3) موقعیت های اتصال باقی مانده با یکدیگر مطابق با SimilarityV m ( τ ) مقایسه می شوند. همانطور که در شکل 12 ب نشان داده شده است، ما وضعیت بهینه را با دقت پنج رقمی انتخاب می کنیم.
در این فرآیند اگر خطاهای توپولوژیکی در همه طرح های تنظیمی رخ دهد، طرح بهینه انتخاب شده از آنها نیز باعث خطاهای توپولوژیکی می شود و خطاهای توپولوژیکی در نتیجه مشخص می شود.

5.2. تنظیم رابطه جهتی فضایی در گره های ویژه

5.2.1. تفاوت بین دو نوع تنظیم

در شکل 13 a، گره های V 1 ، V 2 ، V 3 و V 4 گره های خاصی هستند. بر اساس رابطه (5)، اگر ابتدا رابطه جهتی فضایی در گره V 1 تنظیم شود، نتیجه ناحیه جزئی همانگونه است که در شکل 13 ب نشان داده شده است. اگر ابتدا رابطه جهت فضایی در V 2 تنظیم شود، نتیجه ناحیه جزئی همانطور که در شکل 13 نشان داده شده است.ج. گره های ویژه مستقیماً بر یکدیگر تأثیر می گذارند. نتایج نگهداری جهت مکانی نه تنها به آستانه مربوط می شود بلکه به ترتیب پردازش گره های ویژه نیز نزدیک است. برای زیرگروه‌های محلی شبکه‌های جاده‌ای که مستقیماً توسط گره‌های ویژه و رئوس مجاورت آنها تشکیل شده‌اند، نتایج تنظیم جهت فضایی ممکن است تغییر کلی در رابطه جهت فضایی را به حداقل نرساند. برای حل این مشکل، ما بر بخش‌های جاده‌ای که با گره‌های ویژه در زیرگروه‌های محلی شبکه‌های جاده‌ای متصل هستند، تمرکز کردیم و یک الگوریتم هوشمند برای دستیابی به ترکیب بهینه و در عین حال کاهش دقت شبکه راه‌ها ساختیم.
5.2.2. الگوریتم ژنتیک استراتژی نخبگان برای تنظیم جهت فضایی
گره‌های ویژه‌ای که مستقیماً در یک شبکه جاده‌ای متصل می‌شوند باید به‌عنوان یک ساختار اجتماعی برای حفظ روابط جهتی فضایی به نام زیرگروه محلی سازماندهی شوند. روش‌های بسیاری برای استخراج ساختار جامعه [ 39 ] یا تعمیم شبکه‌های جاده‌ای [ 40 ] مورد مطالعه قرار گرفته‌اند، مانند یک الگوریتم طیفی برای تشخیص جامعه بر اساس ماتریس مشخصه شبکه [ 41 ] و تشخیص جوامع با فشرده‌سازی شرح جریان‌های اطلاعاتی در شبکه ها [ 42 ]. ما از تکرار چرخه‌ای در این کار استفاده کردیم، و گره‌های ویژه در شبکه‌های جاده‌ای که مستقیماً به هم متصل هستند به طور مداوم در همان زیر گروه محلی G ادغام می‌شوند.. رئوس مجاورت بخش‌های جاده مرتبط با گره‌ها نیز به عنوان «گره‌های مجازی» به زیرگروه محلی G اضافه می‌شوند تا آنها را تنظیم کنند.
هنگامی که دقت داده های جاده از هفت رقم به پنج رقم کاهش می یابد، هر گره یا رأس مجاور آن چهار گزینه دارد. 4 موقعیت اختیاری برای یک زیر گروه از گره های خاص وجود دارد، که در آن N تعداد گره ها و نقاط مجاورت آنها در G است . وقتی N نسبتاً بزرگ است، یافتن راه حل بهینه از طریق روش جامع غیرممکن است. یک الگوریتم ژنتیک با استراتژی نخبگان [ 43] در این تحقیق برای حل مشکل استفاده شد. استراتژی نخبگان به این معنی است که اگر تناسب اندام یک فرد در جمعیت های گذشته بیشتر از هر فرد در جمعیت فعلی باشد، این رشته در نسل فعلی حفظ می شود. بر این اساس، ما یک کتابخانه نگهداری نخبگان با ظرفیت ثابت اضافه می کنیم تا بهترین افراد را تا نسل فعلی حفظ کنیم. مسئله برای تعیین آرایش و ترکیب آیتم‌های خاصی که محدودیت‌ها را برآورده می‌کنند، انتزاع می‌شود. استراتژی نخبگان می تواند تضمین کند که فرد مطلوب نابود نمی شود. الگوریتم های هوشمند به طور گسترده در تعمیم نقشه استفاده می شوند [ 44 , 45 , 46 , 47]. فرآیند تنظیم رابطه جهت فضایی زیر گروه های محلی یک شبکه جاده ای بر اساس الگوریتم ژنتیک با استراتژی نخبگان (e-GA) به شرح زیر است:

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

اس=∏من=0ن-1سیمن، سیمن={0،1،2،3}

که در آن S فضای محلول را نشان می دهد، i تعداد ژن ها است، و C i یک سری آلل است که روی ژن i قرار دارند .

(2) ارزیابی سازگاری. تابع تناسب، مبنایی برای ارزیابی کیفیت نتایج است. این تابع برای حفظ رابطه جهتی فضایی مهم است. روش محاسبه در رابطه (2) نشان داده شده است. هر چه تناسب بیشتر باشد، اثر حفظ رابطه جهت فضایی بهتر است. راه حل بهینه باید حداکثر تناسب و محدودیت را برآورده کند. محدودیت است

|آمن-آمن”(j،ک)| < η1

(3) دستکاری ژنتیکی به انتخاب، متقاطع و تنوع اشاره دارد. انتخاب چرخ رولت هلند [ 48 ] عملگر انتخاب ژنتیکی کلاسیک است. در این فرآیند، هرچه افراد بهتری برای جفت گیری انتخاب شوند، احتمال به ارث بردن ژن های عالی بیشتر می شود. برای جمعیتی با عدد N , گروه = { S 0 , S 2 , …, S N − 1 }. ارزش تناسب اندام یک فرد f ( S i ) است. احتمال P i انتخاب شده است

پمن=f(اسمن)∑من=0ن-1f(اسمن)
یک عملیات متقاطع برای تبادل برخی از ژن ها بین دو فرد با احتمال مشخص برای اطمینان از استحکام جمعیت استفاده می شود. در این تحقیق از الگوریتم رولت برای انتخاب تصادفی دو نفر استفاده شد. با توجه به اندازه ژن، فرض کنید k 1 و k 2 دو نقطه متقاطع تصادفی باشند و k 1 و k 2 از 0 تا N − 1 متغیر باشند. کروموزوم ها به سه جایگاه تقسیم می شوند و دنباله ای از قطعات ژن بر اساس مبادله می شوند. احتمال متقاطع Pc ( 0 < P c< 1). فرآیند تلاقی دو فرد برای یک زیر گروه از گره های خاص در شکل 14 نشان داده شده است .
عملیات جهش تنوع جمعیت را تضمین می کند و متعلق به یک رویداد با احتمال کم است. جهش های چند نقطه ای در این مطالعه برای انتخاب افراد از انتخاب رولت و متقاطع برای تغییرات تصادفی استفاده شد. تعداد جهش ها n است (0 ≤ n ≤ N ) و هر بار جهش بر اساس احتمال جهش P m است . جهش های متعدد می توانند تفاوت های فردی را در جمعیت حفظ کنند و از همگرایی زودرس برنامه جلوگیری کنند.
(4) استراتژی نخبگان. افراد با ارزش تناسب اندام بالا در جمعیت فعلی در کتابخانه نخبگان با شماره K نگهداری می شوند . اگر ارزش تناسب اندام آنها بهتر از نسل بعدی نباشد، آنگاه افرادی که در کتابخانه نخبگان نگهداری می شوند مستقیماً به نسل بعدی کپی می شوند و تعداد متناظر از بدترین افراد در نسل بعدی جایگزین می شوند. افراد در نسل بعدی به ترتیب نزولی مطابق با ارزش تناسب اندام و K قبلی طبقه بندی می شوند.افراد با ارزش تناسب اندام بزرگ برای به روز رسانی کتابخانه حفظ نخبگان استفاده می شود. هنگامی که تکرار متوقف می شود، بهترین افراد حفظ شده به راه حل بهینه جهانی تقریب می شوند. تحت استراتژی حفظ نخبگان، الگوریتم ژنتیک می تواند به راه حل بهینه جهانی مسئله با احتمال 1 همگرا شود.
(5) قضاوت راه حل بهینه. در این مطالعه، e-GA تعیین می کند که آیا چرخه با قضاوت در مورد درجه همگرایی جمعیت، که بر اساس تغییر در ارزش تناسب اندام افراد نگهداری شده در کتابخانه نگهداری نخبگان در هر نسل است، خاتمه می یابد یا خیر. حداکثر تولید برای جلوگیری از جستجوی یک راه حل تقریبی پس از به دست آوردن راه حل از پیش پذیرفته شده تنظیم شده است. معیارهای همگرایی جمعیت به شرح زیر است:
آ. در میان K بهترین افراد در کتابخانه حفظ نخبگان، یکی با کمترین ارزش تناسب اندام بهتر از بهترین فرد در بین افرادی در نسل t بعدی است .
ب حداکثر تولید رسیده است.

برای K بهترین افراد نهایی ، افراد با کمترین تغییر فاصله به عنوان راه حل بهینه از بین افراد با حداقل تفاوت در مقادیر تناسب اندام انتخاب می شوند. محاسبه تغییر فاصله Δ D ( j ) در رابطه (9) نشان داده شده است. گره ها و رئوس مجاورت آنها در زیر گروه های محلی شبکه راه G بر اساس طرح بهینه تنظیم می شوند. در این فرآیند، طرح بهینه ممکن است باعث ایجاد خطاهای توپولوژیکی شود. با این حال، این خطاهای توپولوژیکی در نتیجه مشخص خواهند شد:

ΔD(j)=∑من=0ن-1|Dمن-Dمن”(j)|

جایی که i گره i یا راس مجاورت در G است ، j موقعیت آن است و ΔD مجموع تغییرات فاصله گره ها و رئوس مجاورت آنها در G است . D i موقعیت گره i یا راس مجاورت در G با دقت هفت رقمی و D’ i موقعیت گره i یا راس مجاورت در G با دقت پنج رقمی است.

6. نتایج تجربی و تجزیه و تحلیل

6.1. طراحی آزمایش و منطقه مطالعه

الگوریتم پیشنهادی در سی شارپ پیاده‌سازی شد و نرم‌افزار توسعه‌یافته برای آن می‌تواند نقشه شبکه جاده‌ای را با دقت پنج رقمی از یک با دقت هفت رقمی تولید کند. داده‌های هفت رقمی شبکه جاده‌ای (سیستم کمک رانندگی پیشرفته (ADAS) در قالب‌های خاص) منطقه‌ای در چونگ کینگ، چین، که توسط NavInfo Co., Ltd. (پکن، چین) ارائه شده است، که شامل 53525 جاده، 106537 نقطه پایانی است. 8619 نقطه تقاطع و 118327 راس به عنوان داده های تجربی انتخاب شدند. منطقه مورد مطالعه در شکل 15 نشان داده شده است .
با توجه به الزامات داده های شبکه جاده ای با دقت پنج رقمی، محدودیت فاصله حذف راس 2 متر بود. نرخ تراکم مربوط به تراکم نقاط در جاده های اصلی است. محدودیت فاصله ε در این آزمایش برای نمایش جزئیات ساده سازی روی 5 متر تنظیم شد. هنگام تشخیص خطوط مستقیم طولانی، پهنای باند μ نوار 0.1 متر، آستانه طول γ خط مستقیم طولانی 100 متر بود، و آستانه تغییر زاویه چرخش 5 درجه در فرآیند نگهداری شکل محلی بود. در فرآیند حفظ رابطه جهتی فضایی گره های ویژه، آستانه تغییر η1از آزیموت هر بخش جاده مرتبط با گره های ویژه روی 3 درجه تنظیم شد. پارامترها و تنظیمات آستانه الگوریتم ژنتیک در جدول 1 نشان داده شده است . در شکل 15 ، منطقه در جعبه 1 در شکل 16 نشان داده شده است ، و منطقه در جعبه 2 در شکل 17 نشان داده شده است . این مقادیر ثابت نیستند اما برای این آزمایش نسبتا معقول تلقی می شوند.

6.2. تجزیه و تحلیل نتایج

الگوریتم بهبود یافته Opheim ارائه شده در این مطالعه با الگوریتم های کلاسیک DP، Visvalingam-Whyatt (VW) و Opheim مقایسه شد. نرخ‌های فشرده‌سازی داده‌ها در چهار روش ساده‌سازی مشابه بود و مقایسه اثر ساده‌سازی را تسهیل می‌کرد. آستانه فاصله عمودی در الگوریتم DP روی 0.5 متر، در الگوریتم VW آستانه مساحت 4 متر مربع و در الگوریتم Opheim حداقل محدودیت فاصله روی 5 متر تنظیم شد. نتایج ساده شده پس از تعمیر و نگهداری در شکل 16 نشان داده شده است. از جلوه بصری خط ساده شده، فاصله بین نقاط به بهترین وجه محدودیت فاصله را برآورده می کند و تقریب خوبی از جاده اصلی نشان می دهد. در مقایسه با الگوریتم ما، الگوریتم DP نتیجه فشرده سازی بهتری را برای بخش های جاده مستقیم، طولانی و مسطح ایجاد کرد و اثر فشرده سازی جاده های منحنی ایده آل نبود. به خصوص برای جاده های منحنی با پیچ های بزرگ و نقاط متراکم، محدودیت فاصله به سختی برآورده می شد.
مناطق مشخص شده توسط خطوط نقطه چین سیاه در شکل 16 ب، نسخه ساده شده را با استفاده از DP و الگوریتم های پیشنهادی با دقت پنج رقمی نشان می دهد. تفاوت قابل توجهی در حفظ شکل جاده محلی یافت شد. نتایج نشان داد که نتیجه ساده شده الگوریتم ما بهتر از الگوریتم DP است.
نتیجه ساده شده الگوریتم VW در شکل 16 ج نشان داده شده است. چند نقطه محدودیت فاصله را برآورده نمی کند. شکل جاده با دقت پنج رقمی در مقایسه با شکل اصلی، همانطور که در کادر نقطه‌دار نشان داده شده است، بیشتر تغییر کرد، زیرا نگهداری شکل جاده نادیده گرفته شد.
الگوریتم Opheim مشابه الگوریتم فعلی است، اما تغییرات زاویه چرخش و شکل جاده را در نظر نمی گیرد. در نتیجه، شکل جاده به طور قابل توجهی پس از کاهش دقت تغییر کرد. نتیجه ساده سازی نیز به خوبی الگوریتم پیشنهادی نبود.
شکل 17 چهار نتیجه ساده شده را برای یک جاده کمربندی در منطقه 2 در شکل 15 نشان می دهد . به جز الگوریتم Opheim بهبود یافته پیشنهاد شده در این مطالعه، الگوریتم‌های DP، VW و Opheim قادر به حفظ توپولوژی فضایی مطابق با جاده اصلی نبودند. خطاهای توپولوژیکی در کادر نقطه چین در شکل 17 ارائه شده است . نتیجه الگوریتم Opheim بهبود یافته، نشان داده شده در شکل 17 الف، نشان می دهد که حذف نقطه P پس از ساده سازی، ثبات توپولوژیکی را از دست می دهد. بر این اساس، نقطه Pحفظ شد و به عنوان یک نقطه مشکل علامت گذاری شد. حذف رأس تحت دقت بالا، بدون توجه به مورفولوژی خط ورودی و مقدار تلرانس، نتایج بدون خودتقاطع را تضمین می کند. در مقابل، الگوریتم‌های DP، VW و Opheim نقاط مشخصه مهم را حذف کردند و محدودیت دقت موقعیتی را نقض کردند. شکل 17 b-d نشان می دهد که برخی از نقاط تقاطع در جاده حذف شده اند. الگوریتم Opheim بهبود یافته، نقاط تقاطع و سایر نقاط ویژگی را در حالی که محدودیت فاصله را برآورده می کند، حفظ کرد. مزیت دیگر روش پیشنهادی نشان داده شده در شکل 17 این است که می تواند نیاز فاصله فشرده سازی داده های جاده را بهتر از روش های دیگر برآورده کند که فاصله بین نقاط رزرو شده را در نظر نمی گیرند.
شکل 18 نتیجه حفظ رابطه جهتی فضایی شبکه راه مرتبط با گره های ویژه در شکل 13 با استفاده از e-GA است. این نتیجه از الگوریتم هوشمند به طور کلی بهینه است. این روش ویژگی های مورفولوژیکی و دقت جابجایی شبکه راه را حفظ می کند. در شکل 18 ، انحراف آزیموت کلی کوچکترین و شباهت بالاترین است.
برای نشان دادن بهتر عملکرد روش ما، نتایج تجربی بر اساس داده‌های چنگدو (61641 جاده)، گوانگژو (71326 جاده) و شانگهای (43571 جاده) در چین مقایسه و تجزیه و تحلیل شدند. جدول 2 مقایسه های چهار گروه آزمایش را نشان می دهد. به طور مشابه، نرخ فشرده سازی این چهار مجموعه آزمایش قابل مقایسه بود. نتایج ارزیابی فاصله Hausdorff اصلاح شده (MHD) [ 49 ] بین جاده اصلی و ساده شده در جدول 2 نشان داده شده است که درجه تشابه شکل بالاتری را با روش پیشنهادی ما نسبت به سه روش دیگر نشان می دهد. جدول 3 تغییرات زوایای آزیموت را با و بدون تنظیم رابطه جهت فضایی نشان می دهد.جدول 4 تغییرات زوایای چرخش را با و بدون تنظیم رابطه جهت مکانی توصیف می کند. روش ما کلید استخراج نقشه های شبکه راه ها با دقت پنج رقمی از نقشه های با دقت هفت رقمی بود.

7. نتیجه گیری

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

منابع

  1. لی، زی. بنیاد الگوریتمی بازنمایی فضایی چند مقیاسی . CRC Press: Boca Raton، FL، USA، 2006. [ Google Scholar ]
  2. داگلاس، دی اچ. الگوریتم های Peucker، TK برای کاهش تعداد نقاط مورد نیاز برای نمایش یک خط دیجیتالی یا کاریکاتور آن. کارتوگر. بین المللی جی. جئوگر. Inf. 1973 ، 10 ، 112-122. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  3. اوفیم، اچ. صاف کردن یک منحنی دیجیتالی با روش‌های کاهش داده. در مجموعه مقالات یوروگرافیک، مونیخ، آلمان، 9-11 سپتامبر 1981; صص 127-135. [ Google Scholar ]
  4. Opheim, H. کاهش سریع داده یک منحنی دیجیتالی. ژئو فرآیند. 1982 ، 2 ، 33-40. [ Google Scholar ]
  5. Visvalingam، M. وایات، تعمیم خط JD با حذف مکرر نقاط. کارتوگر. J. 1993 ، 30 ، 46-51. [ Google Scholar ] [ CrossRef ]
  6. Saalfeld، A. ساده سازی خط سازگار از نظر توپولوژیکی با الگوریتم داگلاس-پوکر. محاسبه کنید. Geosci. Inf. علمی 1999 ، 26 ، 7-18. [ Google Scholar ] [ CrossRef ]
  7. Pallero, J. ساده سازی خط قوی در هواپیما. محاسبه کنید. Geosci. 2013 ، 61 ، 152-159. [ Google Scholar ] [ CrossRef ]
  8. تیناه، تی. استفاناکیس، ای. کلمن، DJG Contextual Douglas-Peucker ساده سازی. Geomatica 2015 ، 69 ، 327-338. [ Google Scholar ] [ CrossRef ]
  9. چینگ شنگ، جی. براندنبرگر، سی. Hurni، L. یک الگوریتم ساده سازی خط مترقی. ژئو اسپات. Inf. علمی 2002 ، 5 ، 41-45. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  10. پارک، دبلیو. یو، ک. ساده سازی خط ترکیبی برای تعمیم نقشه برداری. تشخیص الگو Lett. 2011 ، 32 ، 1267-1273. [ Google Scholar ] [ CrossRef ]
  11. کیتس، طراحی و تولید کارتوگرافی JS ; Longman Inc.: نیویورک، نیویورک، ایالات متحده آمریکا، 1973. [ Google Scholar ]
  12. جونز، CB; Ware, M. جستجوی نزدیکترین همسایه برای اجسام خطی و چند ضلعی با مثلث های محدود. در مجموعه مقالات هشتمین سمپوزیوم بین المللی در مورد مدیریت داده های فضایی، ونکوور، پیش از میلاد، کانادا، 11-15 ژوئیه 1998. صص 13-21. [ Google Scholar ]
  13. آی، تی. گوا، آر. Liu, Y. بازنمایی درخت دودویی از ساختار منحنی H در عمق. Acta Geod. کارتوگر. گناه 2001 ، 30 ، 343-348. [ Google Scholar ]
  14. آی، تی. لیو، ی. چن، جی. تقسیم بندی سلسله مراتبی حوضه و ساده سازی داده شبکه رودخانه. در حال پیشرفت در مدیریت داده های مکانی ; Springer: برلین/هایدلبرگ، آلمان، 2006; صص 617-632. [ Google Scholar ]
  15. Ai, T. استخراج شبکه زهکشی از خطوط کانتور برای تعمیم خطوط کانتور. ISPRS J. Photogramm. Remote Sens. 2007 ، 62 ، 93-103. [ Google Scholar ] [ CrossRef ]
  16. آی، تی. ژو، Q. ژانگ، ایکس. هوانگ، ی. ژو، ام. ساده‌سازی خط ساحلی ریا با حفظ ویژگی‌های ژئومورفولوژیکی. مار. جئود. 2014 ، 37 ، 167-186. [ Google Scholar ] [ CrossRef ]
  17. آی، تی. که، اس. یانگ، م. Li, J. تولید پاکت و ساده‌سازی چند خطوط با استفاده از مثلث‌سازی Delaunay. بین المللی جی. جئوگر. Inf. علمی 2016 ، 31 ، 297-319. [ Google Scholar ] [ CrossRef ]
  18. پرکال، جی. تلاش برای تعمیم عینی. Mich. Inter.-Univ. ریاضی جامعه Geogr. بحث و گفتگو. پاپ 1966 ، 10 ، 130-142. [ Google Scholar ]
  19. لی، ز. Openshaw, S. الگوریتم‌هایی برای تعمیم خودکار خطوط بر اساس یک اصل طبیعی تعمیم عینی. بین المللی جی. جئوگر. Inf. علمی 1992 ، 6 ، 373-389. [ Google Scholar ] [ CrossRef ]
  20. شی، دبلیو. Cheung, C. ارزیابی عملکرد الگوریتم های ساده سازی خط برای تعمیم برداری. کارتوگر. J. 2006 ، 43 ، 27-44. [ Google Scholar ] [ CrossRef ]
  21. Lang, T. قوانین برای نقشه کش ربات. محاسبه کنید. Geosci. 1969 ، 42 ، 50-51. [ Google Scholar ]
  22. آرکومان، ک. Witkam، APM بهینه سازی تقسیم بندی منحنی در گرافیک کامپیوتری. در مجموعه مقالات سمپوزیوم محاسباتی بین المللی، داووس، سوئیس، 4 تا 7 سپتامبر 1973; صص 467-472. [ Google Scholar ]
  23. کراملی، ساده سازی خط محور اصلی RG. کارتوگر. J. 1992 , 18 , 1003-1011. [ Google Scholar ] [ CrossRef ]
  24. ژائو، ز. Saalfeld، A. الگوریتم‌های ساده‌سازی چند خط آستین با زمان خطی. In Proceedings of the AutoCarto 13, Seattle, WA, USA, 7-10 آوریل 1997. [ Google Scholar ]
  25. مک مستر، آر.بی. شی، تعمیم KS در کارتوگرافی دیجیتال . انجمن جغرافیدانان آمریکایی: واشنگتن، دی سی، ایالات متحده آمریکا، 1992. [ Google Scholar ]
  26. دی برگ، ام. ون کرولد، ام. Schirra, S. ساده سازی زیربخش از نظر توپولوژیکی صحیح با استفاده از معیار پهنای باند. کارتوگر. Geogr. Inf. سیستم 2013 ، 25 ، 243-257. [ Google Scholar ] [ CrossRef ]
  27. یو، جی. چن، جی. ژانگ، ایکس. چن، دبلیو. Pu, Y. یک الگوریتم بهبود یافته داگلاس-پیکر با هدف ساده سازی خط ساحلی طبیعی به خط جهت. در مجموعه مقالات بیست و یکمین کنفرانس بین المللی ژئوانفورماتیک 2013، کایفنگ، چین، 20 تا 22 ژوئن 2013. صص 1-5. [ Google Scholar ]
  28. گویال، RK; Egenhofer، MJ Similarity Assessment for Cardinal Directions between Extended Spatial Objects ; دانشگاه مین: Orono، ME، ایالات متحده آمریکا، 2000. [ Google Scholar ]
  29. گویال، RK; Egenhofer، MJ پرس و جوهای مداوم در مورد جهت های اصلی در سطوح مختلف جزئیات. در مجموعه مقالات یازدهمین کارگاه بین المللی در مورد پایگاه داده و کاربردهای سیستم های خبره، واشنگتن، دی سی، ایالات متحده، 10-13 سپتامبر 2000. صص 876-880. [ Google Scholar ]
  30. تانگ، ال. یانگ، بی. Xu، K. تشخیص تغییر داده های جاده بر اساس تشابه شکل خطی. Geomat. Inf. علمی دانشگاه ووهان 2008 ، 33 ، 367-370. [ Google Scholar ]
  31. تانگ، ال. لی، کیو. خو، اف. چانگ، ایکس. یک روش جدید برای تشخیص تغییر شکل داده های جاده. در مجموعه مقالات سمپوزیوم بین المللی تحلیل فضایی، مدل سازی داده های مکانی-زمانی و داده کاوی، ووهان، چین، 13 اکتبر 2009. پ. 749209. [ Google Scholar ]
  32. چهرقان، ع. علی عباسپور، رضا Geocarto Int. 2017 ، 32 ، 471-487. [ Google Scholar ] [ CrossRef ]
  33. یانگ، بی. یک مدل با وضوح چندگانه از داده های نقشه برداری برای انتقال سریع از طریق اینترنت. محاسبه کنید. Geoences 2005 ، 31 ، 569-578. [ Google Scholar ] [ CrossRef ]
  34. یان، اچ. ژانگ، ال. وانگ، ز. یانگ، دبلیو. لیو، تی. ژو، ال. بیان کمی تشابه فضایی در فضاهای نقشه چند مقیاسی. در مجموعه مقالات کنفرانس بین المللی کارتوگرافی، واشنگتن دی سی، ایالات متحده آمریکا، 2 تا 7 ژوئیه 2017؛ ص 405-416. [ Google Scholar ]
  35. لوئیس، جی. پارتیشن‌های نقطه‌ای Egenhofer، MJ: یک نمایش کیفی برای صحنه‌های فضایی منطقه‌محور در ℝ 2 . در مجموعه مقالات کنفرانس بین المللی علوم اطلاعات جغرافیایی، مونترال، QC، کانادا، 27-30 سپتامبر 2016. [ Google Scholar ]
  36. باتنفیلد، BP انتقال داده های مکانی بردار از طریق اینترنت. در مجموعه مقالات کنفرانس بین المللی علم اطلاعات جغرافیایی، بولدر، CO، ایالات متحده آمریکا، 25-28 سپتامبر 2002. صص 25-28. [ Google Scholar ]
  37. گوا، کیو. لیو، ی. لی، ام. چنگ، ایکس. او، جی. وانگ، اچ. Wei, Z. یک روش ساده سازی پیش رونده نقشه راه ناوبری بر اساس مدل مش. Acta Geod. کارتوگر. گناه 2019 ، 48 ، 1357–1368. [ Google Scholar ] [ CrossRef ]
  38. چای، ز. لیانگ، اس. تشخیص جامعه همپوشانی در مقیاس بزرگ مبتنی بر اولویت گره با استفاده از بهینه‌سازی چندهدفه تکاملی. تکامل. هوشمند 2020 ، 13 ، 59-68. [ Google Scholar ] [ CrossRef ]
  39. روزوال، ام. برگستروم، CT نقشه های پیاده روی تصادفی در شبکه های پیچیده ساختار جامعه را نشان می دهد. Proc. Natl. آکادمی علمی ایالات متحده آمریکا 2008 ، 105 ، 1118-1123. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  40. Fortunato، S. تشخیص جامعه در نمودارها. فیزیک 2010 ، 486 ، 75-174 . [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  41. نیومن، ME مدولاریت و ساختار جامعه در شبکه ها. Proc. Natl. آکادمی علمی ایالات متحده آمریکا 2006 ، 103 ، 8577-8582. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  42. یو، دبلیو. ژانگ، ی. آی، تی. گوان، کیو. چن، ز. لی، اچ. تعمیم شبکه جاده با در نظر گرفتن الگوهای جریان ترافیک. بین المللی جی. جئوگر. Inf. علمی 2019 . [ Google Scholar ] [ CrossRef ]
  43. دی یونگ، KA تحلیل رفتار دسته ای از سیستم های تطبیقی ​​ژنتیکی ؛ دانشگاه میشیگان: Ann Arbor، MI، ایالات متحده آمریکا، 1975. [ Google Scholar ]
  44. Zoraster, S. نتایج عملی با استفاده از بازپخت شبیه سازی شده برای قرار دادن برچسب ویژگی نقطه ای. بین المللی جی. جئوگر. Inf. علمی 1997 ، 24 ، 228-238. [ Google Scholar ] [ CrossRef ]
  45. Ware, JM; جونز، CB; توماس، ن. تعمیم خودکار نقشه با اپراتورهای متعدد: رویکرد بازپخت شبیه سازی شده. بین المللی جی. جئوگر. Inf. علمی 2003 ، 17 ، 743-769. [ Google Scholar ] [ CrossRef ]
  46. Ware, JM; ویلسون، ID; Ware, JA یک رویکرد الگوریتم ژنتیک مبتنی بر دانش برای خودکارسازی تعمیم کارتوگرافی. در برنامه های کاربردی و نوآوری در سیستم های هوشمند X ; Springer: برلین/هایدلبرگ، آلمان، 2003; صص 33-49. [ Google Scholar ]
  47. لی، ز. یان، اچ. آی، تی. چن، جی. تعمیم خودکار ساختمان بر اساس مورفولوژی شهری و نظریه گشتالت. کارتوگر. بین المللی جی. جئوگر. Inf. 2004 ، 18 ، 513-534. [ Google Scholar ] [ CrossRef ]
  48. هالند، سازگاری JH در سیستم‌های طبیعی و مصنوعی: تحلیل مقدماتی با کاربردهای زیست‌شناسی، کنترل و هوش مصنوعی . مطبوعات MIT: کمبریج، MA، ایالات متحده آمریکا، 1992. [ Google Scholar ]
  49. دوبیسون، ام. جین، AK فاصله Hausdorff اصلاح شده برای تطبیق شی. در مجموعه مقالات دوازدهمین کنفرانس بین المللی شناخت الگو، اورشلیم، اسرائیل، 9 تا 13 اکتبر 1994. صص 566-568. [ Google Scholar ]
Ijgi 09 00490 g001 550
شکل 1. جاده ها با دقت های مختلف.
Ijgi 09 00490 g002 550
شکل 2. مراحل اصلی روش ما.
Ijgi 09 00490 g003 550
شکل 3. مدل نمایشی یک شبکه راه: ( الف ) جاده و ( ب ) شبکه راه G.
Ijgi 09 00490 g004 550
شکل 4. رابطه جهتی فضایی با دقت متفاوت: ( الف ) آزیموت قطعه Vمنپمن+1در گره V i ; ( ب ) زاویه چرخش بین دو بخش متوالی جاده در راس P i .
Ijgi 09 00490 g005 550
شکل 5. حفظ رابطه جهتی فضایی جاده. بخش های جاده مرتبط با ( الف ) یک گره کلی و ( ب ) رأس.
Ijgi 09 00490 g006 550
شکل 6. نقشه برداری از یک زیر گروه محلی از شبکه جاده به کروموزوم.
Ijgi 09 00490 g007 550
شکل 7. تضاد توپولوژیکی: ( الف ) حذف راس و ( ب ) حفظ رابطه جهتی فضایی.
Ijgi 09 00490 g008 550
شکل 8. تغییرات ارتفاع در امتداد ویژگی توپوگرافی جاده.
Ijgi 09 00490 g009 550
شکل 9. استخراج یک بخش جاده طولانی، مستقیم و هموار.
Ijgi 09 00490 g010 550
شکل 10. الگوریتم Opheim برای ساده سازی چند خط.
Ijgi 09 00490 g011 550
شکل 11. حذف رأس در یک جاده منحنی. ( a ) D i , 1 < ε ; ( ب ) D i ، 1 ≥ ε ; ( ج ) D i , 1 ≥ ε و D i , 2 ≥ ε ; ( د ) D i , 1 ≥ ε و D i , 2 < ε ; ( ه ) Di , 1 ≥ ε , D i , 2 < ε و D i + 1 , 2 ≥ ε ; ( f ) D i , 1 ≥ ε , D i , 2 < ε و D i + 1 , 2 < ε ; ( g ) | T i | <= | T i + 1 | بر اساس ( e )؛ ( h) | T i | > | T i + 1 | بر اساس ( e )؛ ( من ) | T i | < θ بر اساس ( f ); ( j ) | T i | <= | T i + 1 | بر اساس ( f )؛ ( k ) | T i | > | T i + 1 | بر اساس ( f ).
Ijgi 09 00490 g012 550
شکل 12. موقعیت های اتصال یک گره عمومی: ( الف ) دو موقعیت اتصال حذف شده. ( ب ) وضعیت اتصال بهینه.
Ijgi 09 00490 g013 550
شکل 13. حفظ رابطه جهتی فضایی در گره های ویژه. خط آبی نشان دهنده جاده اصلی و خط نارنجی نشان دهنده جاده با دقت پنج رقمی است. ( الف ) داده های اصلی با دقت هفت رقمی، ( ب ) تنظیم از V 1 به V 2 ، و ( c ) تنظیم از V 2 به V 1 .
Ijgi 09 00490 g014 550
شکل 14. فرآیند تلاقی ژن.
Ijgi 09 00490 g015 550
شکل 15. داده های هفت رقمی اصلی شبکه جاده ای منطقه ای در چونگ کینگ، چین. منطقه در کادر قرمز 1 در شکل 16 و منطقه در کادر قرمز 2 در شکل 17 نشان داده شده است .
Ijgi 09 00490 g016a 550 Ijgi 09 00490 g016b 550
شکل 16. نتایج ساده شده الگوریتم های مختلف. مقایسه ( الف ) الگوریتم DP و الگوریتم بهبود یافته Opheim. ( ب ) الگوریتم VW و الگوریتم بهبود یافته Opheim. ( ج ) الگوریتم Opheim و الگوریتم بهبود یافته Opheim.
Ijgi 09 00490 g017 550
شکل 17. نتایج ساده شده الگوریتم های مختلف: ( الف ) Opheim بهبود یافته. ( ب ) DP; ( ج ) VW، و ( د ) الگوریتم های Opheim.
Ijgi 09 00490 g018 550
شکل 18. حفظ رابطه جهتی فضایی در گره های ویژه با استفاده از e-GA. خط آبی نشان دهنده جاده اصلی و خط نارنجی نشان دهنده جاده با دقت پنج رقمی است. V 1 و V 2 گره هستند.

مقالات داخلی و بین المللی

مطالب مرتبط ...

بدون دیدگاه

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