مثلث‌بندی دیلانی: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۲۱ مهٔ ۲۰۱۴، ساعت ۲۰:۱۰

در ریاضیات و هندسه‌ی محاسباتی، یک مثلث‌بندی دیلانی برای یک مجموعه از نقاط به نام 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 (برای مثال برا ی یک مجموعه نقاط در ℝ³ هیچ سه نقطه ای روی یک خط وجود ندارند ، هیچ چهار نقطه ای روی یک صفحه ، هیچ چهار نقطه ای روی یک دایره و هیچ 5 نقطه ای روی یک کره وجود ندارد) مسئله پیدا کردن تثلیث دیلانی برای گروهی از نقاط در فضای ی بعدی اقلیدسی قابل تبدیل به مسئله ی یافتن پوش محدب برای یک مجموعه نقاط در فضای d + 1 بعدی با دادن مختصات اضافی p|²| ، به هر نقطه p و گرفتن گوشه پایین پوش محدب و نگاشتن مجدد به فضای d بعدی با حذف مختصات اخیر است. چون پوش محدب یکتاست بنابر این تثلیث نیز یکتاست با فرض اینکه تمام اضلاع پوش محدب سیمپلکس هستند . اضلاع غیر سیمپلکس تنها زمانی پدید می آیند که d + 2 تا از نقاط اصلی روی یک ابر کرهابر کره دی بعدی باشند به عنوان مثال نقاط در جنرال پوزیشن نباشند.

ویژگی ها:

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

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

2- تثلیث دیلانی شامل O(n^{⌈d / 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 دو مثلث تولید میکند که شرط دیلانی را براورده میکند.

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

الگوریتم ها

الگوریتمهای زیادی برای محاسبه ی تثلیث دیلانی بر اساس عملیات سریع برای یافتن نقطه ای درون دایره محیطی مثلث و یک داده ساختار کارامد برای ذخیره سای مثلث ها و اضلاع وجود دارد. در دو بعد یک راه برای فهمیدن اینکه آیا نقطه 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(n² چرخاندن ضلع لازم دارد و به سه یا بیش از آن قابل تعمیم نیست.^[۲].

افزایشی

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

تبدیل به زیر مسئله ها:

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

خط جاروب

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

پوش جاروب

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

برنامه ها

منابع

↑ B. Delaunay: Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793–800, 1934
↑ ^۲٫۰ ^۲٫۱ ^۲٫۲ de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5.
↑ 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.
↑ 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.
↑ Guibas, L. (1992). "Randomized incremental construction of Delaunay and Voronoi diagrams". Algorithmica. 7: 381–413. doi:10.1007/BF01758770. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
↑ Edelsbrunner, Herbert; Nimish Shah (1996). "Incremental Topological Flipping Works for Regular Triangulations". Algorithmica. 15 (3): 223–241. doi:10.1007/BF01975867.
↑ Computing Constrained Delaunay Triangulations
↑ Leach, G. (1992). "Improving Worst-Case Optimal Delaunay Triangulation Algorithms.". CiteSeerX: 10.1.1.56.2323. {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |month= ignored (help)
↑ Cignoni, P. (1998). "DeWall: A fast divide and conquer Delaunay triangulation algorithm in E^d". Computer-Aided Design. 30 (5): 333–341. doi:10.1016/S0010-4485(97)00082-1. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
↑ A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf
↑ http://www.cs.cmu.edu/~quake/tripaper/triangle2.html
↑ S-hull

ارجعات بیرونی

Delaunay triangulation in CGAL, the Computational Geometry Algorithms Library:
- Yvinec, Mariette. "2D Triangulation". Retrieved April 2010. {{cite web}}: Check date values in: |accessdate= (help)
- Pion, Sylvain; Teillaud, Monique. "3D Triangulations". Retrieved April 2010. {{cite web}}: Check date values in: |accessdate= (help)
- Hert, Susan; Seel, Michael. "dD Convex Hulls and Delaunay Triangulations". Retrieved April 2010. {{cite web}}: Check date values in: |accessdate= (help)
"Delaunay triangulation". Wolfram MathWorld. Retrieved April 2010. {{cite web}}: Check date values in: |accessdate= (help)
"Qhull". Retrieved April 2010. {{cite web}}: Check date values in: |accessdate= (help) — Code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
Shewchuk, Jonathan Richard. "Triangle". Retrieved April 2010. {{cite web}}: Check date values in: |accessdate= (help) – 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. {{cite web}}: Check date values in: |accessdate= (help) – A sweepline Constrained Delaunay Triangulation (CDT) library, available in ActionScript 3, C, C++, C#, Go, Haxe, Java, Javascript, Python and Ruby

[Delaunay1934-1] B. Delaunay: Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793–800, 1934

[deBerg-2] ۲٫۰ ^۲٫۱ ^۲٫۲ de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). 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. (1992). "Randomized incremental construction of Delaunay and Voronoi diagrams". Algorithmica. 7: 381–413. doi:10.1007/BF01758770. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[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

[Leach1992-8] Leach, G. (1992). "Improving Worst-Case Optimal Delaunay Triangulation Algorithms.". CiteSeerX: 10.1.1.56.2323. {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |month= ignored (help)

[9] Cignoni, P. (1998). "DeWall: A fast divide and conquer Delaunay triangulation algorithm in E^d". Computer-Aided Design. 30 (5): 333–341. doi:10.1016/S0010-4485(97)00082-1. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[10] A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf

[11] ttp://www.cs.cmu.edu/~quake/tripaper/triangle2.html

[12] S-hull

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]