چکیده

:

با افزایش مقدار اطلاعات مکانی جمع آوری شده (2D/3D)، پردازش بلادرنگ این داده های انبوه از جمله مسائل فوری است که باید با آن برخورد کرد. گسسته سازی زمین فیزیکی به یک زمین شبکه ای دیجیتالی و اختصاص یک کد قابل محاسبه یکپارچه به هر شبکه، راهی موثر برای سرعت بخشیدن به پردازش بلادرنگ شده است. محققان الگوریتم های بهینه سازی را برای محاسبات فضایی در سناریوهای خاص پیشنهاد کرده اند. با این حال، مجموعه کاملی از الگوریتم‌ها برای پردازش بلادرنگ با استفاده از کدگذاری شبکه هنوز وجود ندارد. برای پرداختن به این موضوع، یک چارچوب عملیاتی جبری کدگذاری شبکه یکپارچه با دقت طراحی شده برای GeoSOT-3D (یک مدل شبکه چند لایه عرض و طول جغرافیایی) پیشنهاد شده است. با تبدیل محاسبات سنتی ممیز شناور بر اساس طول و عرض جغرافیایی به عملیات باینری، پیچیدگی الگوریتم تا حد زیادی کاهش می یابد. سپس الگوریتم‌های دقیقی را که طراحی شده‌اند، شامل عملیات پایه، عملیات برداری، عملیات تبدیل کد، عملیات فضایی، عملیات متریک، عملیات روابط توپولوژیکی، و عملیات مجموعه ارائه می‌کنیم. برای تأیید امکان‌سنجی و کارایی الگوریتم‌های فوق، ما یک پلتفرم آزمایشی با استفاده از زبان C++ توسعه دادیم (شامل الگوریتم‌های اصلی، و ممکن است الگوریتم‌های بیشتری در آینده گسترش یابند). سپس داده‌های تصادفی تولید کردیم و آزمایش‌هایی را انجام دادیم. نتایج تجربی نشان می دهد که چارچوب محاسباتی امکان پذیر است و می تواند کارایی پردازش فضایی را به طور قابل توجهی بهبود بخشد. انتظار می رود چارچوب عملیات جبری از بازیابی و تجزیه و تحلیل داده های جغرافیایی بزرگ پشتیبانی کند و احیایی را در بالای محاسبات موازی و توزیع شده تجربه کند.

 

1. مقدمه

با توسعه سریع توانایی های اکتشاف فضایی سه بعدی (3 بعدی) و فناوری فضایی شهری، توانایی انسان برای به دست آوردن داده های مکانی به طور قابل توجهی بهبود یافته است [ 1 ، 2 ، 3 ]. حجم داده‌های اطلاعات فضایی چندبعدی، مانند اقیانوس، محیط زیست، اکتشاف فضا، یا مدل‌سازی اطلاعات ساختمان شهری (BIM) و انواع مختلف داده‌های نقطه‌نظر (POI) به طور تصاعدی در حال رشد است [ 4 ، 5 ].]. در عصر امروزی داده‌های مکانی بزرگ، پردازش و استفاده از این اطلاعات فضایی عظیم، الزامات بالاتری را برای توانایی‌های محاسبات فضایی بلادرنگ ایجاد کرده است. با این حال، زمانی که مدل سنتی داده‌های مکانی برای محاسبه فضایی استفاده می‌شود، عمدتاً بر مبنای محاسبه ممیز شناور طول و عرض جغرافیایی است و الگوریتم پیچیده است و نیاز به بهبود دارد [ 6 ]. از آنجایی که ریاضیات انتزاعی از ذات چیزهای عینی است، انتزاع شبکه گسسته اساساً می تواند موقعیت مکانی و رابطه فضایی را منعکس کند [ 2 ، 4 ]]. به عنوان یک انتزاع گسسته از فضای جغرافیایی، گسسته سازی زمین فیزیکی به یک زمین گسسته دیجیتالی و اختصاص یک کد قابل محاسبه یکپارچه به هر شبکه، به روشی موثر برای تسریع پردازش بلادرنگ تبدیل شده است (نشان داده شده در شکل 1 ).
برای اینکه یک مدل تقسیم زمین کامل و علمی باشد، باید شامل دو بخش زیر باشد: روش تقسیم زمین و روش رمزگذاری [ 7 ، 8 ]. اولی نحوه تقسیم زمین سه بعدی را به واحدهای فرعی چند مقیاسی با اشکال مشابه و اندازه های منظم مشخص می کند. دومی عمدتاً قوانین اختصاص یک کد شناسایی منحصر به فرد به هر واحد را تعیین می کند. کد شبکه ارتباط بین فضای جغرافیایی و فضای کامپیوتر را برقرار می کند [ 9]. در همین حال، ارتباط و عملکرد کارآمد اطلاعات مکانی موجود در سیستم تقسیم بندی مستلزم آن است که قوانین عملیات جبری کد مربوطه تعریف شود. بنابراین، جبر کد یک بخش اساسی از تئوری تقسیم‌بندی جغرافیایی است، و همچنین ابزاری ضروری هنگام استفاده از نظریه تقسیم‌بندی برای حل یک سری مسائل عملی است.
مدل شبکه جغرافیایی به تدریج پذیرفته شده و به طور گسترده توسط صنعت و دانشگاه مورد مطالعه قرار گرفته است، و تبدیل به یک راه حل مهم برای سازماندهی موثر، یکپارچه سازی، اشتراک گذاری، بازیابی، توزیع و استفاده از داده های فضایی چندمنبعی عظیم [ 10 ] شده است. محققان همچنین یک مدل داده شبکه گسسته و الگوریتم‌های محاسباتی فضایی متناظر را با توجه به نیاز سناریوهای مختلف، مانند بازیابی داده‌های سنجش از دور عظیم، محاسبات ضد برخورد برای ازدحام پهپادها، برنامه‌ریزی مسیریابی برای صورت‌های فلکی ماهواره‌ای، پیش‌بینی مسیر، پیشنهاد کردند. نقاط POI در شهرها، محاسبات توانایی واکنش اضطراری برای مدیریت ایمنی شهری و غیره [ 11 ، 12 ، 13 ، 14]. بر اساس مدل شبکه، منحنی های پر کردن اغلب برای تخصیص مقادیر به شبکه استفاده می شود. یک منحنی پرکننده فضا از طریق یک منحنی با کل فضا پر می‌شود تا از داده‌های با ابعاد بالا به فضای ذخیره‌سازی با ابعاد پایین نگاشت شود. مقدار شاخص منحنی مربوط به شی فضایی را محاسبه می کند و یک شی یا یک واحد را نشان می دهد. هر منحنی پر کردن روش محاسبه خود را دارد. منحنی‌های مرتبه Z هیلبرت و کدهای Peano و Gray منحنی‌های اصلی پرکننده فضایی هستند [ 15 ، 16 ]. با این حال، مطالعات قبلی با هدف الگوریتم‌های کاربردی خاص انجام شده‌اند و فاقد سیستم‌پذیری و تطبیق‌پذیری هستند [ 17 ، 18 ، 19 ]]. بنابراین، مجموعه کاملی از الگوریتم‌هایی که از کدهای شبکه برای پردازش بلادرنگ استفاده می‌کنند، هنوز وجود ندارد، که به ما می‌گوید چگونه اطلاعات مکانی به کدهای شبکه گسسته و فرآیندهای خاص اندازه‌گیری‌های مکانی، محاسبات مکانی و تحلیل مکانی با استفاده از کدها تبدیل می‌شوند.
در میان مدل‌های شبکه سه‌بعدی پیشنهاد شده در مطالعات قبلی، یک شبکه تقسیم مختصات جغرافیایی با کدگذاری انتگرال یک‌بعدی بر روی 2 n- tree 3D (GeoSOT-3D) یک مدل داده شبکه استاندارد، چند مقیاسی، عرض و طول جغرافیایی است [ 6 ]. دارای مزایای بیان بصری شبکه طول و عرض جغرافیایی، شاخص octree موثر و محاسبه کارآمد با استفاده از کدهای شبکه [ 20 ] است. این مدل شبکه‌ای دارای 2 n شبکه در هر لایه است ( n لایه شبکه است)، و می‌تواند از مضرب‌های انتگرالی «2» برای جایگزینی محاسبات اعداد ممیز شناور بر اساس طول و عرض جغرافیایی استفاده کند (که انجام آن را برای رایانه راحت می‌کند. عملیات باینری) [ 11 ، 13, 14 , 19 ]. بنابراین، لازم است از مزایای عدد صحیح باینری کدهای GeoSOT-3D به طور کامل استفاده شود، زیرا بازده عملیات اعداد صحیح کامپیوتر بسیار بهتر از عملیات ممیز شناور است. در مطالعه ما، یک چارچوب عملیات جبری کدگذاری شبکه یکپارچه مبتنی بر عملیات بیت دودویی برای پشتیبانی از تجزیه و تحلیل داده‌های مکانی بزرگ توسعه داده شد. ما الگوریتم های اصلی را توسعه دادیم.
بقیه مقاله به صورت زیر سازماندهی شده است: در بخش 2 ، چارچوب عملیات جبری برای GeoSOT-3D پیشنهاد شده است. در بخش 3 ، عملیات جبری خاص ارائه شده است. بخش 4 بستر، نتایج و تجزیه و تحلیل را ارائه می کند. در نهایت، بخش 5 مقاله را به پایان می رساند.

