البته اگر از روش های پردازش تصویر برای اینکار استفاده کنید به نظرم هم بار محاسباتی شما سنگین میشه و هم روش صحیح برای این مسئله نیست . چون فرمودید نقاط تقاطع را دارید بخش هندسی داستان حل شده است فقط بخش الگوریتم این مسئله می مونه.
برای این مسئله شما باید یک گراف را تجسم کنید که نقاط تقاطع به عنوان گره و پاره خط بین این نقاط تقاطع هم یال ها گراف است.چون خطوط اصلی موجود هستند نقاط تقاطع را در هر خط با توجه به یکی از نقاط ابتدایی یا انتهایی مرتب کنید این کار را برای تمام خطوط انجام بدید.سپس هر نقطه تقاطع را به گراف تحت عنوان یک نود اضافه کنید.اطلاعاتی که را در هر نود ذخیره می کنید شامل داده های زیر است.
1- هر نقطه تقاطع از 2 خط تشکیل شده که شاخص آنها به صورت tuple نگهداری میشه.(l1,l2)
2-تعداد همسایگان هر نقطه تقطع که این تعداد همسایه ها می تونه به شرط حداقل یک چهار ضلعی از 2 تا 4 می تونه متغیر باشه.(neighbor_count)
پس از تکمیل کردن گراف حال از طریق الگوریتم DFS یا مشتقات آن( به وفور در همین سات پیدا میشه) گراف را به صورت برگشتی پیمایش کنید.
شرایط برای پیمایش نقاط ابتدا برای استخراج هر مستطیل :هر نقطه ابتدایی باید2=< neighbor_count باشد .
شرایط خاتمه پیمایش : زمانیکه در گراف گره ای با 2=< neighbor_count وجود نداشته باشد چهار ضلعی جهت استخراج باقی نمانده.
پس از انتخاب نقطه اول نقاط بعدی حتما باید در همسایگی نقطه قبلی باشند یعنی فاصله l2,l1 گره بعدی با l1,l2 گره فعلی برابر یک باشد.
خطوط l2 و l1 نمی توانند برای گره های بعدی 3 بار متوالی یکسان باشند.
گره آخر در چهار ضلغی باید گره اول باشد اگر نباشد گره های همسایه دیگر بررسی شود.
پس از پیمایش گره ها از هر کدام یک واحد کم شود.
گره های همسایه ای که دارای 1=< neighbor_count باشند پیمایش می شوند.