ساختار داده درختی

ساختار داده درختی یک ساختار داده درختی است که رستری  را با تقسیم بازگشتی آن به چهار ربع، ربع فرعی و غیره تا زمانی که هر ربع حاوی سلول‌هایی با همان مقدار باشد، تقسیم می‌کند. شکل ۲-۳۱ یک درخت چهارگانه را برای ذخیره سازی رستری نشان می‌دهد که نمایانگر آب در اطراف زمین (به رنگ سفید) است. گره ریشه (بالا) درخت کل رستر را نشان می‌دهد. یک گره غیر برگ نشان دهنده یک ربع با مقادیر سلولی چندگانه است و به چهار قسمت فرعی تقسیم می‌شود. گره‌های برگ مربوط به آن چهار ضلعی است که دارای مقدار سلولی واحد هستند و برای آنها نیاز به تقسیم دیگری نیست.

بسیاری از طرح‌های نمایه سازی برای شناسایی چهار ضلعی‌ها ایجاد شده است. مثال درشکل ۲-۳۱ تنها یکی از آنهاست با استفاده از این طرح چهار ضلع شمال غربی صفر، ربع چهارم شمال شرقی ۱، ربع چهارم جنوب غربی ۲ و ربع چهارم جنوب شرقی ۳ شماره گذاری می‌شود. هر ربع به چهار زیر چهار قسمت تقسیم می‌شود که با استفاده از شماره چهارم والدین آنها که با ربع چهارم خود ضمیمه شده است کدگذاری می‌شوند. به عنوان مثال کد ۳۱ نشان دهنده ربع دوم شمال شرقی (کد ۱) به عنوان یک زیرمعیار از ربع درجه جنوب شرقی سطح اول (کد ۳) است. این سیستم نمایه سازی سلسله مراتبی اجازه می‌دهد تا مکان هر چهارم نسبت به منشاء رستر محاسبه شود و تعیین اطلاعات محله را آسان می‌کند (لو و یونگ، ۲۰۰۷).

ساختار داده درختی برای مناطقی که داده‌ها نسبتاً همگن هستند و برای برنامه‌هایی که به جستجوی مکرر پایگاه داده نیاز دارند، مناسب‌تر است. تکنیک‌های ذخیره سازی داده، نمایه سازی و جستجو توسط چهار درخت به خوبی تحقیق و مستند شده است (سامت، ۱۹۹۰ a و ۱۹۹۰ b) . ساختار داده چهار درختی در SPANS GIS   ( Ebdon,1992) استفاده شد که اکنون در Geomatica PCI گنجانده شده است.

مدل داده‌های شی گرا

مشابه مدل داده‌های برداری، مدل داده‌های شی گرا با نمای شی از مکان جغرافیایی مطابقت دارد. این شامل چندین مفهوم شی گرا از جمله شناسه شی و شی، ویژگی‌ها و روش ها، کلاس، سلسله مراتب کلاس و وراثت است.

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

شکل ۲-۳۱ Quadtree

 

هر شیء متعلق به یک کلاس خاص است. همه اشیاء در یک کلاس مجموعه ای از ویژگیها و روشها را به اشتراک می‌گذارند و به پیامهای مشابه پاسخ می‌دهند. یک شی باید فقط به یک کلاس تعلق داشته باشد. به عنوان مثال همه اجسام جاده توسط یک کلاس Road توصیف می‌شوند. به اشیاء در یک کلاس نمونه‌های کلاس می‌گویند. هر نمونه برای هر ویژگی ارزش خاص خود را دارد اما همان نام و متد ویژگی را با نمونه‌های دیگر کلاس به اشتراک می‌گذارد همانطور که در شکل ۲-۳۲ نشان داده شده است.