2. چارچوب عملیات جبری برای GeoSOT-3D

2.1. مدل شبکه ای GeoSOT-3D

کنسرسیوم فضایی باز (OGC) استانداردهای مربوطه را برای شبکه گسسته منتشر کرده است که اولین مورد آن تعریف روش تقسیم بندی است [ 21 ]. در مطالعه ما، GeoSOT-3D به عنوان چارچوب شبکه گسسته انتخاب شده است. این با تقسیم بعد ارتفاع بر اساس شبکه تقسیم مختصات جغرافیایی با کدگذاری انتگرال یک بعدی بر روی مدل دوبعدی کروی 2 n- درخت (GeoSOT) توسعه یافته است.
مدل GeoSOT یک روش تقسیم بندی و کدگذاری است که سطح زمین را به شبکه ها تقسیم می کند [ 13 ]. از طریق تقسیم زمین سه بار (زمین را (180 درجه × 360 درجه) به 512 درجه × 512 درجه گسترش دهید، سپس هر 1 درجه به 64 دقیقه و هر 1 دقیقه به 64 اینچ منبسط شود)، تقسیم‌بندی‌های هشت درختی در درجه لایه های دقیقه و دوم به دست می آیند. GeoSOT هماهنگ و تراز است. بزرگترین شبکه تقسیم بندی در بالاترین لایه (لایه 0) می تواند کل سطح زمین را پوشش دهد، در حالی که کوچکترین شبکه تقسیم بندی در پایین ترین لایه (لایه 32) می تواند مقیاس های سانتی متری را نشان دهد.
مدل GeoSOT-3D ( شکل 2 ) یک مدل شبکه سه بعدی چند لایه است. بعد ارتفاع مدل شبکه GeoSOT را گسترش می دهد و سه بعد طول، عرض جغرافیایی و ارتفاع را به طور پیوسته از طریق تقسیم octree تقسیم می کند [ 6 ]. در نهایت مدل شبکه چندلایه درجات صحیح، دقیقه های صحیح و ثانیه های صحیح را بدست می آوریم و یک مدل سه بعدی شبکه زمینی با فضای 50000 کیلومتری تا حاشیه بیرونی زمین و پایین تا مرکز زمین تشکیل می دهیم. 32 لایه. سپس، به هر شبکه یک کد داده می شود تا به طور منحصر به فرد منطقه مکانی را شناسایی کند. کدهای موجود در همان لایه بر اساس منحنی فضای پرکننده مرتبه Z طبقه بندی می شوند [ 12]. در نهایت، اطلاعات مکانی با ابعاد بالا به کد شبکه ای یک بعدی تبدیل می شود که برای شناسایی، ذخیره سازی و محاسبه اطلاعات مکانی مناسب است.
GeoSOT-3D مبتنی بر یک کد یک بعدی باینری است و دارای یک کد تک بعدی هشت بعدی و کد سه بعدی باینری طراحی شده است که می تواند به سرعت با توجه به برنامه های کاربردی مختلف تبدیل شود:
(1)
کد هشت بعدی تک بعدی. کد با مقادیر هشتگانه (0، 1، 2، 3، 4، 5، 6، 7) تا 32 رقم کدگذاری شده است. طول کد لایه شبکه را مشخص می کند. هنگام نوشتن کد، با G شروع می شود. کدهای درجه، دقیقه و ثانیه با «-» و کدهای زیر ثانیه با «.» از هم جدا می شوند. فرم Gddddddddd-mmmmmm-ssssss.uuuuuuuuu است، جایی که d ، m ، s ، و uاعداد اکتالی با مقادیر 0، 1، 2، 3، 4، 5، 6، 7 هستند. کد هر لایه شبکه بر اساس لایه قبلی کد شبکه است و جهت رمزگذاری مرتبه Z مربوط به همان شبکه لایه ای که شبکه در آن قرار دارد. کد هشت بعدی یک بعدی عمدتاً برای ایجاد فهرست و شناسایی نام دامنه استفاده می شود.
(2)
کد یک بعدی باینری ( شکل 3 الف). کد از مقادیر باینری 96 بیتی (0،1) تشکیل شده است، و هر کد سه بیتی یک مقدار هشتگانه را نشان می دهد، بنابراین کد یک بعدی باینری دقیقاً با کد یک بعدی هشتگانه مطابقت دارد. کد باینری یک بعدی عمدتاً برای محاسبه استفاده می شود و عموماً به شکل یک ساختار ذخیره می شود. استفاده از یک کد با طول متغیر برای بیان لایه سلسله مراتبی بخش، مانند یک کد تک بعدی اکتال، غیرممکن است. بنابراین، کد یک بعدی باینری به طور کلی نیاز به افزودن یک کد لایه با طول 5 بیت برای نمایش لایه دارد و طول کل کد 96 + 5 = 101 بیت است.
(3)
کد سه بعدی باینری ( شکل 3 ب). در کد باینری 96 بیتی یک بعدی شبکه GeoSOT-3D، هر عدد باینری سه بیتی نشان دهنده کد یک شبکه در یک لایه است. این سه رقم جدا شده و به طور جداگانه ذخیره می شوند تا یک کد سه بعدی باینری GeoSOT-3D را تشکیل دهند. کد سه بعدی باینری GeoSOT-3D معنای جغرافیایی واضحی دارد و از مقادیر باینری 32 بیتی برای نشان دادن ارتفاع، عرض و طول جغرافیایی استفاده می شود. بیت اول کد بازه زمانی که شبکه در آن قرار دارد را نشان می دهد.

2.2. طراحی چارچوب عملیات جبری

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

G تمام کدهای شبکه در GeoSOT-3D (با تعداد کل 2 32∗3 ) است.
تعریف  2.

S تمام عملیات جبر کدگذاری شبکه تعریف شده در GeoSOT-3D است.
تعریف  3.

{G, S} فضای جبری کدگذاری شبکه است که گروهی است که توسط مجموعه کد شبکه و مجموعه عملیات جبری تشکیل شده است .
سپس با توجه به تابع، عملیات را دسته بندی می کنیم که شامل:
  • عملیات اساسی.
این به معنای عملیات اساسی برای خود کد است که عمدتاً پشتیبانی عملکردی برای سایر عملیات ها را فراهم می کند. عملیات اصلی فقط کد را دستکاری می کند و اطلاعات مکانی موجود در کد را شامل نمی شود. در مطالعه ما، عملیات اساسی شامل عملیات بیتی، عملیات لایه، عملیات پیشوند کد و عملیات پسوند کد است.
  • عملیات برداری
کد حاوی اطلاعات مکان شبکه است که می تواند به عنوان یک بردار در نظر گرفته شود که از مبدا فضای سه بعدی زمین به این شبکه اشاره می کند. ما عملیات برداری کد، از جمله “+” و “-” را می سازیم.
  • عملیات متریک
