مدل رقومی زمین (DTM)- بخش سوم (تولید TIN)

تولید TIN

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

شیوه های تشکیل 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 با فرمول زیر مشخص می شود :

clip image002 thumb1 مدل رقومی زمین (DTM)  بخش سوم (تولید TIN)

اگر D>0 نقطه P سمت چپ AB قرار دارد. (پادساعتگرد)

اگر D=0 نقطه P روی AB قرار دارد.

اگر D<0 نقطه P سمت راست AB قرار دارد. (ساعتگرد)

به این ترتیب معیار عددی به صورت زیر خواهد بود:

1 ، 2 و 3 سه راس مثلث مورد نظر

clip image004 thumb1 مدل رقومی زمین (DTM)  بخش سوم (تولید TIN) و clip image006 thumb مدل رقومی زمین (DTM)  بخش سوم (تولید TIN) و clip image008 thumb مدل رقومی زمین (DTM)  بخش سوم (تولید TIN)

اگر این سه مقدار مثبت بود نقطه P داخل مثلث 123 خواهد بود.

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

معیار عددی برای swap :

بعد از این که مثلث پیدا شد با وصل کردن نقطه جدید به راس های آن مثلث ، مثلث قبلی به سه مثلث تقسیم می شود. حال همانطور که گفته شد باید شرط empty circumcircle برای این سه مثلث چک شود.

برای بررسی این شرط برای نقطه P و سه مثلث مجاور مثلث قبلی این شرط را چک می کنیم :

clip image010 thumb مدل رقومی زمین (DTM)  بخش سوم (تولید TIN)

 A ، B و C ، سه راس مثلث در جهت پادساعتگرد و D نقطه چهارم است.

اگر H>0 بود آنگاه ضلع جدید باید swap شود. این شرط برای مثلث های مجاور مثلث swap شده به وسیله stack باید چک شود و این کار تا زمانی که تمام مثلث ها در شرط دلونی صدق کند باید تکرار شود. برای جنوگیری از مشکل حلقه نامتناهی یک مقدار صفر به عنوان خارج دامنه در نظر می کیریم و وقتی به آن رسیدیم swap را انجام نمی دهیم.

حذف نقطه از شبکه مثلث بندی دلونی :

این الگوریتم عکس الگوریتم وارد کردن نقطه است. برای این کار الگوریتم های مختلفی وجود دارد :

الگوریتم Heller :

مثلثی که کوچکترین دایره محیطی را دارد با swap کردن ضلع حذف می شود. این کار برای هر سه ضلع انجام می شود و پس از swap کردن هر سه ضلع نقطه حذف می شود.

الگوریتم Deviller :

در این روش مثلث هایی که شامل نقطه مورد نظر هستند به ترتیب power of P حذف می شوند.

clip image012 thumb مدل رقومی زمین (DTM)  بخش سوم (تولید TIN)

 در این روش برای حذف مثلث ها از ساختار 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 استفاده می شود :

clip image014 thumb مدل رقومی زمین (DTM)  بخش سوم (تولید TIN)

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 نشان داده شده است. با تعریف فاصله رستری فاصله هر پیکسل با پیکسل های مرجه مشخص شده و آن پیکسل به ناحیه مرجعی تعلق می گیرد که کمترین فاصله را از آن دارد. در واقع تبدیل فاصله می تواند توسط اپراتور ها در ریاضیات مورفولوژی توسعه یابد.

Поэтому вам не стоит экономить на услугах надежного и ответственного копирайтера, а лучше всего взяться за это дело собственноручно topodin, Ну что давайте экспериментировать на кошках? Самое главное в привлечении клиента – составить его портрет, вы должны понимать кто ваш потенциальный клиент и что ему от вас надо,  так вы поймете, чем привлечь клиента и как качественно его обслужить! При привлечении первых клиентов рекомендуют сделать вывеску и написать – «Мы открылись»

مطالب مرتبط

2 نظر

  1. فرخ شفیعی

    سلام
    شما سایت خیلی خوبی ایجاد کرده اید.
    من بدنبال یک سورس کد الگوریتم دیلونی هستم که قادر به مثلث بندی و پس از ان ایجاد منحنی میزان باشه.منتها منحنی میزان هاش باید بتونن با Swap مثلث ها تغییر شکل بدهند.
    منظور از Swap در اینجا اینست که ضلع مشترک دو مثلث مجاور تغییر کند.این کار بنحو شایسته ای در نرم افزار SDRMAP6.5 انجام می شود منتها مشکل آنست که این نرم افزار روی ویندوز ۷ بالا نمی آید.

    پاسخ
    1. ادمین

      عبارت Delaunay algorithm code را اگر در گوگل جستجو کنید به احتمال زیاد به برنامه هایی در زبان های مختلف دست خواهید یافت.

      پاسخ

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *