مدل رقومی زمین (DTM) در شش بخش
نقل قول :
ابتدا یه سری بحث های مقدماتی و تئوری و بعدا کارکردن با DTM در ARcGIS
بخش سوم
2 – توصیف کننده های زمین و استراتژی های نمونه برداری
براي ساخت يك شبكه مثلثي از مجموعه نقاطي كه به صورت مجموعه تصادفي توزيع شده اند، راه هاي مختلفي وجود دارد كه هر كدام بر اساس پايه هاي متفاوتي است كه بدان ها اشاره مي كنيم.
شيوه هاي تشكيل TIN
براي تشكيل TIN دو شيوه براي وارد كردن داده ها داريم :
1) تمام داده ها را به صورت كلي به شبكه بدهيم --> (static) batch
2) اجازه حذف يا اضافه كردن نقاط را در حين پروسه مثلث بندي بدهيم-->dynamic
بايد توجه كرد منظور از ديناميك حركت نقاط نيست. (حركت نقاط موضوع كينماتيك است.)
داده هاي مكاني هم مي تواند به فرم رستري و هم به فرم برداري باشد، بنابراين مثلث بندي در هر دو وضعيت مي تواند انجام شود.
شبكه مثلث بندي هم مي تواند به طور مستقيم از روي داده ها توليد شود و هم به طور غير مستقيم از روي dual آن Voronoi diagram ساخته شود. شيوه غير مستقيم بيشتر در وضعيت رستري انجام مي شود، چون در فضاي رستري ساخت Voronoi diagram راحت تر است.
اصول تشكيل TIN
اصل empty circumcircle : هيچ نقطه ديگري داخل دايره محيطي مثلث دلوني قرار نمي گيرد.
اصل local equiangularity : شبكه مثلثي بهينه است اگر جابجا كردن قطر چهار ضلعي محدبي كه با دو مثلث مجاور ساخته شده منجر به كاهش كوچكترين زاويه داخلي يا افزايش بزرگتريم زاويه داخلي نشود. به اين اصل max-min angle نيز مي گويند.
اصل مي نيمم كردن مجموع فاصله ها : اضافه كردن نقطه جديد، براي ساخت مثلث جديد ، مثلثي مي شود كه جمع فاصله آن از نقاط baseline كمترين مقدار باشد.
اصل مينيمم كردن شعاع دايره محيطي : نقطه جديد براي ساخت مثلث با كمترين شعاع دايره محيطي ساخته مي شود.
Vector-based Static Delunay Triangulation
انتخاب نقطه شروع :
مزيت مثلث بندي دلوني : شكل نهايي شبكه به نقطه شروع وابسته نيست. انتخاب آن تنها براي راحتي پياده سازي الگوريتم مطرح مي شود. برخي از انتحاب ها عبارتست از :
1. مركز (تقريبي) هندسي داده
2. دو نقطه اي كه كمترين فاصله را نسبت به هم دارند
3. يك line segment روي مرز فرضي
4. يك line segment روي مرز convex hall
بعد از انتخاب اولين نقطه دومين نقطه كه نزديكترين نقطه بين نقاط موجود است شناسايي شده و نقطه سوم search مي شود. نقطه سوم به صورت ساعتگرد نسبت به دو نقطه قبل انتخاب مي شود. يك روش جستجوي ساده ، رسم دايره به صورتي است كه خط واصل بين دو نقطه اول قطر آن دايره باشد. اگر فقط يك نقطه داخل دايره بود آن نقطه به عنوان نقطه سوم انتخاب مي شود. اگر بيش از يك نقطه داخل دايره بود نقطه اي كه به پايه نزديكتر بود انتحاب مي شود و اگر نقطه اي داخل دايره نبود به تدريج شعاع دايره را زياد مي كنيم طوري كه پايه وتر دايره باشد، تا نقطه سومي داخل دايره قرار گيرد.
براي تشكيل مثلث هاي بعدي، يك راه اين است كه از روي مرز convex hall به تدريح حركت كرده تا به مركز برسيم.
Vector-based Dynamic Delunay Triangulation
هنگامي كه حجم داده ها بالاست جستجوي نقاط كارايي نخواهد داشت. به همين دليل مثلث بندي اغلب به صورت ديناميكي و با افزايش تدريجي نقاط انجام مي شود.(incremental triangulation) الگوريتم هاي مختلفي براي مثلث بندي به اين شيوه وجود دارد كه در اينجا الگوريتم Bowyer-Watson شرح داده مي شود :
ايده پايه اين روش شروع با مثلث هاي بزرگ است. مرحله اول تشكيل مثلث هاي بزرگ خيلي ساده است. پس از تشكيل مثلث هاي بزرگ نقاط به تدريج وارد مي شود. به طور مثال نقطه P وارد يكي از مثلث ها مي شود (تشخيص اين كه نقطه به كدام مثلث وارد شده يه عهده الگوريتم walk است.) و آن مثلث را به سه قسمت تقسيم مي كند. سپس براي هر ضلع مثلث قبلي اصل empty circumcircle چك مي شود.
الگوريتم Walk
هنگامي كه حجم داده ها بالاست ، براي افزايش كارايي پيدا كردن مثلثي كه نقطه جديد به آن وارد شده توسط اين الگوريتم انجام مي شود. در اين الگوريتم دو مساله در نظر گرفته مي شود :
1. يك معيار عددي كه مشخص كند نقطه داخل مثلث هست يا نه
2. يك pointer كه اگر نقطه داخل مثلث فعلي نبود به مثلث بعدي اشاره كند
ارتباط جهتي بين نقطه P و خط AB با فرمول زير مشخص مي شود :
اگر D>0 نقطه P سمت چپ AB قرار دارد. (پادساعتگرد)
اگر D=0 نقطه P روي AB قرار دارد.
اگر D<0 نقطه P سمت راست AB قرار دارد. (ساعتگرد)
به اين ترتيب معيار عددي به صورت زير خواهد بود:
1 ، 2 و 3 سه راس مثلث مورد نظر
اگر اين سه مقدار مثبت بود نقطه P داخل مثلث 123 خواهد بود.
براي ايجاد pointer از اولين ضلعي كه مقدار مربوط به آن منفي بود عبور مي كنيم و همين روند را براي مثلث (هاي) بعدي تكرار مي كنيم تا به مثلثي برسيم كه هر سه مقدار مثبت شود.
معيار عددي براي swap :
بعد از اين كه مثلث پيدا شد با وصل كردن نقطه جديد به راس هاي آن مثلث ، مثلث قبلي به سه مثلث تقسيم مي شود. حال همانطور كه گفته شد بايد شرط empty circumcircle براي اين سه مثلث چك شود.
براي بررسي اين شرط براي نقطه P و سه مثلث مجاور مثلث قبلي اين شرط را چك مي كنيم :
A ، B و C ، سه راس مثلث در جهت پادساعتگرد و D نقطه چهارم است.
اگر H>0 بود آنگاه ضلع جديد بايد swap شود. اين شرط براي مثلث هاي مجاور مثلث swap شده به وسيله stack بايد چك شود و اين كار تا زماني كه تمام مثلث ها در شرط دلوني صدق كند بايد تكرار شود. براي جنوگيري از مشكل حلقه نامتناهي يك مقدار صفر به عنوان خارج دامنه در نظر مي كيريم و وقتي به آن رسيديم swap را انجام نمي دهيم.
حذف نقطه از شبكه مثلث بندي دلوني :
اين الگوريتم عكس الگوريتم وارد كردن نقطه است. براي اين كار الگوريتم هاي مختلفي وجود دارد :
الگوريتم Heller :
مثلثي كه كوچكترين دايره محيطي را دارد با swap كردن ضلع حذف مي شود. اين كار براي هر سه ضلع انجام مي شود و پس از swap كردن هر سه ضلع نقطه حذف مي شود.
الگوريتم Deviller :
در اين روش مثلث هايي كه شامل نقطه مورد نظر هستند به ترتيب power of P حذف مي شوند.
در اين روش براي حذف مثلث ها از ساختار queue استفاده مي شود.
الگوريتم مصطفوي :
در اين روش مثلثي حذف مي شود كه دايره محيطي آن شامل هيچ كدام از نقاط همسايه P نباشد.
Constrained Delunay Triangulation
دقت DTM نهايي با در نظر گرفتن نقاط و خطوط F-S بالاتر خواهد رفت. به عبارتي نمي خواهيم اين خطوط توسط ضلع هاي مثلث قطع شود.
ساده ترين راه : روي اين خطوط نقاط را dense در نظر بگيريم ( فاصله بين آنها از نصف فاصله متوسط نقاط مجموعه كمتر باشد.) ايراد اين روش افزايش حجم فايل است.
شيوه ديگر برخورد با اين خطوط به عنوان قيد است.
مثلث بندي مقيد : (Constrained Delunay Triangulation – CDT)
يك CDT در حقيقت يك شبكه delunay نيست. چون برخي از مثلث ها ممكن است در شرط دلوني صدق نكند. براي يك مجموعه داده مشخص و يك مجموعه خط به عنوان قيد رئوس مثلث بندي بايد شرايط زير را داشته باشد :
1. خطوط قيد مشخص در مثلث بندي لحاظ مي شود.
2. مثلث بندي نهايي تا جاي ممكن به مثلث بندي دلوني نزديك باشد
منظور از CDT اين است كه خطوط F-S توسط اضلاع مثلث قطع نشود. براي برآورده كردن اين منظور اين خطوط يك مانع در نظر گرفته مي شوند و اصل circle circumcircle اين گونه بهبود مي يابد كه فقط براي نقاطي كه بتواند از يك سمت خط ديده شوند اين اصل در نظر گرفته مي شود. براي اين منظور شيوه دو مرحله اي براي ساخت CDT در نظر گرفته مي شود :
1. ساخت مثلث بندي دلوني استاندارد با تمام نقاط شامل داده هاي نقطه اي بدون در نظر گرفتن قيدها انجام مي شود
2. براي برقراري قيود و سازگار كردن تمام مثلث ها ، اضلاع مثلث هايي كه اين خطوط را قطع كرده اند، swap مي شوند.
Triangulation from Contour Data with Skeletonization
شيوه هاي مثلث بندي از داده هاي منحني ميزان :
1. با خطوط منحني ميزان به صورت نقاط تصادفي رفتار شود و از مثلث بندي دلوني براي تشكيل مثلث ها استفاده شود.
2. با خطوط منحني ميزان مثل قيد رفتار شود.
3. حد وسط بين دو شيوه فوق
در شيوه اول برخي اثرات ناخواسته مثل flat triangle ( سه راس مثلث از يك منحني انتخاب شده باشد) ممكن است اتفاق بيفتد. در شيوه دوم هم حجم محاسبات خيلي زياد مي شود.
حد وسط اين دو شيوه ، اين گونه است كه نقاط بيشتري براي جلوگيري از اين دو مشكل اضافه كنيم ß استخراج خطوط skeleton :
براي اين كار از Medial Axis Transform(MAT) استفاده مي شود. نقاط روي MAT مركز دايره هاي محاطي مماس حداقل در دو نقطه است.(شكل 23-5 صفحه 104)
از روي Voronoi Diagram مي توان MAT را استخراج نمود.
پس از استخراج خطوط Skeleton از منحني ميزان ها بايد ارتفاع آنها را استخراج نمود. قسمت عمده اي از اين خطوط بين دو خط منحني مجاور قرار مي گيرند كه ارتفاع آنها به ساگي از ميانگين ارتفاع دو منحني مجاور استخراج مي شود. قسمت هاي از اين خطوط شامل شاخه هاي كوچك است (شكل 26-5 صفحه106 ) . براي بدست آوردن ارتفاع اين نقاط از مقايسه شعاع دايره هر نقطه و شعاع دايره در محل برخورد با محور اصلي Skeleton استفاده مي شود :
Zc : ارتفاع منحني ميزان نزديكتر
Zb : ارتفاع منحني ميزان ديگر
Zi : ارتفاع نقطه مورد نظر
Ri : شعاع دايره در نقطه مورد نظر
Rc : شعاع دايره مرجع
نقاط Skeleton براي مثلث بندي از روي منحني ميزان به شبكه نقاط اضافه مي شوند.
Delunay Triangulation Via Voronoi Diagram
همانطور كه گفته شد مثلث بندي دلوني را مي توان به طور غير مستقيم از روي Voronoi Diagram ساخت و برعكس.
ساخت دلوني از Voronoi : پس از ساخت Voronoi هر دو نقطه اي كه يك مرز مشترك در ناحيه voronoi دارند به هم وصل مي شوند و به اين شيوه مثلث ها ساخته مي شود. پيوستگي مثلث ها بررسي و نهايتا مثلث بندي شكل مي گيرد.
ساخت Voronoi Diagram :
الگوريتم بر مبناي بردار :
از نقطه نظر محاسبات هندسي، يك Voronoi Diagram تقسيم بندي صفحه به نواحي پليگوني n-ضلعي است كه هر كدام از آنها مرتبط با يك نقطه مشخص است . ناحيه مربوط به يك نقطه مجموعه نقاطي است كه به آن نقطه از ساير نقاط نزديك تر است. پليگون هاي Thiessen يا نواحي Voronoi يك الگو از پليگون هاي محدب است كه كل صفحه را پوشش مي دهد.
روش ساده ساخت Voronoi الگوريتم تدريجي است كه ايده پايه آن اضافه كردن نقطه در زمان است.
الگوريتم بر مبناي رستر :
از آنجايي كه مرزهاي Voronoi نقطه P از خطوط عمود منصف بين P و همسايه هاي نزديكش ساخته مي شود، فاصله در توليد Voronoi يك مفهوم كليدي است. از طرفي چون كار با اعداد صحيح در فضاي رستري ساده تر است مساله تعريف فاصله integer مطرح مي شود. دو شيوه تعريف فاصله در شكل 32-5 صفحه 112 نشان داده شده است. با تعريف فاصله رستري فاصله هر پيكسل با پيكسل هاي مرجه مشخص شده و آن پيكسل به ناحيه مرجعي تعلق مي گيرد كه كمترين فاصله را از آن دارد. در واقع تبديل فاصله مي تواند توسط اپراتور ها در رياضيات مورفولوژي توسعه يابد.
نظرات شما عزیزان:
