streamalism.org

1. סקירה כללית

במדריך זה נחקור את המושג חיפוש אחר שכנים במרחב דו מימדי. לאחר מכן נעבור על יישומה ב- Java.

2. חיפוש חד ממדי לעומת חיפוש דו מימדי

אנו יודעים שחיפוש בינארי הוא אלגוריתם יעיל למציאת התאמה מדויקת ברשימת פריטים תוך שימוש בגישה של חלוקה וכיבוש.

בואו עכשיו שקול אזור דו מימדי שבו כל פריט מיוצג על ידי קואורדינטות (נקודות) XY במישור.

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

נבחן אלטרנטיבה למבנה נתוני העץ הבינארי בחלק הבא.

3. Quadtree

עץ רביעי הוא מבנה נתוני עץ מרחבי שבו לכל צומת יש ארבעה ילדים בדיוק. כל ילד יכול להיות נקודה או רשימה המכילה ארבע עצמות משנה.

א נְקוּדָה מאחסן נתונים - למשל, קואורדינטות XY. א אזור מייצג גבול סגור שבתוכו ניתן לאחסן נקודה. הוא משמש להגדרת שטח ההישג של ארבע קוואדר.

בואו נבין זאת יותר בעזרת דוגמה של 10 קואורדינטות בסדר שרירותי כלשהו:

(21,25), (55,53), (70,318), (98,302), (49,229), (135,229), (224,292), (206,321), (197,258), (245,238)

שלושת הערכים הראשונים יאוחסנו כנקודות מתחת לצומת השורש כפי שמוצג בתמונה השמאלית ביותר.

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

כל אחד מהרביעים הללו יכול לאחסן שלוש נקודות ובנוסף להכיל ארבעה רביעים בתחומו. ניתן לעשות זאת רקורסיבית, וכתוצאה מכך נוצר עץ של רביעים, שם מבנה הנתונים של ארבע העץ מקבל את שמו.

בתמונה האמצעית לעיל, אנו יכולים לראות את הרבעים שנוצרו מצומת השורש וכיצד נשמרות ארבע הנקודות הבאות ברביעים אלה.

לבסוף, התמונה הימנית ביותר מראה כיצד רבע אחד מחולק שוב בכדי להכיל יותר נקודות באזור, בעוד שהרבעים האחרים עדיין יכולים לקבל את הנקודות החדשות.

כעת נראה כיצד ליישם את האלגוריתם הזה ב- Java.

4. מבנה נתונים

בואו ניבנה מבנה נתונים של ארבע העץ. נצטרך שלוש מחלקות תחום.

ראשית, ניצור נְקוּדָה בכיתה לאחסון הקואורדינטות XY:

נקודה בכיתה ציבורית {float private x; צף פרטי y; נקודה ציבורית (צף x, צף y) {this.x = x; this.y = y; } // getters & toString ()}

שנית, בואו ניצור א אזור בכיתה להגדרת גבולות הרבע:

מעמד ציבורי אזור {צף פרטי x1; צף פרטי y1; צף פרטי x2; צף פרטי y2; אזור ציבורי (לצוף x1, לצוף y1, לצוף x2, לצוף y2) {this.x1 = x1; this.y1 = y1; this.x2 = x2; this.y2 = y2; } // getters & toString ()}

לבסוף, שיהיה לנו QuadTree בכיתה לאחסון נתונים כ- נְקוּדָה מקרים וילדים כמו QuadTree שיעורים:

מחלקה ציבורית QuadTree {גמר סטטי פרטי פרטי MAX_POINTS = 3; אזור אזור פרטי; נקודות רשימה פרטיות = ArrayList חדש (); רשימה פרטית quadTrees = ArrayList חדש (); QuadTree ציבורי (אזור אזור) {this.area = שטח; }}

לייצר א QuadTree אובייקט, אנו מציינים את זה אֵזוֹר משתמש ב אזור בכיתה דרך הקונסטרוקטור.

5. אלגוריתם

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

5.1. שיטות עוזר

בואו נשנה את שלנו אזור מעמד.

ראשית, תהיה לנו שיטה containPoint ל ציין אם נתון נְקוּדָה נופל בתוך או מחוץ לא האזור אֵזוֹר:

מכיל בוליאני ציבוריPoint (נקודת נקודה) {חזרה point.getX ()> = this.x1 && point.getX () = this.y1 && point.getY () <this.y2; }

בשלב הבא, תהיה לנו שיטה עושה Overlap ל ציין אם נתון אזור חופף לאחר אזור:

הבוליאני הציבורי doesOverlap (Region testRegion) {if (testRegion.getX2 () this.getX2 ()) {return false; } אם (testRegion.getY1 ()> this.getY2 ()) {return false; } אם (testRegion.getY2 () <this.getY1 ()) {return false; } להחזיר נכון; }

לבסוף, בואו ניצור שיטה getQuadrant ל לחלק טווח לארבעה רביעים שווים והחזר אחד שצוין:

אזור ציבורי getQuadrant (int quadrantIndex) {float quadrantWidth = (this.x2 - this.x1) / 2; quadrantHeight לצוף = (this.y2 - this.y1) / 2; // 0 = SW, 1 = NW, 2 = NE, 3 = מתג SE (quadrantIndex) {case 0: להחזיר אזור חדש (x1, y1, x1 + quadrantWidth, y1 + quadrantHeight); מקרה 1: להחזיר אזור חדש (x1, y1 + quadrantHeight, x1 + quadrantWidth, y2); מקרה 2: להחזיר אזור חדש (x1 + quadrantWidth, y1 + quadrantHeight, x2, y2); מקרה 3: להחזיר אזור חדש (x1 + quadrantWidth, y1, x2, y1 + quadrantHeight); } להחזיר אפס; }

5.2. אחסון נתונים

כעת אנו יכולים לכתוב את ההיגיון שלנו לאחסון נתונים. נתחיל בהגדרת שיטה חדשה addPoint על QuadTree בכיתה להוסיף חדש נְקוּדָה. שיטה זו תחזור נָכוֹן אם נקודה נוספה בהצלחה:

addPoint בוליאני ציבורי (נקודת נקודה) {// ...}

לאחר מכן, בואו נכתוב את ההיגיון בכדי לטפל בנקודה. ראשית, עלינו לבדוק אם הנקודה כלולה בגבול ה- QuadTree למשל. אנחנו גם צריכים להבטיח שה- QuadTree מופע לא הגיע ליכולתו של MAX_POINTS נקודות.

אם שני התנאים מתקיימים, נוכל להוסיף את הנקודה החדשה:

if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); לחזור אמיתי; }}

מצד שני, אם הגענו ל MAX_POINTS ערך, ואז עלינו להוסיף את החדש נְקוּדָה לאחת מרבעי המשנה. לשם כך אנו עוברים דרך הילד quadTrees רשום והתקשר לאותו דבר addPoint שיטה שתחזיר א נָכוֹן ערך על תוספת מוצלחת. ואז אנחנו יוצאים מהלולאה מיד כ צריך להוסיף נקודה בדיוק לרבע אחד.

אנו יכולים לתמצת את כל ההיגיון הזה בשיטת עוזר:

addPointToOneQuadrant בוליאני פרטי (נקודת נקודה) {isPointAdded בוליאני; עבור (int i = 0; i <4; i ++) {isPointAdded = this.quadTrees.get (i) .addPoint (point); אם (isPointAdded) להחזיר true; } להחזיר שקר; }

בנוסף, תהיה לנו שיטה שימושית createQuadrants לחלק את העץ הנוכחי לארבעה רביעים:

חלל פרטי createQuadrants () {אזור אזור; עבור (int i = 0; i <4; i ++) {region = this.area.getQuadrant (i); quadTrees.add (QuadTree חדש (אזור)); }}

אנו קוראים לשיטה זו ליצור רביעים רק אם איננו יכולים להוסיף נקודות חדשות. זה מבטיח שמבנה הנתונים שלנו ישתמש בשטח זיכרון מיטבי.

אם מחברים את הכל, יש לנו את העדכון addPoint שיטה:

addPoint בוליאני ציבורי (נקודת נקודה) {if (this.area.containsPoint (point)) {if (this.points.size () <MAX_POINTS) {this.points.add (point); לחזור אמיתי; } אחר {if (this.quadTrees.size () == 0) {createQuadrants (); } להחזיר את addPointToOneQuadrant (נקודה); }} להחזיר שקר; }

5.3. חיפוש נתונים

הגדרת מבנה העץ הארבע שלנו לאחסון נתונים, כעת אנו יכולים לחשוב על ההיגיון לביצוע חיפוש.

כשאנחנו מחפשים למצוא פריטים סמוכים, אנחנו יכולים ציין a searchRegion כנקודת ההתחלה. לאחר מכן, אנו בודקים אם הוא חופף לאזור השורש. אם כן, אנו מוסיפים את כל נקודות הילד שלה שנופלות בתוך ה- searchRegion.

לאחר אזור השורש, אנו נכנסים לכל אחד מהרבעים וחוזרים על התהליך. זה נמשך עד שנגיע לקצה העץ.

בואו לכתוב את ההיגיון הנ"ל כשיטה רקורסיבית ב- QuadTree מעמד:

חיפוש ברשימה ציבורית (חיפוש אזור באזור, התאמות רשימה) {if (התאמות == null) {התאמות = ArrayList חדש (); } אם (! this.area.doesOverlap (searchRegion)) {התאמות חוזרות; } אחר {עבור (נקודת נקודה: נקודות) {אם (searchRegion.containsPoint (נקודה)) {matches.add (נקודה); }} אם (this.quadTrees.size ()> 0) {for (int i = 0; i <4; i ++) {quadTrees.get (i) .search (searchRegion, matches); }}} התאמות חוזרות; }

6. בדיקות

עכשיו שיש לנו את האלגוריתם שלנו, בואו נבדוק אותו.

6.1. אכלוס הנתונים

ראשית, בואו לאכלס את העץ הארבע באותם 10 קואורדינטות בהן השתמשנו קודם:

אזור אזור = אזור חדש (0, 0, 400, 400); QuadTree quadTree = QuadTree חדש (אזור); צף [] [] נקודות = צף חדש [] [] {{21, 25}, {55, 53}, {70, 318}, {98, 302}, {49, 229}, {135, 229}, {224, 292}, {206, 321}, {197, 258}, {245, 238}}; עבור (int i = 0; i <points.length; i ++) {נקודה נקודה = נקודה חדשה (נקודות [i] [0], נקודות [i] [1]); quadTree.addPoint (נקודה); }

6.2. חיפוש טווח

לאחר מכן, בואו לבצע חיפוש טווח באזור המוקף בקואורדינטות הגבול התחתון (200, 200) ובקואורדינטות הגבול העליון (250, 250):

אזור searchArea = אזור חדש (200, 200, 250, 250); תוצאת רשימה = quadTree.search (searchArea, null);

הפעלת הקוד תיתן לנו קואורדינטות סמוכות הכלולות באזור החיפוש:

[[245.0 , 238.0]]

בואו ננסה אזור חיפוש אחר בין הקואורדינטות (0, 0) ו- (100, 100):

אזור searchArea = אזור חדש (0, 0, 100, 100); תוצאת רשימה = quadTree.search (searchArea, null);

הפעלת הקוד תיתן לנו שני קואורדינטות סמוכות לאזור החיפוש שצוין:

[[21.0 , 25.0], [55.0 , 53.0]]

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

ואז, מכל הנקודות המתקבלות של פעולת החיפוש, אנחנו יכולים לחשב את המרחקים האוקלידיים בין הנקודות הנתונות ולמיין אותם כדי להשיג את השכנים הקרובים ביותר.

7. מורכבות זמן

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

8. מסקנה

במאמר זה הבנו לראשונה את המושג עץ ארבע על ידי השוואתו לעץ בינארי. לאחר מכן ראינו כיצד ניתן להשתמש בו ביעילות לאחסון נתונים המפוזרים על פני שטח דו-ממדי.

לאחר מכן ראינו כיצד לאחסן נתונים ולבצע חיפוש טווח.

כמו תמיד, קוד המקור עם הבדיקות זמין ב- GitHub.