علاوه بر این کلاس جدید (زیر کلاس) می‌تواند از یک کلاس موجود (فوق کلاس) مشتق شود. زیر کلاس تمام صفات و متدهای سوپرکلاس را به ارث می‌برد و ممکن است ویژگی‌ها و متدهای اضافی داشته باشد. کلاس‌ها را می‌توان در یک سلسله مراتب کلاس سازماندهی کرد که در آن سوپرکلاس‌ها در بالا و زیر کلاس‌ها به پایین منشعب می‌شوند. به این ترتیب وراثت می‌تواند اتفاق بیفتد جایی که روشهای فوق کلاس را می‌توان تعریف کرد و سپس در همه اشیاء زیر کلاس استفاده کرد.

شکل ۲-۳۲ مسیرکلاس و نمونه‌های آن

شکل ۲-۳۳

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

کلاس‌های نقطه، خط و سطح ویژگی‌ها و روش‌ها را از GeoEntity به ارث می‌برند، اما ویژگی‌ها و متدهای خود را تعریف می‌کنند. کلاسهای خط و سطح سه ویژگی اضافه می‌کنند : تعداد مختصات نقطه، آرایه مختصات x و آرایه مختصات y. دو کلاس یک روش جدید، getBound ، برای بدست آوردن حداکثر و حداقل مقادیر x و y از یک شی یا ناحیه دارند. کلاس سطح متد جدید دیگری نیز دارد که مشخص می‌کند برای تعیین اینکه آیا یک نقطه خاص در یک شی ناحیه قرار دارد یا خیر استفاده می‌شود. سه زیر کلاس روشهای draw و getSize را دوباره تعریف می‌کنند. متد رسم کلاس نقطه ممکن است یک شی نقطه ای را با نماد نقطه بکشد و متد getSize آن نیز مقدار صفر را باز می‌گرداند. روش رسم کلاس خط ممکن است یک شی را با نماد خط با عرض معین نشان دهد و متد getSize آن طول شی خط را اندازه می‌گیرد. برای یک شیء متد رسم کلاس سطح آن را با استفاده از نماد مساحت نشان می‌دهد و متد getSize آن اندازه مساحت شی را محاسبه می‌کند. این توانایی یک روش برای انجام وظایف مختلف با ورودی و خروجی متفاوت، بارگذاری روش نامیده می‌شود.

مدل داده شی گرا داده‌های مکانی (شامل هندسه ، توپولوژی و ویژگی ها) را به عنوان اشیا ذخیره می‌کند. یک شیء هم حالت و هم رفتار را در بر می‌گیرد و می‌تواند تمام روابطی را که با اجسام دیگر دارد ذخیره کند. هر شیء به عنوان یک جزء جداگانه یا بلوک ساختمان تعریف شده است که می‌تواند با سایر اشیاء برای تشکیل اشیاء پیچیده مورد استفاده قرار گیرد. این ویژگیها به کاربران امکان می‌دهد مدلهای شی گرا خود را بسازند که بر اساس دیدگاه خود و لایه  بندی ویژگیهای جغرافیایی که مطالعه می‌کنند، یک مدل پایه را توسعه دهند. علاوه بر این آنها اجازه می‌دهند داده‌های مکانی به طور مستقیم با استفاده از یک زبان برنامه نویسی شی گرا ویرایش شوند که به دلیل کارآمدی برتر به عنوان تکنیک برنامه نویسی ترجیحی مورد استفاده توسعه دهندگان GIS قرار گرفته است. مدل داده پایگاه جغرافیایی توسعه یافته توسط ESRI نمونه ای از مدل داده‌های شی گرا است (به کادر ۲-۶ مراجعه کنید). مدل داده‌های شی گرا نیز در SmallWorld GIS، Oracle Spatial و IBM DB2 Spatial Extender استفاده شده است.

کادر ۲-۶- مدل داده‌های پایگاه اطلاعات زمین جغرافیایی

تکنیک

