مثلث‌بندی دیلانی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
یک نمایش مثلث بندی دیلانی با دوایر محیطی

در ریاضیات و هندسه‌ی محاسباتی، یک مثلث‌بندی دیلانی برای یک مجموعه از نقاط به نام P در یک صفحه، یک مثلث‌بندی به نام (DT(P است به نحوی که هیچ یک از نقاط P درون هیچ‌یک از دایره‌های محیطی مثلثهای (DT(P نباشد. این مثلث‌بندی کمینه‌ی زاویه‌های مثلثها را به بیشترین مقدار ممکن می‌رساند و به این ترتیب از به وجود آمدن مثلث‌های باریک جلوگیری می‌کند. این مثلث‌بندی توسط بوریس دیلانی در سال ۱۹۳۴ ابداع شد.[۱] برای چهار یا تعداد بیشتری نقطه روی یک دایره یکسان (به عنوان مثال راس های یک مستطیل) تثلیث دیلانی یکتا نیست : هر دو تثلیث ممکن که چهار ضلعی را به دو مثلث تقسیم میکند شرط دیلانی ارضا می کند به عنوان مثال فرض اینکه اگر تمام دایره های محیطی مثلث ها درون تهی باشند. با در نظر گرفتن کره های محاطی ایده ی تثلیث دیلانی به سه یا تعداد بیشتری بعد تعمیم می یابد .تعمیم به سیستم متریک نسبت به سیستم اقلیدسی ترجیح داده می شود ولی در این موارد (اقلیدسی) تثلیث دیلانی الزاما وجود ندارد یا یکتا نیست.

جستجو در ویکی‌انبار در ویکی‌انبار پرونده‌هایی دربارهٔ مثلث‌بندی دیلانی موجود است.

ارتباط با دیاگرام ورونی[ویرایش]

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

دیلانی d بعدی[ویرایش]

دیلانی d بعدی برای مجموع نقاط p در فضای فضای اقلیدسی اقلیدسی d بعدی تثلیث دیلانی( DT( p است به طوریکه هیچ نقطهای در P درون ابر کره محیطی هر سیمپلکس در (DT(P نباشد . اثبات شده[۲] که در برای هر p یک تثلیث دیلانی یکتا وجود دارد که p گروهی از نقاط در جنرال پوزیشن باشند که نتیجه می دهد هیچ زیر فضای k بعدی آن شامل k + 2 نقطه و یا کره k بعدی شامل k + 3 نقطه نباشد برای 1 ≤ k ≤ d − 1 (برای مثال برا ی یک مجموعه نقاط در 3 هیچ سه نقطه ای روی یک خط وجود ندارند ، هیچ چهار نقطه ای روی یک صفحه ، هیچ چهار نقطه ای روی یک دایره و هیچ 5 نقطه ای روی یک کره وجود ندارد) مسئله پیدا کردن تثلیث دیلانی برای گروهی از نقاط در فضای ی بعدی اقلیدسی قابل تبدیل به مسئله ی یافتن پوش محدب برای یک مجموعه نقاط در فضای d + 1 بعدی با دادن مختصات اضافی p|2| ، به هر نقطه p و گرفتن گوشه پایین پوش محدب و نگاشتن مجدد به فضای d بعدی با حذف مختصات اخیر است. چون پوش محدب یکتاست بنابر این تثلیث نیز یکتاست با فرض اینکه تمام اضلاع پوش محدب سیمپلکس هستند . اضلاع غیر سیمپلکس تنها زمانی پدید می آیند که d + 2 تا از نقاط اصلی روی یک ابر کرهابر کره دی بعدی باشند به عنوان مثال نقاط در جنرال پوزیشن نباشند.

ویژگی ها:[ویرایش]

قدم های مثال
انیمیشنی که نشان می دهد تثلیث دیلانی ضلع را کوتاه تر نمیکند حتما.

فرض کنید n تعداد نقاط و d تعداد بعد باشد.


1- اتحاد تمام سیمپلکس ها در تثلیث, پوش محدب تمام نقاط است.


2- تثلیث دیلانی شامل O(nd / 2⌉)
مثلث است.[۳]
3- در صفحه (d =2) اگر b راس در پوش محدب باشند هر تثلیثی از آن نقاط حدااکثر 2n - 2 - b مثلث دارد به علاوه یک وجه بیرونی در صفحه.


4- هر راس حداقل توسط شیش مثلث محاصره شده.


5- در صفحه, تثلیث دیلانی مینمم زاویه را بیشینه میکند در مقایسه با هر تثلیث دیگری ازنقاط کوچکترین زاویه در تثلیث دیلانی حداقل به بزرگی کوچکترین زاویه در بقیه است اما تثلیث دیلانی الزاما ماکسیمم زاویه را کمینه نمیکند تثلیث دیلانی همچنین الزاما طول اضلاع را مینمم نمیکند.


6- دایره ای که بر هر مثلث دیلانی محیط است هیچ نقطه داخلی دیگری درون خود ندارد.


7- اگر یک دایره که از دو تا از نقاط داده شده بگذرد هیچ نقطه دیگری درون خود ندارد بنا بر این بخشی که دو نقطه را به هم متصل میکند یک ضلع تثلیث دیلانی نقاط داده شده است.


8- هر مثلث تثلیث دیلانی برای نقاط فضای d بعدی در یک وجه پوش محدب تصویر نقاط روی سهمی وار d + 1 بعدی صدق می کند و بلعکس.


9- نزدیک ترین همسایگی b به هر نقطه p روی یک ضلع در تثلیث دیلانی قرار دارد چون نزدیک ترین گراف همسایه یک زیر گراف از تثلیث دیلانی است.


10- تثلیث دیلانی یک اسپنر هندسی است :کوتاه ترین مسیر بین دو راس در طول اضلاع دیلانی بیشتر از \frac{4\pi}{3\sqrt{3}} \approx 2.418 برابر فاصله اقلیدسی بین آنها نیست.


تعبیر تصویری دیلانی : چرخاندن[ویرایش]

از ویژگی های فوق یک ویژگی بدست می آید .با نگاه کردن به دومثلث ABD و BCD با ضلع مشترک BD اگر زوایای α و γ کوچکتر مساوی 180 شود مثلث ها شرط دیلانی را براورده می کنند. این یک ویژگی بسیار مهم است چون ما را قادر به استفاده از تکنیک چرخاندن می کند .اگر دو مثلث شرط دیلانی را برآورده نکنند جا به جا کردن ضلع مشترک BD با ضلع مشترک AC دو مثلث تولید میکند که شرط دیلانی را براورده میکند.

الگوریتم ها[ویرایش]

الگوریتمهای زیادی برای محاسبه ی تثلیث دیلانی بر اساس عملیات سریع برای یافتن نقطه ای درون دایره محیطی مثلث و یک داده ساختار کارامد برای ذخیره سای مثلث ها و اضلاع وجود دارد. در دو بعد یک راه برای فهمیدن اینکه آیا نقطه d درون دایره محیطی A و B و C قرار دارد محاسبه دترمینان این ماتریس به ما نشان می دهد.[۴] .

\begin{vmatrix}
A_x & A_y & A_x^2 + A_y^2 & 1\\
B_x & B_y & B_x^2 + B_y^2 & 1\\
C_x & C_y & C_x^2 + C_y^2 & 1\\
D_x & D_y & D_x^2 + D_y^2 & 1
\end{vmatrix} = \begin{vmatrix}
A_x - D_x & A_y - D_y & (A_x^2 - D_x^2) + (A_y^2 - D_y^2) \\
B_x - D_x & B_y - D_y & (B_x^2 - D_x^2) + (B_y^2 - D_y^2) \\
C_x - D_x & C_y - D_y & (C_x^2 - D_x^2) + (C_y^2 - D_y^2)
\end{vmatrix} > 0

. وقتی A و B و C به ترتیب پاد ساعت گرد مرتب شوند این دترمینان مثبت است اگر و تنها اگر d درون دایره محیطی باشد .

الگوریتم چرخاندن[ویرایش]

همان طور که در بالا ذکر شد اگر یک مثلث غیر دیلانی باشد ما می توانیم یکی از ضلع های ان را بچرخانیم کنیم. این منجر به یک الگوریتم راحت می شود : هر تثلیث از نقاط را بسازید و سپس اضلاع را بچرخانید تا زمانی که هیچ مثلثی غیر دیلانی نباشد. متاسفانه این عملیات ازین (O(n2 چرخاندن ضلع لازم دارد و به سه یا بیش از آن قابل تعمیم نیست.[۲].

افزایشی[ویرایش]

آسان ترین ترین راه برای محاسبه کارامد تثلیث دیلانی افزودن مکرر راس در یک زمان و تثلیث مجدد قسمت های تغییر یافته گراف است. وقتی یک راس v اضافه می شود ما مثلث شامل v را به سه قسمت تقسیم میکنیم سپس الگوریتم چرخاندن را اعمال می کنیم اگر اینکار به صورت اشتباه انجام شود از (O(n مرتبه زمان میبرد. ما بین تمام مثلث ها جست و جو کرده تا v را پیدا کنیم سپس هر مثلث را یکبار میچرخانیم پس زمان اجرا کلی از اردر (O(n2 است .
اگر ما راس هایی به صورت تصادفی وارد کنیم معلوم میشود (با شواهد پیچیده) که هر ورود به طور متوسط فقط (O(1 مثلث را میچرخاند - با و جود اینکه امکان دارد گاهی اوقات تعداد بیشتری را بچرخاند[۵]. این هنوز زمان یافتن مکان نقطه را قابل بهبود می گذارد .ما می توانیم تاریخچه تقسیم ها و چرخاندن های انجام شده را ذخیره کنیم: هر مثلث یک اشاره گر به دو یا سه مثلث که جایگزین آن شده اند را ذخیره می کند .برای یافتن مثلثی که v را در بر دارد ما از مثلث پایه شروع می کنیم و اشاره گری که به مثلث شامل v اشاره می کند را دنبال می کنیم تا جایی که به مثلثی برسیم که هنوز جایگزین نشده است به طور متوسط این عملیات (O(log n زمان می برد . برای تمام راس ها این عملیات ازین (O(n logn زمان می برد[۲] . در حینی که این تکنیک به ابعاد بالا تر تعمیم می یابد (همانطور که توسط ادلزبرونر و شاح ثابت شده[۶]) ) زمان اجرا می تواند نسبت به بعد نمایی رشد کند اگر تثلیث دیلانی نهایی کوچک باشد.
الگوریتم بویر واتسون یک رویکرد ساختار افزایشی دیگر را ارائه می دهد این رویکرد جایگزینی برای ضلع چرخان برای محاسبه ی مثلث های دیلانی شامل یک راس تازه وارد شده می باشد.

تبدیل به زیر مسئله ها:[ویرایش]

الگوریتم تبدیل به زیر مسئله ها برای تثلیث ها در ابعاد دو توسط لیی و شاختر ابداع شد و توسط گی باس و استولفی[۷] بهبود داده شد و بعد ها توسط دویر.در این الگوریتم مکررا خطی برای تقسیم راس ها به دو مجموعه رسم میشود.تثلیث دیلانی برای هر مجموعه محاسبه می شود و سپس دو مجموعه در طول خط تقسیم ترکیب می شوند با استفاده چند شگرد هوشمندانه عملیات ترکیب می تواند در زمان (O(n انجام شود بنا بر این زمان اجرا کل این (O(n logn است[۸] . برای گونه خاصی مشخصی از مجموعه نقاط از قبیل توزیع یکنواخت تصادفی با انتخاب هوشمند خطوط تقسیم زمان مورده انتظار می تواند به (O(nlog logn کاهش یابد در حالی که هنوز اجرای بدترین حالت را در اختیار دارد. الگوریتم تبدیل به زیر مسئله ها برای اجرای یک تثلیث در d بعد در قالب "دی وال : یک الگوریتم سریع تقسیم وغلبه تثلیث دیلانی در Ed"" توسط سیگنونی و منتانی و اسکوپینو ارائه شده است[۹] .
تقسیم و غلبه نشان داده که سریع ترین تکنیک تولید DT است[۱۰][۱۱].

خط جاروب[ویرایش]

الگوریتم شانس از تکنیک خط جاروب برای رسیدن به زمان اجرا (O(n logn در حالت صفحه ای استفاده می کنند.

پوش جاروب[ویرایش]

پوش جاروب[۱۲] یک تکنیک ترکیبی برای تثلیث دیلانی دو بعدی است که از یک جاروب تکثیر شعاعی (به ترتیب بوجود امده از مجموعه نقاط دو بعدی مرتب شده با فرض تثلیث بدون تداخل ) استفاده می کند که با یک قدم چرخاندن مثلث مکرر تزویج شده است .همچنین یک متغیر منطقی صحیح دقیق برای الگوریتم ارائه میشود.

کاربرد ها[ویرایش]

تثلیث دیلانی برای صد نقطه تصادفی در صفحه.


درخت پوشای حداقل اقلیدسی یک مجموعه ای از نقطه ها زیرمجموعه ای از تثلیث دیلانی همان نقاط می باشد و این میتواند در کارایی محاسبات استفاده شود. تثلیث دیلانی برای مدل سازی زمینه و اشیای دیگر که به عنوان مجموعه ای از نقاط داده شده اند یک مجموعه ی خوبی از مثلث ها را می دهد که می تواند به عنوان چند ضلعی در مدل استفاده شود.به طور خاص تثلیث دیلانی سعی دارد از مثلث های باریک استفاده نکند(که آنها درمقایسه با مساحت شان دایره محیطی های بزرگی دارند). تثلیث دیلانی می تواند برای مشخص کردن چگالی یا شدت نقاط در مدل سازی نقاط به معنی Delaunay tessellation field estimator استفاده شوند. تثلیث دیلانی به دلیل تضمین زاویه و به دلیل الگوریتم های مثلث بندی سریع توسعه یافته اغلب مورد استفاده برای ایجاد شبکه برای حل فضای گسسته مانند روش المان محدود و روش حجم محدود که از روش های شبیه سازی فیزیکی قرار می گیرند. به طور معمول، دامنه شبکه بندی به عنوان یک مجموعه مختلط ساده ی درشت مشخص شده است، برای شبکه به صورت عددی پایدار ، باید آن خالص سازی کرد. به عنوان مثال با استفاده از الگوریتم راپرت. افزایش محبوبیت استفاده از روش المان محدود و تکنیک های روش المان مرزی انگیزه برای بهبود الگوریتم های ی درگیر به صورت خودکار را افزایش می دهد. با این حال، همه ی این الگوریتم ها می توانند عناصر شبکه نامنظم و حتی غیر قابل استفاده ایجاد کند. خوشبختانه، چندین روش وجود دارد که می تواند یک شبکه بندی موجود را بگیرد و آن را بهبود کیفیت بدهد. به عنوان مثال، صاف کردن ( همچنین به عنوان پالایش شبکه بندی نیز نامیده می شود) یکی از این روش هاست، که انباشتگی های محل گره ها را به منظور به حداقل رساندن اعوجاج عنصر می باشد . روش شبکه کشیده اجازه می دهد تا نسلی از شبکه شبه منظم که با ضوابط دیلانی سنخیت دارند و راه حل های یک مرحله ا ی دارند رشد کنند.


منابع[ویرایش]

  1. B. Delaunay: Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793–800, 1934
  2. ۲٫۰ ۲٫۱ ۲٫۲ de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications. Springer-Verlag. ISBN 978-3-540-77973-5. 
  3. Seidel, R. (1995). "The upper bound theorem for polytopes: an easy proof of its asymptotic version". Computational Geometry 5 (2): 115–116. DOI:10.1016/0925-7721(95)00013-Y. 
  4. Guibas, Lenoidas; Stolfi, Jorge (1985-04-01). "Primitives for the manipulation of general subdivisions and the computation of Voronoi". ACM. p. 107. Retrieved 2009-08-01. 
  5. Guibas, L.; D. Knuth; M. Sharir (1992). "Randomized incremental construction of Delaunay and Voronoi diagrams". Algorithmica 7: 381–413. DOI:10.1007/BF01758770. 
  6. Edelsbrunner, Herbert; Nimish Shah (1996). "Incremental Topological Flipping Works for Regular Triangulations". Algorithmica 15 (3): 223–241. DOI:10.1007/BF01975867. 
  7. Computing Constrained Delaunay Triangulations
  8. Leach, G. (June 1992). Improving Worst-Case Optimal Delaunay Triangulation Algorithms.. CiteSeerX: 10.1.1.56.2323. 
  9. Cignoni, P.; C. Montani; R. Scopigno (1998). "DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed". Computer-Aided Design 30 (5): 333–341. DOI:10.1016/S0010-4485(97)00082-1. 
  10. A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf
  11. http://www.cs.cmu.edu/~quake/tripaper/triangle2.html
  12. S-hull

ارجعات بیرونی[ویرایش]

  • Delaunay triangulation in CGAL, the Computational Geometry Algorithms Library:
  • "Delaunay triangulation". Wolfram MathWorld. Retrieved April 2010. 
  • "Qhull". Retrieved April 2010.  — Code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
  • Shewchuk, Jonathan Richard. "Triangle". Retrieved April 2010.  – A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator
  • Kumar, Piyush; Mohanty, Somya. "Triangle++".  – A C++ wrapper on Triangle
  • "Poly2Tri". Google Code. Retrieved April 2010.  – A sweepline Constrained Delaunay Triangulation (CDT) library, available in ActionScript 3, C, C++, C#, Go, Haxe, Java, Javascript, Python and Ruby