عملیات متریک ویژگی های واقعی جغرافیایی یک منطقه را از طریق کد محاسبه می کند، از جمله اندازه گیری مساحت، اندازه گیری فاصله، اندازه گیری منطقه طرح ریزی، و اندازه گیری جهت.
  • محاسبه فضایی
عملیات فضایی محاسبه شبکه‌های منطقه‌ای و ویژگی‌های جغرافیایی بین شبکه‌ها از طریق عملیات بیت دودویی است که عمدتاً شامل کسب کدهای همسایگی و کسب کدهای والد-فرزند است.
  • عملیات روابط توپولوژیکی
عملیات رابطه توپولوژیکی عمدتاً برای تعیین رابطه موقعیت مکانی بین شبکه ها استفاده می شود.
  • عملیات را تنظیم کنید
در کاربردهای عملی، مجموعه های شبکه اغلب برای شناسایی مکان اشیاء فضایی استفاده می شود. بنابراین، عملیات مبتنی بر مجموعه کد، از جمله ادغام مجموعه کد، تقاطع مجموعه کد، تفاوت مجموعه کد، قضاوت رابطه مجموعه کد و سایر عملیات ضروری است.
بر اساس عملیات پیشنهادی، برنامه هایی مانند پرس و جو فضایی، ارتباط خودکار فضایی و حتی GIS کدگذاری شبکه جدید را می توان توسعه داد. همانطور که مشاهده می شود مهمترین قسمت عملیات جبری است. در بخش 3 ، عملیات هر دسته را شرح می دهیم.

3. عملیات جبری

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

3.1. عملیات اساسی

عملیات پایه عمدتاً برای ارائه پشتیبانی عملیاتی اولیه از سایر عملیات استفاده می شود. فقط روی کد GeoSOT-3D عمل می کند و اطلاعات مکانی موجود در کد را شامل نمی شود. عملیات اصلی آن شامل عملیات بیتی، عملیات لایه، عملیات پیشوند کد و عملیات پسوند کد است.

3.1.1. عملیات بیتی

عملیات جبری کد GeoSOT-3D عمدتاً بر اساس عملیات بیت دودویی اساسی زیر است، از جمله &، |، ^، ~، <<، >>. قانون عملیات بیتی مانند زبان های برنامه نویسی مربوطه مانند C است.
  • به صورت بیتی و
    اپراتور:&
  • بیتی OR
    اپراتور:|
  • XOR بیتی
    اپراتور:^
  • با بیت معکوس شد
    اپراتور~
  • جابجایی به چپ
    اپراتور:<<
  • به راست تغییر دهید
    اپراتور:>>

3.1.2. لایه لایه را دریافت کنید

لایه کد عملیاتی است که برای به دست آوردن لایه کد استفاده می شود. از آنجایی که طول کد مربوط به زمان هایی است که مدل زمین تقسیم می شود، طول کد لایه کد است. به عنوان مثال، لایه کد (100101) = 6.

3.1.3. عملیات پیشوند کد

محتوای کد طول مشخص شده از ابتدای کد تقسیم شده به دست می آید و به عنوان Code Pre ثبت می شود .

کد Pre = کد >> (96 − n ); ( n ارقام پیشوند است)

3.1.4. عملیات پسوند کد

محتوای کد طول مشخص شده از انتهای کد تقسیم شده به دست می آید و به عنوان Code Last ثبت می شود .

آخرین کد = کد << (96 − n ); ( n رقم پسوند است)

3.2. عملیات بردار

کد GeoSOT-3D حاوی اطلاعات مکان شبکه است که می تواند به عنوان یک بردار در نظر گرفته شود که از مبدا فضای سه بعدی زمین به این شبکه اشاره می کند. بنابراین، کد را می توان به عنوان یک بردار در نظر گرفت. ما عملیات حسابی کد را می سازیم، از جمله “+” و “-“.
هنگامی که کد GeoSOT-3D را به عنوان یک بردار در نظر می گیریم، اولین چیزی که باید تعریف شود “+” و “-” بردار است. عملیات افزودن کد GeoSOT-3D را می توان به عنوان “+” بین دو بردار تعریف کرد، بنابراین “+” کد A و کد B ، کد ناحیه ای است که توسط بردار جدید به آن اشاره شده است، همانطور که در شکل 7 نشان داده شده است.
عملیات “-” عملیات معکوس “+” است و کدی که باید اضافه شود باید با عنصر معکوس آن جایگزین شود.
شبه کد عملیات در پیوست A پیوست شده است.

3.3. عملیات متریک

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

3.3.1. فاصله

محاسبه فاصله بین دو شبکه C 1 ( کد Lon , Code Lat , Code Hei ) و C 2 ( Code Lon , Code Lat , Code Hei ) در فضای سه بعدی زمین به شرح زیر است:

دجیهoاسOتیسی1،سی2=(اسپآn1–اسپآn2–اسپآn3)×3+(اسپآn1–اسپآn2)×2+اسپآn1×1

که در آن Span 1, Span 2, Span 3 دهانه های C 1 و C 2 به صورت سه بعدی هستند و Span 1 > Span 2 > Span را برآورده می کنند.3. روش محاسبه فاصله در اینجا نزدیک به فاصله اقلیدسی در شبکه GeoSOT-3D است. توجه به این نکته ضروری است که هنگام محاسبه فاصله یک دهانه کوچک، فاصله کروی می تواند تقریباً برابر با فاصله اقلیدسی باشد. اگر کاربران نیاز به محاسبه فاصله دقیق و بزرگ داشته باشند، باید آن را دوباره به بیضی تبدیل کنند. ما توصیه می کنیم که فاصله شبکه فقط برای نشان دادن محدوده تقریبی استفاده شود تا محدوده دقیق، برای مثال، محاسباتی مانند تخمین سریع طول.

3.3.2. منطقه طرح ریزی

طرح ریزی شبکه سه بعدی روی بیضی مرجع یک شبکه GeoSOT 2D است که می تواند با یک ذوزنقه کروی بیان شود: محدوده عرض جغرافیایی B 1 ~ B 2 و محدوده طول جغرافیایی L 1 ~ L 2 است. فرمول محاسبه مساحت هر ذوزنقه روی بیضی به شرح زیر است:

اس=2ب2ΔL[آگناه12(ب2–ب1)cosبمتر–بگناه32(ب2–ب1)cos3بمتر       +سیگناه52(ب2–ب1)cos5بمتر–Dگناه72(ب2–ب1)cos7بمتر       +Eگناه92(ب2–ب1)cos9بمتر]

که در آن A ، B ، C ، D و E ثابت هستند و می توان آنها را به صورت زیر محاسبه کرد:

ه2=(آ2–ب2)/آ2آ=1+(3/6)ه2+(30/80)ه4+(35/112)ه6+(630/2304)ه8ب=(1/6)ه2+(15/80)ه4+(21/112)ه6+(420/2304)ه8سی=(3/80)ه4+(7/112)ه6+(180/2304)ه8D=(1/112)ه6+(45/2304)ه8E=(5/2304)ه8

که در آن a محور نیمه اصلی بیضی مرجع (متر) است. b محور نیمه فرعی بیضی مرجع (متر) است. Δ L اختلاف طول جغرافیایی است (واحد: رادیان). B m = ( B 1 + B 2 )/2.

3.3.3. گرایش

رابطه جهت گیری شبکه ها به رابطه جهتی دو شبکه در فضا، مانند بالا و پایین، چپ و راست، شرق و غرب، جنوب و شمال و غیره اشاره دارد. بالا، پایین، چپ و راست مجموعه ای از نسبی هستند. روابط آزیموت، و آنها به طور کلی به صورت جفت ظاهر می شوند. برخلاف این روابط جهت گیری، شرق، غرب، شمال و جنوب دلالت بر یک جهت مرجع مطلق دارند.
شکل 8 a تعریف جهت گیری نسبی شبکه را نشان می دهد. در سیستم مختصات محلی آن، “بالا” به عنوان شمال تعریف می شود. شکل 8 ب تعریف جهت گیری مطلق شبکه را نشان می دهد. تفاوت بالا، پایین، چپ و راست این است که شرق، غرب، جنوب و شمال دلالت بر جهت مرجع مطلق دارند. رابطه جهت گیری فضایی شبکه را می توان از طریق مقایسه کدگذاری در سه بعدی به دست آورد. هر دو شبکه انتخاب شده است، C 1 ( CodeE 1 , CodeB 1 , CodeL 1 )، C 2 ( CodeE 2 , CodeB 2 , CodeL2 )، که در آن C 1 شبکه مرجع، C 2 شبکه اشاره گر است، و رابطه جهت گیری فضایی شبکه مانند شکل 9 محاسبه شده است .

3.4. محاسبه فضایی

عملیات فضایی به محاسبه شبکه‌های منطقه‌ای و ویژگی‌های جغرافیایی بین شبکه‌ها از طریق عملیات بیتی اشاره دارد که عمدتاً شامل کسب کدهای همسایگی و کسب کدهای والد-فرزند است.

3.4.1. عملیات محله

عملیات همسایگی کد شبکه مجاور منطقه را به دست می آورد ( شکل 10 a). برای چارچوب زیربخش GeoSOT، رابطه همسایگی بین یک منطقه و منطقه اطراف به همسایه سطح، همسایه لبه و همسایه گوشه تقسیم می‌شود. به طور خلاصه، با شروع از منطقه داده شده، یک شبکه در امتداد جهت طول / عرض / ارتفاع حرکت می کند تا مجموعه کد محله به دست آید.
محاسبه همسایگی شبکه بر اساس کد سه بعدی باینری است (کدهای دیگر را می توان ابتدا به کدگذاری سه بعدی باینری تبدیل کرد) و سپس محاسبه همسایگی انجام می شود. برای شبکه‌ای که به‌عنوان ( کد Lon ، Code Lat ، Code Hei ) کدگذاری شده است، یک ترکیب جابجایی از کد آن در بعد ارتفاع، بعد طول جغرافیایی و بعد عرض جغرافیایی نشان‌دهنده شبکه همسایگی خاصی از شبکه است. برای یک کد بعد معین در کد سه بعدی باینری، جابجایی کد را می توان به صورت زیر انجام داد:
(1)
یک شبکه را به جلو حرکت دهید:

سیoدهنهw=سیoده+1<<(32–سیoدهLآyهr)
(2)
یک شبکه را در جهت منفی حرکت دهید:

سیoدهنهw=سیoده–1<<(32–سیoدهLآyهr)

3.4.2. عملیات شبکه مادر

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

جیپ(سیoده)=جیپrه(سیoده،سیoدهLآyهr–1) 1≤سیoدهLآyهr≤32

که در آن G P عملیات محاسبه کد شبکه اصلی است. ورودی محاسبه کد شبکه است. خروجی کد شبکه اصلی شبکه است.

3.4.3. عملیات شبکه کودک

به همین ترتیب، پس از ارث بردن مدل شبکه، کد شبکه فرزند می تواند با کد والد و کد شبکه فرزند در شبکه والد ترکیب شود. فرمول محاسبه به صورت زیر نشان داده شده است:

جیاس(سیoده)={سیoده+‘0‘،سیoده+‘1‘…..سیoده+‘7‘} 0≤سیoدهLآyهr≤31

که در آن G S عملیات محاسبه کد شبکه اصلی است. ورودی محاسبه کد شبکه است. خروجی کد شبکه اصلی شبکه است.

3.5. محاسبه روابط توپولوژیکی

عملیات رابطه توپولوژیکی عمدتاً برای تعیین رابطه موقعیت مکانی بین شبکه ها استفاده می شود. رابطه توپولوژیکی بین موجودات را می توان با یک مدل نه تقاطع توصیف کرد [ 22 ، 23 ]. در مدل نه تقاطع برای GeoSOT، ما A 0 را به عنوان شبکه هایی با فاصله 1 در نمودار Voronoi تعریف می کنیم ( شکل 11 ).
هیچ راهی برای “تقاطع” یک سلول شبکه با دیگری وجود ندارد، زیرا دو سلول شبکه نمی توانند در یک شبکه همپوشانی داشته باشند، آنها فقط می توانند همسایه باشند (که توسط رابطه لمس پوشش داده می شود). فقط یک رابطه مهار ممکن است بین شبکه های لایه های مختلف وجود داشته باشد ( شکل 12 a). بنابراین، می توانیم شش رابطه را به دست آوریم: حاوی(T*****FF*)، پوشش(T*****FF*،*T****FF*،***T**FF*،* ***T*FF*)، تحت پوشش (T*F**F***،*TF**F***،**FT*F***،**F*TF***)، گسست (FF*FF****،)، برابر (T*F*FFF*)، و لمس (FT********، F**T****، F***T* ***). سپس، با تمایز لبه‌های مجاور و گوشه‌های مجاور، این را به هشت رابطه توپولوژیکی گسترش می‌دهیم ( شکل 12 ).

اسآر9=∂آ∩∂ب∂آ∩ب0∂آ∩ب–1آ0∩∂بآ0∩ب0آ0∩ب–1آ–1∩∂بآ–1∩ب0آ–1∩ب–1
در روش ما، ما رابطه توپولوژیکی را با قضاوت در مورد بزرگی کدها محاسبه می کنیم. ابتدا، رابطه توپولوژیکی بین شبکه ها به صورت سه بعدی محاسبه می شود. سپس رابطه توپولوژیکی دو بعدی و رابطه توپولوژیکی با ابعاد بالا محاسبه شده و در نهایت رابطه توپولوژیکی فضایی شبکه ها به دست می آید.
C A و C B به ترتیب کدهای باینری شبکه A و B در بعد D هستند و طول کد L A , L B است. فرآیند محاسبه رابطه توپولوژیکی بین شبکه A و شبکه B در بعد D به شرح زیر است.
برای لایه کد یکسان ( L A = L B )، قضاوت می شود که آیا C A = C B ، به این معنی که رابطه توپولوژیکی RD شبکه A و B در بعد D برابر است. در غیر این صورت، فاصله شبکه واقعی بین L A و L B محاسبه می شود. اگر دهانه 1 باشد، R D مجاور است. اگر دهانه بزرگتر از 1 باشد، R D از هم گسسته است.
برای لایه‌های کد مختلف، بدون از دست دادن کلیت، فرض می‌شود که L A > L B و پیشوند C A ‘ که طول C A آن L B است گرفته می‌شود. اگر C A = C B باشد، B شامل A است. اگر C A ‘ > C B , L A -L B بعد از C B اضافه شود و سپس رابطه توپولوژیکی طبق کد همان لایه محاسبه می شود. اگر سیA ′ < C B , L A – L B 0s بعد از C B اضافه می شود و سپس رابطه توپولوژیکی طبق کد همان لایه محاسبه می شود. با توجه به روش پیشنهادی، روابط توپولوژیکی R E ، RB و RL شبکه A و شبکه B در سه بعد را می توان در نهایت محاسبه کرد.

3.6. تنظیم عملیات

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

4. نتایج تجربی

4.1. پلت فرم آزمایشی و طراحی آزمایش

بر اساس چارچوبی که پیشنهاد کردیم، یک پلتفرم آزمایشی را با استفاده از C++ توسعه دادیم. در این پلت فرم آزمایشی، می‌توانیم شبکه را از طریق محدوده لایه و مساحت داده شده تجسم کنیم و بر اساس آن اندازه‌گیری و تحلیل فضایی مربوطه را انجام دهیم (الگوریتم‌های اصلی در پیوست A نشان داده شده‌اند ). حافظه مورد نیاز برای استفاده از پلتفرم ما 8 گیگابایت است. شکل 14 تقسیم کره را با انتخاب ناحیه فضایی زیر یک لایه مشخص نشان می دهد. از این میان، زیربخش های زیرزمینی و زیرزمینی همگی به عنوان لایه فرعی نهم انتخاب شده اند و محدوده طول و عرض جغرافیایی 120 درجه شرقی تا 150 درجه شرقی، 20 درجه شمالی تا 50 درجه شمالی است.
سپس، داده‌های شبیه‌سازی شده تصادفی را تولید کردیم و آزمایش‌های عملیات متریک و محاسبه روابط توپولوژیکی خود را انجام دادیم و سپس کارایی عملیات جبری را تحلیل کردیم. این کار امکان‌سنجی و کارایی چارچوب عملیات جبری کدگذاری شبکه یکپارچه را تأیید می‌کند.
محیط آزمایشی: Win7 Ultimate 64 بیتی، Intel Core i5-2400 @ 3.10 گیگاهرتز، رم 8 گیگابایت، هارد دیسک 512 گیگابایت، ویژوال استودیو 2010.