Geodatabase یک مدل داده شی گرا است که توسط ESRI برای نمایش ویژگی‌های جغرافیایی دنیای واقعی و ذخیره داده‌های مکانی، به عنوان بخشی از ArcObjects، فناوری مؤلفه اساسی برای محصولات ArcGIS ایجاد شده است (سیلر، ۲۰۱۰).  همانطور که در شکل ۲-۳۴  نشان داده شده است مدل پایه پایگاه داده جغرافیایی شامل کلاس‌های کلیدی زیر است :

شکل ۲-۳۴ مدل پایه پایگاه زمینی

۱٫      مکان کاری :  یک مکان کاری مربوط به یک پایگاه داده جغرافیایی، یک مکان کاری با پوشش ArcInfo یا یک پوشه با فایل شکل است. این کلاس محفظه ای از اشیاء مجموعه داده است که مجموعه داده‌های مکانی و غیر مکانی را نشان می‌دهد و روشهایی را برای نمونه گیری مجموعه داده‌های موجود و ایجاد مجموعه داده‌های جدید ارائه می‌دهد. مکان کاری ممکن است شامل صفر یا چند مجموعه داده باشد.

۲٫      مجموعه داده : مجموعه ای از داده‌ها در مکان کاری است. این کلاس بالاترین سطح محفظه داده است که نمونه‌های آن مجموعه ای از انواع مختلف مجموعه داده‌ها هستند.

۳٫      GeoDataset : این زیر کلاسی از مجموعه داده‌ها است، نشان دهنده نوع مجموعه داده است که حاوی داده‌های مکانی است.

۴٫      FeatureDataset : این مجموعه داده ویژگی‌ها داده‌های بردار را در کلاس‌های صفت ذخیره می‌کند. این زیر کلاس از کلاس GeoDataset است. نمونه‌های آن مجموعه ای از کلاس‌های ویژگی با سیستم‌های مرجع مرجع متداول است.

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

۶٫      جدول : جدول مجموعه ای از داده است. مجموعه ای از ردیف‌ها است که دارای ویژگی‌های ذخیره شده در ستون ها، به فیلدها هستند. این کلاس یک شی Dataset است. یک شیء جدول نشان دهنده یک ObjectClass یا یک AttributedRelationshipClass در یک geodatabase است.

۷٫      ردیف : رکورد در یک جدول است. یک شیء ردیف آنی است که یک ردیف مداوم را در یک شیء جدول نشان می‌دهد. یک ردیف دارای مجموعه ای از فیلدها است. همه سطرهای یک جدول مجموعه ای از فیلدها را به اشتراک می‌گذارند. کلاس ردیف عضوی از جدول کلاس است.

۸٫      ObjectClass : این جدولی است که ردیف‌های آن نشان دهنده موجودیت‌ها هستند و به عنوان اشیا با حالت‌ها و رفتارها مدل شده اند. ممکن است حاوی یک زیرگونه باشد که می‌تواند موارد آن را در چند زیرگروه لایه بندی کند. همه زیرگونه‌ها تعریف فیلد یکسانی دارند و در یک جدول ذخیره می‌شوند. Subtyping جایگزینی برای ایجاد چندین کلاس فرعی است که هر کدام توسط کلاس شی خاص خود نشان داده می‌شوند. همچنین می‌تواند در تعریف ویژگی‌ها و قوانین اتصال که در موارد ObjectClass اعمال می‌شود ، استفاده شود.

FeatureClass یک ObjectClass است که اشیاء آن ویژگی‌ها هستند. یک کلاس ویژگی دارای یک زمینه متمایز از نوع هندسه است که به آن میدان شکل گفته می‌شود. قسمت Shape هندسه ویژگی‌های FeatureClass را ذخیره می‌کند. شکل ۲-۳۵ نمونه ای از کلاس ویژگی چند ضلعی است که به صورت جدول ذخیره می‌شود. هر سطر یک ویژگی چند ضلعی را نشان می‌دهد. در این جدول کلاس ویژگی‌های چند ضلعی، قسمت Shape هندسه چند ضلعی را برای هر ویژگی نگه می‌دارد. مقدار Polygon نشان می‌دهد که این فیلد شامل مختصات و هندسه ای است که در هر سطر یک چند ضلعی را تعریف می‌کند.

