איך בודקים חפיפה בין 2 מלבנים

[אלירן שני]

איך בודקים חפיפה בין 2 מלבנים ../images/Emo35.gif

היי, אני זקוק לאלגוריתם/שיטה הפשוט/ה והקצר/ה ביותר על מנת לבדוק האם שני מלבנים נתונים חופפים אחד את השני (באופן חלקי או מלא, זה לא משנה) ידועות לי הקורדינטות של כל פינה בכל אחד מהמלבנים. ניסיתי להציב מספר תנאים לבדיקה אך בכל פעם גיליתי מקרה חדש של חפיפה שהתנאים לא תופסים.... אשמח מאד לעזרה בנושא, תודה מראש

 

[yossiea]

אני חושב שקל יותר...

לפתור את זה על ידי בדיקת קווים חותכים במקום מלבנים חופפים כי הרי מלבנים מורכבים מארבעה קווים המתחברים יחדיו אזי אם ידועים כל קואורדינטות המלבנים. אם צלע אחת חותכת צלע מלבן אחר אזי בטוח שיש חפיפה. כדי לדעת אם צלע נכנסת לתוך צלע אחרת. הנוסחה בערך... היא ככה: אם הקואורדינטות נקראות x,y (כלומר x1,x2 וכן y1,y2 עבור 2 הקצוות של הצלע) ו-u,v עבור הצלע של המלבן השני אז לפי משוואת הישר אפשר לקבל: b1 = (y2-y1)/(x2-x1) b2 = (v2-v1)/(u2-u1) a1 = y1-b1*x1 a2 = v1-b2*u1 xi = -(a1-a2)/(b1-b2) yi = a1+b1*xi עכשיו נשאר רק למצוא האם (x1-xi)*(xi-x2)>=0 או האם (u1-xi)*(xi-u2)>=0 וכן הלאה האם (y1-yi)*(yi-y2)>=0 וכן (v1-yi)*(yi-v2)>=0. הערות: שים לב שצריך להוסיף תנאי בדיקה למקרה של חלוקה באפס למנוע שגיאה. כנראה שאת הבדיקה הזו צריך לעשות עבור כל צלע (כלומר כפול ארבע) העסק יסתבך במקרה של יותר משני מלבנים או במצולעים וכו'. יכול להיות שיש אלגוריתם יותר יעיל. אני לא מכיר בכל אופן. תחפש תחת הערך: Line Intersection בטוח תמצא משהו. בהצלחה.