*توجه *توجه برای مشاهده مطلب و یا دانلود فایل مورد نظر خود به پایین همین پست مراجعه گردد
منبع : gisworld
مدل رقومی زمین (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
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. مثلث بندی نهایی تا جای ممکن به مثلث بندی دلونی نزدیک باشد
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: شعاع دایره مرجع
پست های مرتبط:
دانلود...
مشخصات مدیر وبسایت
عناوین یادداشتهای وبلاگ
بایگانی آرشیو ماهانه وبسایت
کلمات کلیدی وبسایت
