Mapping and Spatial Modelling for Navigation

اجرای موفقیت آمیز برنامه های کاربردی در استدلال فضایی مستلزم توجه به نمایش داده های مکانی است. به طور خاص، یک برخورد یکپارچه و یکنواخت با ویژگی‌های فضایی مختلف برای فعال کردن استدلال برای پیشبرد سریع ضروری است. در حال حاضر، رایج ترین ویژگی ها نقاط، مستطیل ها، خطوط، مناطق، سطوح و حجم ها هستند. به عنوان نمونه ای از یک کار استدلالی، پرس و جوی به شکل "همه شهرهای با جمعیت بیش از 5000 نفر را در مناطق کشت گندم در 10 مایلی رودخانه می سی سی پی بیابید." توجه داشته باشید که این پرس و جو بسیار پیچیده است. این نیاز به پردازش یک نقشه خط (برای رودخانه)، ایجاد یک راهرو یا حائل (برای یافتن منطقه در 10 مایلی رودخانه)، یک نقشه منطقه (برای گندم)، و یک نقشه نقطه (برای شهرها) دارد. استدلال فضایی با مرتب‌سازی مکانی داده‌ها (به عنوان مثال، یک شاخص فضایی) آسان‌تر می‌شود. در این مقاله نشان می‌دهیم که چگونه می‌توان از ساختارهای داده سلسله مراتبی برای تسهیل این فرآیند استفاده کرد. آنها بر اساس اصل تجزیه بازگشتی (شبیه به روش های تقسیم و غلبه) هستند. در اصل، آنها در درجه اول به عنوان دستگاه هایی برای مرتب سازی داده های بیش از یک بعد و انواع فضایی مختلف استفاده می شوند. اصطلاح quadtree اغلب برای توصیف این دسته از ساختارهای داده استفاده می شود. در این مقاله، ما بر پیشرفت‌های اخیر در استفاده از روش‌های چهاردرختی تمرکز می‌کنیم. ما در درجه اول بر روی داده های منطقه تمرکز می کنیم. برای درمان گسترده تر این موضوع، به [SameS4a، SameSSa، SameSSb، SameSSc، SameSga، SameSgbj مراجعه کنید.

The successful implementation of applications in spatial reasoning requires paying attention to the representation of spatial data. In particular, an integrated and uniform treatment of different spatial features is necessary in order to enable the reasoning to proceed quickly. Currently, the most prevalent features are points, rectangles, lines, regions, surfaces, and volumes. As an example of a reasoning task consider a query of the form "find all cities with population in excess of 5,000 in wheat growing regions within 10 miles of the Mississippi River. " Note that this query is quite complex. It requires- processing a line map (for the river), creating a corridor or buffer (to find the area within 10 miles of the river), a region map (for the wheat), and a point map (for the cities). Spatial reasoning is eased by spatially sorting the data (i. e. , a spatial index). In this paper we show how hierarchical data structures can be used to facilitate this process. They are based on the principle of recursive decomposition (similar to divide and conquer methods). In essence, they are used primarily as devices to sort data of more than one dimension and different spatial types. The term quadtree is often used to describe this class of data structures. In this paper, we focus on recent developments in the use of quadtree methods. We concentrate primarily on region data. For a more extensive treatment of this subject, see [SameS4a, SameSSa, SameSSb, SameSSc, SameSga, SameSgbj.