الگوریتم امروز

وبلاگ تخصصی الگوریتم

الگوریتم امروز

وبلاگ تخصصی الگوریتم

وبلاگ علمی و مخصوص مباحث الگوریتمی است.
نظر خصوصی نگذارید چون جواب نمی‌دهم نظر عمومی بگذارید بدون نام هم که باشد همانجا جواب می‌دهم.

بایگانی

تمرین عملی هندسه محاسباتی

يكشنبه, ۳ فروردين ۱۳۹۹، ۰۱:۴۲ ب.ظ

الگوریتم جاروب صفحه برای پیدا کردن تقاطع پاره‌خط‌ها را پیاده‌سازی کنید:
http://page.mi.fu-berlin.de/panos/cg13/l03.pdf

می‌خواهم برای اعداد اعشاری پیاده‌سازی کنم، به جای نقطه تقاطع معادله‌ی خط‌ها را نگه دارم. اینجا آدم تازه می‌فهمد که مقاله‌های لافر در مورد حفظ کردن ساختار توپولوژیکی جواب در حضور داده‌های نادقیق به چه دردی می‌خورد: اگر تقاطعی باشد در کدام جهت رندش کنیم که بدانیم هیچ تقاطعی را از دست نداده‌ایم. البته فکر کنم دقیقاً برای این سوال بررسی نشده. شاید روی آن کار کنیم.

فقط اگر کلید داشته باشیم می‌توانیم از کتابخانه استاندارد استفاده کنیم، چون کلاً آن ساختمان داده‌ها برای اعداد طراحی شده‌اند. حالا مثلاً در الگوریتم جاروب صفحه ما داریم ترتیب یک سری پاره‌خط را نگه می‌داریم که به مرور که جلو می‌رویم ترتیبشان تغییر می‌کند. مشکل این است که چطوری با عدد ترتیب به پاره‌خط‌ها بدهیم که بتوانیم دو تای مجاور را بعد از یک تقاطع جابه‌جا کنیم بدون اینکه بخواهیم دوباره ترتیب همه‌ی پاره‌خط‌ها را عوض کنیم. یک راه‌حل این است که همان اعداد ۱ تا n را بدهیم و برای جابه‌جا کردن هر دو پاره‌خط را حذف کنیم و کلیدهایشان را جابه‌جا کنیم و دوباره اضافه کنیم. مشکل این کار وقتی است که می‌خواهیم نقطه جدید اضافه کنیم، باید روی درخت جستجو کنیم بر حسب y، ولی فقط ترتیب پاره‌خط‌ها را داریم. می‌توانیم تابع مقایسه را دوباره بنویسیم که یک پارامتر دیگه بگیرد که نگه دارد کدام نقطه جدید است و بر اساس y آن مقایسه کند.

موافقین ۰ مخالفین ۰ ۹۹/۰۱/۰۳
سپیده آقاملائی

نظرات  (۰)

هیچ نظری هنوز ثبت نشده است

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی