בדוק אם שני מלבנים חופפים בג'אווה
1. סקירה כללית
במדריך מהיר זה נלמד לפתור בעיה אלגוריתמית של בדיקה האם שני המלבנים הנתונים חופפים.
נתחיל בהסתכלות על הגדרת הבעיה ונבנה בהדרגה פיתרון.
לבסוף, ניישם את זה ב- Java.
2. הגדרת בעיה
נניח שיש לנו שני מלבנים נתונים - r1 ו r2. עלינו לבדוק אם יש לפחות נקודה משותפת אחת r1 ו r2. אם כן, זה פשוט אומר ששני המלבנים האלה חופפים.
בואו נסתכל על כמה דוגמאות:
אם נבחין במקרה האחרון, המלבנים r1 ו r2 אין גבולות מצטלבים. ובכל זאת, הם חופפים מלבנים כמו כל נקודה r1 הוא גם נקודה ב r2.
3. הגדרה ראשונית
כדי לפתור בעיה זו, ראשית עלינו להתחיל בהגדרת מלבן באופן פרוגרמטי. מלבן יכול להיות מיוצג בקלות על ידי הקואורדינטות התחתונות משמאל ומשמאל למעלה:
מלבן בכיתה ציבורית {Point PointLeft פרטי; נקודה פרטית topRight; // constructor, getters and setters בוליאני isOflapping (מלבן אחר) {...}}איפה נְקוּדָה הוא מחלקה המייצגת נקודה (x, y) בחלל:
נקודה בכיתה ציבורית {int int private; פרטית int y; // בונה, גטרים וקובעים}בהמשך נגדיר isOflapping (מלבן אחר) השיטה שלנו מַלבֵּן בכיתה כדי לבדוק אם היא חופפת למלבן נתון אחר - אַחֵר.
4. פיתרון
השניים מלבנים נתון לא יחפפו אם אחד מהתנאים שלהלן נכון:
- אחד משני המלבנים נמצא מעל הקצה העליון של המלבן השני
- אחד משני המלבנים נמצא בצד שמאל של הקצה השמאלי של המלבן השני
בכל המקרים האחרים, שני המלבנים יחפפו זה עם זה. כדי לשכנע את עצמנו, אנחנו תמיד יכולים להוציא כמה דוגמאות.
5. יישום ג'אווה
עכשיו, אחרי שאנחנו מבינים את הפיתרון, בואו ניישם את שלנו isOflapping () שיטה:
ציבורי בוליאני הוא Overlapping (מלבן אחר) {if (this.topRight.getY () other.topRight.getY ()) {return false; } אם (this.topRight.getX () other.topRight.getX ()) {return false; } להחזיר נכון; }שֶׁלָנוּ isOflapping () שיטה ב מַלבֵּן הכיתה חוזרת שֶׁקֶר אם אחד המלבנים נמצא מעל או לצד שמאל של השני, נָכוֹן אחרת.
כדי לברר אם מלבן אחד נמצא מעל השני, אנו משווים את זה קואורדינטות y. כמו כן, אנו משווים את קואורדינטות x כדי לבדוק אם מלבן אחד נמצא משמאל לשני.
6. מסקנה
במאמר קצר זה למדנו כיצד לפתור בעיה אלגוריתמית של מציאת האם שני המלבנים הנתונים חופפים זה לזה. הוא משמש כאסטרטגיית זיהוי התנגשות עבור שני עצמים מלבניים.
כרגיל, קוד המקור כולו זמין ב- Github.
