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

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

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

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