4.2. مقایسه کارایی عملیات برداری

منحنی پرکننده فضا هیلبرت یک منحنی پرکننده فضا پیوسته و فراکتال است ( شکل 15 ). کلید هیلبرت منحنی اساسی و چرخش سیستم مختصات است. مطالعات نشان داده اند که در میان بسیاری از منحنی های پرکننده فضا، منحنی هیلبرت بهترین تجمیع داده ها را دارد [ 24 ]. بنابراین منحنی هیلبرت بیشتر در نمایه سازی فضایی استفاده می شود.
ما کارایی محاسبه منحنی هیلبرت و منحنی مرتبه Z را با محاسبه جابجایی پایه در فضای دو بعدی مقایسه کردیم و میانگین زمان را به عنوان استاندارد طلایی تعیین کردیم. برای منحنی هیلبرت، از آنجایی که سیستم مختصات دائماً در حال چرخش است، قبل از اینکه بتوانیم کد شبکه را پس از جابجایی محاسبه کنیم، باید (x, y) آن را تعیین کنیم. ما به طور تصادفی 300000 کد شبکه تولید کردیم و کدهای شبکه را در سمت شرقی آنها محاسبه کردیم. میز 1میانگین زمان صرف شده برای تبدیل کد منحنی هیلبرت به (x,y) 180 میلی‌ثانیه است. در شرایط یکسان، تنها 11 میلی ثانیه طول می کشد تا محاسبه جابجایی تحت ترتیب Z تکمیل شود. ما معتقدیم که مرتبه z خصوصیات مختصات فضایی را تا حد بیشتری نسبت به منحنی هیلبرت حفظ می کند و برای محاسبات فضایی مناسب تر است. با این حال، برای محاسبات فضایی، منحنی هیلبرت نمی تواند محاسبات کارآمد را انجام دهد. بنابراین، ما در حال انجام تحقیقاتی در مورد محاسبات فضایی بر اساس Z-order هستیم.

4.3. مقایسه بازده عملیات متریک

در ابتدا، ما عملیات متریک شبکه (الگوریتم در بخش 3.3 ) را با اندازه‌گیری‌های هندسی عرض، طول و ارتفاع (LLH) سیستم مختصات (شامل فاصله و جهت) مقایسه کردیم. ما همچنین میانگین زمان را به عنوان استاندارد طلایی تعیین کردیم.

دEتوجلمندهآnسی1،سی2=(آرآرکوس(cos(Lآتیآ)cos(Lآتیب)cos(Lonب–Lonآ)+گناه(Lآتیآ)گناه(Lآتیب)))2+(اچب–اچآ)2φ=آرکسین(cos(Lonب)∗گناه(Lآتیب–Lآتیآ)گناهج)،cosج=گناه(Lonب)گناه(Lonآ)+cos(Lonب)cos(Lonآ)∗cos(Lآتیب–Lآتیآ)θ=آرکتان(اچب–اچآدEتوجلمندهآn)
ما به طور تصادفی 1،000،000 موجودیت نقطه در سراسر جهان تولید کردیم، کد 1 تا 32 لایه GeoSOT-3D هر نقطه را محاسبه کردیم و سپس عملیات زیر را انجام دادیم:
مرحله 1.1: برای هر دو نقطه، فاصله اقلیدسی بین آنها محاسبه می شود و میانگین زمان محاسبه ثبت می شود.
مرحله 1.2: برای هر دو نقطه (همانند مرحله 1.1)، کدهای مربوط به آنها (از لایه 1 تا لایه 32) برای محاسبه فاصله شبکه بین شبکه ها استفاده می شود (الگوریتم در بخش 3.3.1 )، و زمان محاسبه ثبت می شود. .
مرحله 2.1: برای هر دو نقطه، جهت گیری فضایی بین آنها محاسبه می شود و زمان محاسبه ثبت می شود.
مرحله 2.2: برای هر دو نقطه (همان مرحله 2.1)، کدهای مربوط به آنها (از لایه 1 تا لایه 32) برای محاسبه جهت گیری بین شبکه ها استفاده می شود (الگوریتم در بخش 3.3.3 )، و زمان محاسبه ثبت می شود.
شکل 16 میانگین زمان صرف شده برای اندازه گیری فاصله مکانی را نشان می دهد. کارایی عملیات جبری کدگذاری شبکه بسیار بهتر از سیستم مختصات طول، طول و ارتفاع است. میانگین زمان صرف شده با استفاده از LLH حدود 0.5 میکرو ثانیه است، در حالی که زمان محاسبه شبکه در 0.07 میکروثانیه پایدار است. دلیل اصلی این امر این است که فاصله محاسبه طول و عرض جغرافیایی نیاز به تبدیل مختصات قطبی و محاسبه مربع دارد. عملیات شبکه از تعداد زیادی توابع مثلثاتی و عملیات ریشه مربع اجتناب می کند.
شکل 17 میانگین زمان صرف شده برای محاسبه جهت مکانی را نشان می دهد. میانگین زمان استفاده شده برای محاسبه جهت مکانی بین دو نقطه با استفاده از طول و عرض جغرافیایی 0.6 میکروثانیه طول می کشد و عملیات جبری کدگذاری شبکه حدود 0.1 میکرو ثانیه است. دومی از حساب بیتی برای محاسبه جهت مکانی استفاده می کند، بنابراین کارآمدتر است. به طور مشابه، عملیات جبری یک رابطه جهت گیری کیفی بین دو شبکه فراهم می کند که برای سناریوهای کاربردی که نیاز به یک رابطه جهت گیری خشن دارند مناسب است.

4.4. مقایسه بازده عملیات توپولوژیکی

