پیش‌نویس:لیست لبه های متصل دو برابر

لیست لبه‌های متصل مضاعف (DCEL)، همچنین به عنوان ساختار داده نیمه لبه شناخته می‌شود، یک ساختار داده برای نشان دادن تعبیه یک نمودار مسطح در صفحه و پلی توپ‌ها به صورت سه بعدی است. این ساختار داده دستکاری کارآمد اطلاعات توپولوژیکی مرتبط با اشیاء مورد نظر (راس‌ها، لبه‌ها، وجه‌ها) را فراهم می‌کند. در بسیاری از الگوریتم‌های هندسه محاسباتی برای رسیدگی به بخش‌های فرعی چند ضلعی صفحه، که معمولاً نمودارهای خط مستقیم مسطح (PSLG) نامیده می‌شوند، استفاده می‌شود. به عنوان مثال، نمودار Voronoi معمولاً با یک DCEL در داخل یک جعبه مرزی نشان داده می‌شود.

این ساختار داده در ابتدا توسط مولر و پرپاراتا^[۱] برای نمایش چندوجهی محدب سه بعدی پیشنهاد شد. نسخه‌های ساده‌شده ساختار داده، همان‌طور که در اینجا توضیح داده شد، فقط گراف‌های متصل را در نظر می‌گیرند، اما ساختار DCEL ممکن است برای رسیدگی به گراف‌های قطع‌شده و همچنین با معرفی لبه‌های ساختگی بین اجزای جداشده گسترش یابد.

ساختار داده‌ها[ویرایش]

هر نیم لبه دقیقاً یک نیم لبه قبلی، نیم لبه بعدی و دوقلو دارد.

DCEL چیزی بیش از یک لیست دو طرفه از لبه‌ها است. در حالت کلی، یک DCEL حاوی یک رکورد برای هر یال، رأس و وجه زیربخش است. هر رکورد ممکن است حاوی اطلاعات اضافی باشد، به عنوان مثال، یک چهره ممکن است حاوی نام منطقه باشد. هر لبه معمولاً دو وجه را محدود می‌کند و بنابراین، راحت است که هر یال را به عنوان دو "نیم لبه" در نظر بگیریم (که در تصویر سمت راست با دو یال با جهت مخالف، بین دو راس، نشان داده شده‌اند). هر نیم لبه با یک وجه "مرتبط" است و بنابراین یک اشاره گر به آن وجه دارد. تمام نیمه لبه‌های مرتبط با یک چهره در جهت عقربه‌های ساعت یا خلاف جهت عقربه‌های ساعت هستند. به عنوان مثال، در تصویر سمت راست، تمام نیمه لبه‌های مرتبط با وسط وسط (یعنی نیمه لبه‌های "داخلی") خلاف جهت عقربه‌های ساعت هستند. یک نیم لبه دارای یک اشاره گر به نیمه لبه بعدی و نیم لبه قبلی همان وجه است. برای رسیدن به وجه دیگر می‌توانیم به سمت دوقلو نیم لبه رفته و سپس روی دیگر را تراورس کنیم. هر نیم یال نیز یک اشاره گر به راس مبدأ خود دارد (راس مقصد را می‌توان با پرس و جو مبدأ دوقلو یا نیم یال بعدی به دست آورد).

هر رأس شامل مختصات رأس است و همچنین یک اشاره گر به یک یال دلخواه که راس را به عنوان مبدأ دارد ذخیره می‌کند. هر صورت یک اشاره گر را در نیمی از لبه‌های مرز بیرونی خود ذخیره می‌کند (اگر صورت نامحدود باشد، اشاره گر صفر است). همچنین فهرستی از لبه‌های نیمه دارد، یکی برای هر سوراخی که ممکن است در صورت رخ دهد. اگر رئوس یا وجه‌ها اطلاعات جالبی در خود ندارند، نیازی به ذخیره‌سازی آنها نیست، بنابراین در فضا صرفه جویی می‌شود و پیچیدگی ساختار داده کاهش می‌یابد.

جستارهای وابسته[ویرایش]

ساختار داده چهار لبه
لیست چهره با پیوند دوگانه
لبه بالدار
نقشه ترکیبی

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

↑ Muller, D. E.; Preparata, F. P. (1978). "Finding the Intersection of Two Convex Polyhedra". Theoretical Computer Science. 7 (2): 217–236. doi:10.1016/0304-3975(78)90051-8. {{cite journal}}: |hdl-access= requires |hdl= (help)

[1] Muller, D. E.; Preparata, F. P. (1978). "Finding the Intersection of Two Convex Polyhedra". Theoretical Computer Science. 7 (2): 217–236. doi:10.1016/0304-3975(78)90051-8. {{cite journal}}: |hdl-access= requires |hdl= (help)

[۱]