شی : این یک ردیف با شناسه کلاس شی غیر منفی (OBJECTID) است که در پایگاه داده جغرافیایی مختص به خود است همانطور که در شکل ۲-۳۵ نشان داده شده است این یک زیر کلاس از کلاس Row و یکی از اعضای ObjectClass است.

·        ویژگی : این یک شی مکانی با شکل هندسی است. این کلاس یک زیر کلاس از کلاس Object است. همچنین یکی از اعضای FeatureClass است. نوع شکل یک ویژگی با کلاس ویژگی تعریف می‌شود که می‌تواند ترکیبی از نقاط باشد. نقطه (ویژگی‌هایی که از بیش از یک نقطه تشکیل شده اند)، Polyline یا Polygon باشد. همانطور که در شکل ۲-۳۵ نشان داده شده است، یک ویژگی به عنوان یک ردیف در جدول کلاس ویژگی ذخیره می‌شود.

·        RelationshipClass : این نشان دهنده ارتباط بین دو کلاس جدول و شی است.

رابطه : این کلاس مجموعه ای از روابط بین اشیاء متعلق به دو کلاس/جدول را نشان می‌دهد (یکی کلاس/جدول مبدا و دیگری کلاس/جدول مقصد). این عضو RelationshipClass است. دو نوع رابطه وجود دارد: رابطه ساده و رابطه نسبت داده شده. رابطه ساده نشان دهنده روابط یک به یک یا یک به چند بین اشیا از طریق یک فیلد در جدول مقصد است که به طور منحصر به فرد ردیفی از جدول مبدا را مشخص می‌کند (شکل ۲٫۳۶a). رابطه نسبت داده شده نشان دهنده روابط یک به یک یا یک به چند بین اشیا با استفاده از جدولی است که به عنوان جدول رابطه شناخته می‌شود، که در آن یک فیلد به طور منحصر به فرد یک ردیف از جدول مبدا را مشخص می‌کند و دیگری به طور منحصر به فرد یک ردیف از جدول مقصد را مشخص می‌کند. شکل ۲٫۳۶b).

AttributedRelationshipClass – این یک زیر کلاس از RelationshipClass و همچنین یک جدول رابطه است، همانطور که در شکل ۲-۳۶ نشان داده شده است.

AttributedRelationship – این عضوی از AttributedRelationshipClass و همچنین زیر کلاسی از کلاس‌های Row و Relationship است. این یک نوع ردیف است که یک جفت شی یا ویژگی مرتبط را نشان می‌دهد (شکل ۲٫۳۶ را ببینید).

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

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

مجموعه داده‌های شبکه – این مجموعه‌ها شامل مجموعه‌ای از لبه‌ها و اتصالات متصل و همچنین ویژگی‌های چرخشی همراه با قوانین اتصال هستند. نمایش و مدل سازی رفتار شبکه‌های حمل و نقل

زمین : این در TIN نشان داده شده و ساختار یافته است.

پوشش کاداستر : این شامل ویژگی‌های قطعه متصل است که نشان دهنده رکورد بررسی برای یک منطقه از زمین است.

شکل ۲-۳۶ روابط

قوانین توپولوژیکی همچنین می‌توانند در یک کلاس ویژگی یا بین دو یا چند کلاس ویژگی تعریف و اعمال شوند : برای مثال ساختمان‌ها (یک کلاس ویژگی) نباید با حق تقدم (کلاس ویژگی دیگر) همپوشانی داشته باشند (ESRI 2003).

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

http://support.esri.com/fa/knowledgebase/techarticles/detail/40585

برگرفته از کتاب کاربرد GISدر محیط زیست

ترجمه:سعید جوی زاده،شهناز تیموری،فاطمه حسین پور فرزانه