تحلیل همپوشانی یکی از مهمترین محاسبات روابط توپولوژیکی است. در حال حاضر گرافیک کامپیوتری تقریبا در تمامی زمینه ها از جمله بازی، سرگرمی، آموزش، CAD/CAM و … استفاده می شود که یکی از عملیات های بسیار مهم در گرافیک کامپیوتری Overlay است. تحلیل همپوشانی را می توان برای VLSI CAD، GIS، صنعت پوشاک و غیره اعمال کرد. الگوریتم های زیادی وجود دارد، اما محاسبه تقاطع هزینه های زیادی را به همراه خواهد داشت. در این آزمایش، ما عملیات همپوشانی شبکه (الگوریتم در بخش 3.5 ) را با تحلیل همپوشانی سیستم مختصات طول، طول و ارتفاع (LLH) مقایسه کردیم.
فرآیند پوشش نیاز به دو یا چند لایه دارد. لایه‌های مورد استفاده در این آزمایش به دو نوع تقسیم می‌شوند: یکی لایه‌ای است که فقط یک شی منطقه دارد ( شکل 18 a,b و جدول 2 ) و دیگری لایه‌ای با اشیاء چند منطقه است ( شکل 19 و جدول 3 ).
ما از شبکه های چندلایه برای نمایش یک شی جغرافیایی استفاده می کنیم. برای یک موجود جغرافیایی، به داده‌های شبکه مرزی و یک نقطه داخلی نیاز داریم و سپس از الگوریتم پر کردن دانه برای محاسبه مجموعه شبکه مربوطه آن استفاده می‌کنیم. در نهایت، شبکه‌ها را مطابق با قانون تقسیم هشت درخت شبکه‌ای که در شکل 18 الف نشان داده شده است، جمع می‌کنیم.
این آزمایش به دو بخش تقسیم شده است، پوشش لایه تنها با یک شی منطقه و پوشش لایه با اشیاء چند منطقه، برای تجزیه و تحلیل تأثیر تعداد اشیاء. در همین حال، ما از الگوریتم برش ویلر-آترتون استفاده کردیم (وایلر-آترتون یک الگوریتم کلاسیک برش چند ضلعی بر اساس سیستم طول و عرض جغرافیایی است، و پیچیدگی الگوریتم با پیچیدگی هندسی عناصر و تعداد تقاطع های چند ضلعی همبستگی مثبت دارد [ 25 ]). ) برای انجام تحلیل همپوشانی. در نهایت، نتایج را با کارایی محاسباتی عملیات جبری مقایسه کردیم ( جدول 2 و جدول 3 ).
بر اساس نتایج به دست آمده می توان به دو نکته زیر اشاره کرد:
(1)
برای محاسبه همپوشانی لایه‌های حاوی یک شی منطقه واحد، بازده عملیات جبری کمی بالاتر از الگوریتم Weiler-Atherton است. در شرایط آزمایشی در این مقاله، بازده عملیات جبری حدود 1.32 برابر افزایش یافته است. برای محاسبه همپوشانی دو جسم سطحی، وقت گیرترین بخش الگوریتم همپوشانی در قضاوت رابطه تودرتو بین دو مجموعه شبکه نهفته است. این عملیات ابتدایی ترین نوع عملیات بیت است. این به تعداد شبکه های تحت پوشش هر شی منطقه مربوط می شود. در مقایسه، بیشترین مصرف زمان الگوریتم ویلر-آترتون در قضاوت تقاطع بین دو جسم نهفته است. تعداد قضاوت ها به تعداد پاره های خطی که دو جسم سطحی را بیان می کنند، مربوط می شود:
(2)
برای محاسبه همپوشانی لایه‌های حاوی اشیاء مساحت چندگانه، بازده عملیات جبری بسیار بالاتر از الگوریتم ویلر-آترتون است. در شرایط آزمایشی این مقاله، بازده عملیات جبری حدود 6.44 برابر بهبود یافته است. برای محاسبه همپوشانی بین دو مجموعه شی مساحت، مصرف زمان عملیات جبری به اندازه منطقه پوشش کلی مجموعه شبکه و دقت داده مربوط می شود. با تعداد کل شبکه های مرتبط مرتبط است. همبستگی ضعیفی با تعداد اشیاء درگیر در محاسبه دارد. با این حال، زمان مصرف شده توسط الگوریتم Weiler-Atherton به تعداد اشیاء در محاسبه مرجع مرتبط است. هر چه اشیاء بیشتر باشد،

4.5. تحلیل کارایی عملیات جبری

ما با مسئله تلاقی خطوط و خطوط در فضای سه بعدی و تلاقی موجودیت ها شروع می کنیم و عملیات جبری را با روش قضاوت رابطه فضایی تحت سیستم سنتی عرض، طول و ارتفاع (LLH) مقایسه می کنیم تا برتری را نشان دهیم. روش ما در رابطه با رابطه فضایی.
ما محاسبه تقاطع منحنی های فضای سه بعدی را به عنوان مثال برای تجزیه و تحلیل محاسبه با فرض الگوریتم تقاطع خط-خط فضای سه بعدی در نظر می گیریم ( شکل 20 ). منحنی ها در فضای سه بعدی به طور گسترده ای وجود دارند، مانند مسیر پرواز یک موشک. دو منحنی در فضای سه بعدی به صورت زیر تعریف می شوند:

خط 1: اف1ایکس،y،z=0اف2ایکس،y،z=0خط 2: جی1ایکس،y،z=0جی2ایکس،y،z=0
اگر دو منحنی باید فوکوس داشته باشند، چهار معادله منحنی 1 و منحنی 2 باید به طور همزمان حل شوند. اگر منحنی 1 و منحنی 2 به ساده ترین خط مستقیم منحرف شوند، حل نقطه کانونی نسبتا آسان است. سپس برای معادلات مربوط به سطوح درجه بالاتر، فرآیند حل آنها پیچیدگی بیشتری خواهد داشت. در کاربردهای عملی، الزامات تشخیص برخورد پیچیده‌تر از یافتن تقاطع منحنی‌ها است. دلیل این امر این است که برای تشخیص برخورد در مسیر، نه تنها باید در نظر گرفت که آیا منحنی مسیر دارای یک تقاطع است، بلکه همچنین باید در نظر داشت که آیا در شعاع مشخصی از فضای اطراف دو مسیر تقاطع وجود خواهد داشت یا خیر. از این رو،
این مشکل را می توان به مسئله بهینه سازی تابع هدف بر اساس محدودیت های برابری نسبت داد. شرط محدودیت معادله بیان دو منحنی است و هدف بهینه سازی فاصله بین دو نقطه است. برای حل حداقل فاصله، روشی که در عمل استفاده می شود، روش ضریب لاگرانژ (ضریب لاگرانژ) است. یعنی قید معادله به صورت فرمولی با ضریب و تابع هدف نوشته می شود که به آن تابع لاگرانژی و ضریب آن را ضریب لاگرانژی می گویند. تابع لاگرانژی برای استخراج هر متغیر و صفر قرار دادن آن برای به دست آوردن مجموعه ای از مقادیر کاندید استفاده می شود و سپس تأیید می کند که مقدار بهینه به دست آمده است.
از طریق تجزیه و تحلیل فوق، می توان دریافت که الگوریتم محاسبه روابط فضایی سه بعدی سنتی پیچیده است. با این حال، تحت چارچوب ما، محاسبات فضایی پیچیده فوق را می توان به محاسبات فضایی سه بعدی موجودیت های فضایی تبدیل کرد، که سپس با استفاده از عملیات جبری قابل تحقق است. این روش بر اساس ماهیت چند مقیاسی کد است. با پشتیبانی از عملیات جبری می توان محل تلاقی خطوط داخلی در فضا را تشخیص داد و موقعیت یابی درشت را انجام داد. سپس، عملیات جبری هیچ ربطی به شکل هندسی موجودیت فضا (خط) و تعداد موجودات فضایی ندارد. الگوریتم قضاوت موجودیت های چند خط فضایی مانند الگوریتم عمل تقاطع دو موجودیت خط فضایی است. از این رو،O ( nlogn )، که در آن n تعداد عناصر در مجموعه شبکه است و الگوریتم پایداری بالایی دارد.

5. نتیجه گیری ها

با افزایش مقدار اطلاعات مکانی جمع آوری شده (2D/3D)، پردازش بلادرنگ این داده های عظیم یکی از مسائل فوری است که نیاز به پاسخ دارد. گسسته سازی زمین فیزیکی به یک زمین شبکه بندی شده دیجیتال و اختصاص یک کد قابل محاسبه یکپارچه به هر شبکه، راهی موثر برای سرعت بخشیدن به پردازش بلادرنگ شده است. بر اساس مدل شبکه GeoSOT-3D، ما یک چارچوب عملیات جبری کدگذاری شبکه یکپارچه برای GeoSOT-3D ایجاد کردیم. با تبدیل محاسبات سنتی ممیز شناور مبتنی بر طول و عرض جغرافیایی به عملیات باینری، پیچیدگی الگوریتم تا حد زیادی کاهش می یابد. سپس، عملیات های مختلف در چارچوب مورد بحث قرار گرفت، از جمله عملیات پایه، عملیات برداری، عملیات تبدیل کد، عملیات فضایی، عملیات متریک و عملیات روابط توپولوژیکی. برای تأیید امکان‌سنجی و کارایی الگوریتم‌های فوق، ما یک پلتفرم آزمایشی با استفاده از زبان C++ توسعه دادیم (شامل الگوریتم‌های اصلی، و ممکن است در آینده الگوریتم‌های بیشتری بسط داده شوند). سپس داده‌های تصادفی تولید کردیم و آزمایش‌هایی را انجام دادیم. آزمایش ها ثابت کردند که این بهتر از محاسبات در سیستم عرض، طول و ارتفاع است که روش محاسبه مستقیم تری را برای مدل GeoSOT-3D ارائه می دهد.
با این حال، هنوز محدودیت هایی وجود دارد. به عنوان مثال، اگر دانه بندی فضایی خیلی خوب باشد، رمزگذاری یک منبع ذخیره بزرگ را اشغال می کند و طراحی فشرده سازی رمزگذاری باید انجام شود. مورد خاصی که در آن کدها در نقطه عطف منحنی پرکننده (در لبه شبکه مجاور) با فاصله بسیار دور از هم مرتب شده اند، باید بیشتر مورد بحث قرار گیرد. در آینده، ما به بهبود روش خود برای الگوریتم‌ها و برنامه‌ها، با استفاده از تولید نمودار Voronoi، تجزیه و تحلیل بافر، اتوماتای ​​سلولی و غیره ادامه خواهیم داد. انتظار می‌رود چارچوب عملیات جبری از بازیابی و تجزیه و تحلیل داده‌های جغرافیایی بزرگ پشتیبانی کند و احیا را تجربه کند. رایانش محاسبات موازی و توزیع شده در عصر داده های بزرگ مکانی

مشارکت های نویسنده

مفهوم سازی، کایهوا هو و شوانگ لی. روش، کایهوا هو و شوانگ لی. نرم افزار Kaihua Hou و Chi Zhang. اعتبارسنجی، کایهوا هو، شوانگ لی و بو چن. تحلیل رسمی، شوانگ لی; تحقیق، Shuang Li و Liesong He; نوشتن – آماده سازی پیش نویس اصلی، Kaihua Hou; نوشتن-بررسی و ویرایش، شوانگ لی و لی منگ. تجسم، Kaihua Hou; نظارت، چنگچی چنگ; مدیریت پروژه، چنگچی چنگ و بو چن. Chengqi Cheng همه نویسندگان نسخه منتشر شده نسخه خطی را خوانده و با آن موافقت کرده اند.

منابع مالی

این مطالعه توسط طرح ملی تحقیق و توسعه کلیدی (Grant No. 2018YFB0505300) و بنیاد ملی علوم طبیعی چین (شماره 42001184) تأمین مالی شد.

بیانیه هیئت بررسی نهادی

قابل اجرا نیست.

بیانیه رضایت آگاهانه

قابل اجرا نیست.

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

الگوریتم های ارائه شده در این مطالعه به درخواست نویسنده مربوطه در دسترس هستند.

تضاد علاقه

نویسندگان هیچ تضاد منافع را اعلام نمی کنند.

پیوست اول

1. رمزگشایی منحنی هیلبرت در مقابل کد جابجایی مرتبه Z

پوسیدگی خالی (int n ، int* x، int* y، int rx، int ry){
   اگر (ry == 0){
      اگر (rx == 1){
         *x = n − 1 − *x;
         *y = n − 1 − *y;
      }
      int t = *x;
      *x = *y;
      *y = t;
   }
}
 void d2xy (int n، int d، int* x، int* y){
    int rx، ry، s، t = d;
    *x = *y = 0;
    برای (s = 1; s < n ; s *= 2){
      rx = 1 & (t / 2)؛
      ry = 1 & (t ^ rx);
      rot (s، x، y، rx، ry)؛
      *x += s * rx;
      *y += s * ry;
      t /= 4;
    }
 }
 unsigned int moveR(int n , کد بدون امضا) {
    اگر (کد % 2 == 0)
       بازگشت (کد + 1)؛
    n – = 2;
    برای (int i = 4; i < n ; i = i * 4) {
       اگر ((کد و i) == 0)
          کد بازگشت & n |i;
       n −= i;
    }
    بازگشت 0;
 }
2. کد شبه تابع را رمزگذاری کنید

تابع 2: رمزگذاری:
ورودی: طول جغرافیایی، عرض جغرافیایی، ارتفاع،
خروجی لایه: کد GeoSOT-3D
1: ساخت سیoده{     بدون امضا بین المللی درجه:10;     بدون امضا بین المللی دقیقه:6;     بدون امضا بین المللی دومین:16;   }; 2: سیoدهLon←Longمنتیتودهدهgrهه،مترمنnتوتیه،سهجonد 3: سیoدهLآتی←Lآتیمنتیتودهدهgrهه،مترمنnتوتیه،سهجonد 4: سیoدهاچهمن←اچهمنgساعتتی 5: سیoدهمن>>(32–لآyهr)<<(32–لآyهr) 6: for j=0 تیo لآyهr 7:  جیهoاسOتی–3D سیoده←سیoدهمن[j] 8: هnد for
3. رمزگشایی تابع شبه کد:

تابع 3: رمزگشایی:
ورودی: خروجی کد GeoSOT-3D
: طول جغرافیایی، عرض جغرافیایی، ارتفاع، لایه    1: [سیoدهلon،سیoدهLآتی،سیoدهاچهمن]←جیهoاسOتی سیoده   2: Lآتیمنتیتودهدهgrهه،مترمنnتوتیه،سهجonد←سیoدهLآتی   3: Longمنتیتودهدهgrهه،مترمنnتوتیه،سهجonد←سیoدهLon   4: اچهمنgساعتتی←سیoدهاچهمن
4. وکتور +

تابع 4: بردار +
ورودی: GeoSOT-3D Code1، GeoSOT-3D Code2
خروجی: GeoSOT-3D Code
//دو دودویی شماره“ بیت ها هستند برابر به کد   1: جیهoاسOتی–3D سیoده=(سیoده1|0ب101010…10+سیoده2)&0ب010101…01

منابع

  1. چن، اس. تجزیه و تحلیل ژئو فضایی/زمانی در پردازش جغرافیایی. J. Remote Sens. 1997 ، 161-171. [ Google Scholar ] [ CrossRef ]
  2. آهنگ، JC; ژائو، CL; ژونگ، اس پی؛ نیلسن، TAS؛ پریشچپوف، AV نقشه برداری الگوهای مکانی-زمانی و شناسایی عوامل تراکم ترافیک با تکنیک های ترکیب داده ها و استخراج چند منبع. محاسبه کنید. محیط زیست سیستم شهری 2019 , 77 . [ Google Scholar ] [ CrossRef ]
  3. Xiong، X. کیائو، اس جی. Li، YY; هان، ن. یوان، جی. Zhang، YQ یک الگوریتم پیشنهاد نقطه‌ی علاقه در شبکه‌های جغرافیایی-اجتماعی چند منبعی. مهندس Appl. آرتیف. هوشمند 2020 , 88 . [ Google Scholar ] [ CrossRef ]
  4. لین، ی. وانگ، اچ. ژانگ، اس. لی، جی. Gao, H. انتخاب منبع مبتنی بر کیفیت کارآمد از منابع داده عظیم. جی. سیست. نرم افزار 2016 ، 118 ، 221-233. [ Google Scholar ] [ CrossRef ]
  5. آهنگ ها.؛ چنگ، سی. پو، جی. آن، اف. Luo, X. سازمان زیربخش داده های سنجش از دور جهانی بر اساس GeoSOT. Acta Geod. کارتوگر. گناه 2014 ، 43 ، 869-876. [ Google Scholar ]
  6. چنگ، سی. تانگ، ایکس. چن، بی. Zhai, W. یک روش تقسیم بندی برای یکسان سازی شبکه های عرض و طول جغرافیایی موجود. ISPRS Int. J. Geo-Inf. 2016 ، 5 ، 161. [ Google Scholar ] [ CrossRef ]
  7. وانگ، آر. بن، جی. دو، ال. ژو، جی. Li, Z. رمزگذاری و عملیات برای سیستم شبکه شش گوشه با دیافراگم مسطح. Acta Geod. کارتوگر. گناه 2018 ، 47 ، 1018–1025. [ Google Scholar ]
  8. Xiaochong، T. جین، بن؛ Zhiyuan، QIN; Yongsheng، Z. زیربخش شبکه جزئی بر اساس سیستم های شبکه جهانی گسسته. Acta Geod. کارتوگر. گناه 2009 ، 38 ، 506-513. [ Google Scholar ]
  9. Xiaochong، T. جین، بن؛ Yongsheng، Z. زیربخش شبکه شش ضلعی با وضوح چندگانه جهانی و قوانین کدگذاری آدرس. Acta Geod. کارتوگر. گناه 2007 ، 36 ، 428-435. [ Google Scholar ]
  10. Goodchild، MF; Shiren, Y. ساختار داده های مکانی سلسله مراتبی برای سیستم های اطلاعات جغرافیایی جهانی. نمودار CVGIP. فرآیند تصویر مدل ها 1992 ، 54 ، 31-44. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  11. لی، اس. چنگ، سی. Pu, G. QRA-Grid: تحلیل کمی ریسک و مدل پیش هشدار مبتنی بر شبکه برای خط لوله گاز طبیعی شهری. ISPRS Int. J. Geo-Inf. 2019 ، 8 ، 122. [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
  12. لی، اس. هو، ک. چنگ، سی. لی، اس. Chen, B. A Space-Interconnection الگوریتم برای صورت فلکی ماهواره بر اساس مدل شبکه فضایی. Remote Sens. 2020 , 12 , 2131. [ Google Scholar ] [ CrossRef ]
  13. میائو، اس. چنگ، سی. ژای، دبلیو. رن، اف. ژانگ، بی. لی، اس. ژانگ، جی. ژانگ، اچ. الگوریتم تشخیص تعارض پرواز در ارتفاع پایین بر اساس شاخص فضایی و زمانی شبکه چند لایه. ISPRS Int. J. Geo-Inf. 2019 ، 8 ، 289. [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
  14. یانگ، م. چنگ، سی. چن، ب. استخراج شباهت فردی با ارزیابی تعاملات با مکان‌های مهم شخصی از مسیرهای GPS. ISPRS Int. J. Geo-Inf. 2018 ، 7 ، 126. [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
  15. بردلی، PE; Jahn، MW در مورد رفتار شاخص‌های منحنی پرکننده فضایی با مقیاس p-Adic برای داده‌های با ابعاد بالا. محاسبه کنید. J. 2020 . [ Google Scholar ] [ CrossRef ]
  16. لورینی، آر. تامپسون، دی. مبانی سیستم های اطلاعات فضایی . مطبوعات دانشگاهی: کمبریج، MA، ایالات متحده آمریکا، 1992; جلد 37. [ Google Scholar ]
  17. جین، ا. چنگ، سی. روش کدگذاری داده های فضایی بر اساس شبکه تقسیم بندی جهانی. جی. ژئومات. علمی تکنولوژی 2013 ، 30 ، 284-287. [ Google Scholar ]
  18. تانگ، ایکس. بن، جی. وانگ، ی. ژانگ، ی. پی، تی. کدگذاری کارآمد و طرح عملیات فضایی برای سیستم شبکه جهانی گسسته شش ضلعی دیافراگم 4. بین المللی جی. جئوگر. Inf. علمی 2013 ، 27 ، 898-921. [ Google Scholar ] [ CrossRef ]
  19. ژو، ایکس. تانگ، دی. هائو، ال. Song, Y. کاربرد تئوری کمربند تقسیم زمین در پردازش تصویر. علمی Surv. نقشه 2019 ، 44 ، 84-89. [ Google Scholar ]
  20. لی، اس. پو، جی. چنگ، سی. Chen, B. روشی برای مدیریت و پرس و جو داده های جغرافیایی فضایی با استفاده از شاخص فضایی آرایه کد شبکه ای. علوم زمین به اطلاع رساندن. 2019 ، 12 ، 173-181. [ Google Scholar ] [ CrossRef ]
  21. موضوع 21 کنسرسیوم زمین فضایی باز: مشخصات چکیده سیستم های شبکه جهانی گسسته. در دسترس آنلاین: https://docs.opengeospatial.org/as/15-104r5/15-104r5.html (در 18 ژوئیه 2021 قابل دسترسی است).
  22. چن، جی. لی، سی ام؛ Li، ZL; طلا، C. مدل 9 تقاطع مبتنی بر ورونوی برای روابط فضایی. بین المللی جی. جئوگر. Inf. علمی 2001 ، 15 ، 201-220. [ Google Scholar ] [ CrossRef ]
  23. ژو، ی. وانگ، اس. Guan، Y. یک الگوریتم موازی کارآمد برای تجزیه و تحلیل پوشش چند ضلعی. Appl. علمی 2019 ، 9 ، 4857. [ Google Scholar ] [ CrossRef ] [ نسخه سبز ]
  24. ماه، بی. Jagadish، HV; فالوتسوس، سی. Saltz، JH تجزیه و تحلیل خواص خوشه‌بندی منحنی پرکننده فضای هیلبرت. IEEE Trans. بدانید. مهندسی داده 2001 ، 13 ، 124-141. [ Google Scholar ] [ CrossRef ][ نسخه سبز ]
  25. ویلر، ک. Atherton، P. حذف سطح پنهان با استفاده از مرتب سازی ناحیه چند ضلعی. محاسبات ACM SIGGRAPH. نمودار. 1977 ، 11 ، 214-222. [ Google Scholar ] [ CrossRef ]
Ijgi 10 00489 g001 550
شکل 1. از سیاره زمین تا زمین گسسته دیجیتال: ( الف ) سیاره زمین. ( ب ) زمین گسسته دیجیتالی.
Ijgi 10 00489 g002 550
شکل 2. مدل GeoSOT-3D: ( الف ) زیربخش GeoSOT; ( ب ) زیربخش GeoSOT-3D. ( ج ) منحنی پر شدن مرتبه Z.
Ijgi 10 00489 g003 550
شکل 3. ترکیب کد باینری: ( الف ) کد 1 بعدی باینری. ( ب ) کد سه بعدی باینری.
Ijgi 10 00489 g004 550
شکل 4. حالت عملیات فضایی فعلی داده های زیربخش.
Ijgi 10 00489 g005 550
شکل 5. طراحی چارچوب عملیات جبری.
Ijgi 10 00489 g006 550
شکل 6. چارچوب عملیات جبری برای GeoSOT-3D.
Ijgi 10 00489 g007 550
شکل 7. عملیات “+” کد GeoSOT-3D.
Ijgi 10 00489 g008 550
شکل 8. جهت گیری فضایی. ( a ) تعریف جهت گیری نسبی شبکه را نشان می دهد. ( ب ) تعریف جهت گیری مطلق شبکه را نشان می دهد.
Ijgi 10 00489 g009 550
شکل 9. محاسبه رابطه جهت گیری فضایی شبکه.
Ijgi 10 00489 g010 550
شکل 10. محاسبه فضایی: ( الف ) جهت های همسایه. ( ب ) هندسه به معنای نمودار برای عملیات شبکه اصلی (در دو بعدی).
Ijgi 10 00489 g011 550
شکل 11. نمودار ورونوی.
Ijgi 10 00489 g012 550
شکل 12. رابطه توپولوژیکی فضایی بین شبکه ها. ( الف ) مکاتبات با DE-9IM. ( ب ) رابطه توپولوژیکی فضایی بین شبکه ها (3D).
Ijgi 10 00489 g013a 550 Ijgi 10 00489 g013b 550
شکل 13. عملیات اتحادیه: ( الف ) برای دو شبکه. ( ب ) برای دو مجموعه شبکه.
Ijgi 10 00489 g014a 550 Ijgi 10 00489 g014b 550
شکل 14. سکوی آزمایشی: ( الف ) روی زمین. ب ) زیرزمینی
Ijgi 10 00489 g015 550
شکل 15. منحنی هیلبرت.
Ijgi 10 00489 g016 550
شکل 16. میانگین زمان برای اندازه گیری فاصله مکانی.
Ijgi 10 00489 g017 550
شکل 17. میانگین زمان برای اندازه گیری جهت گیری فضایی.
Ijgi 10 00489 g018 550
شکل 18. آزمایش‌های همپوشانی: لایه ( a ) و لایه ( b ) لایه‌هایی هستند که قرار است روی هم قرار بگیرند و فقط یک شی ناحیه دارند. لایه ( ج ) نتیجه همپوشانی است. مناطق صورتی و سبز مناطق اصلی هستند. ناحیه ارغوانی ناحیه روی هم پوشانده شده است.
Ijgi 10 00489 g019 550
شکل 19. آزمایش های همپوشانی: لایه ( a ) یک لایه با اشیاء چند ناحیه است. ( a ) را در امتداد محور x حرکت دادیم و یک لایه جدید تشکیل دادیم که با لایه قدیمی ( a ) پوشانده شد. لایه ( b ) نتیجه همپوشانی است.
Ijgi 10 00489 g020 550
شکل 20. تقاطع دو خط در فضای سه بعدی.

دسته‌بندی نشده

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

بدون دیدگاه

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