מושגי יסוד ב Geospatial Processing

GIS הוא קיצור משעמם של Geographical Information Systems - "מערכות מידע גיאוגרפיות", אבל חלק ממה שנעשה עם טכנולוגיות אלו הוא בכלל מגניב למדי: Waze, המפות של גוגל, GetTaxi, מערכות שליטה צבאיות, ועוד משתמשות בטכניקות של Geospatial Processing (מקור: spatial = מרחבי, נשמע כמו "ספיישל", בדומה ל Special "ספשל") בכדי להגיע לתוצאות.

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

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

כלי Geospatial קיימים מתחלקים לכמה קבוצות:

• מערכות GIS קלאסיות, המפשרות לערוך מפות, לצפות בהן, ולבצע חיתוכים ושאילתות. המערכות הנפוצות בתחום זה הן ArcGIS (בתשלום) ו QGIS (תוכנה חופשית).
• מנועי חישוב Geospatial, היודעים לבצע חישובים על נתונים גיאוגרפיים. חישובים לדוגמה הם:
• מציאת מסלול קצר ביותר בין 2 נקודות (proximity)
• מציאת k אובייקטים מסוג מסוים הקרובים ביותר לנקודה נתונה (k-nearest)
• מציאת הגוף הקמור המינימלי המכיל קבוצת נקודות גיאוגרפיות (convex hull)
• פישוט התיאור של צורה גיאומטרית לייצוג פשוט יותר, עם מינימום שינוי (simplification)
• פעולות חיתוך / איחוד / מציאת שונות בין פוליגונים במרחב (intersection, disjoint, ..., וכו')
• ועוד
  המנועים הנפוצים בתחום (קוד פתוח) הם JTS (בג'אווה), GEOS (פורט של JTS ל ++C), ו GDAL (כתובה ב ++C, מתאימה למידע raster, שאינו וקטורי). כמובן שיש גם כמה מנועים proprietary.
• בסיסי נתונים Geospatial, אלו בסיסי נתונים "רגילים" היודעים לאחסן בעמודות/מסמך (תלוי בסוג בסיס הנתונים) מידע גיאוגרפי, ואז לבצע עליו חישובים. הרבה פעמים מדובר על בסיסי נתונים מוכרים עם extension ליכולות ה geospatial.
  בכדי לבצע חישובים יעילים של מרחקים, יש לבנות על הנתונים הגאוגרפים אינדקסים במבני-נתונים ייעודיים כגון k-d tree, או R-tree.
  k-d tree, למשל, הוא עץ בינארי, כאשר כל רמה שלו מתארת חיתוך של ציר אחר, למשל: רמה 1 לציר x, רמה 2 לציר y, ואז רמה 3 שוב לציר x וכו'. חיפוש במרחב עליו יהיה יעיל הרבה יותר מ B-tree - מבנה הנתונים ה"גנרי" לאינדקסים בבסיסי נתונים.
• בעולם הקוד הפתוח: PostgreSQL ו MongoDB הם המובילים, ל MySQL יש יכולות Goespatial בסיסיות בלבד.
• בעולם ה Commercial ניתן למצוא את אורקל (כמובן), MS-SQL (מאז גרסה 2005) ו DB2, שגם להם יש יכולות Geospatial.
• יש גם בסיסי נתונים ייעודיים למידע גיאוגרפי - והם פחות מוכרים.

למשל: PostgreSQL מנצל את היכולת המובנה שלו להגדרת טיפוסים חדשים, בכדי להגדיר מבנים גיאוגרפיים (למשל: פוליגון) ובעזרת extension בשם PostGIS (המכיל את GEOS) - הוא מאפשר לבצע שאילתות SQL שגם מבצעות חישובים.

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

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

ייצוג מידע גיאוגרפי

כיצד מייצגים מידע גאוגרפי?
האם "אלנבי 43, ת"א" הוא מידע מספיק? (לרוב - לא, צריך לתרגם אותו), ומה שונה חישוב גיאוגרפי מחישוב מתמטי פשוט?


מערכת קורדינטות

מערכת קורדינטות מדויקת המתארת מיקום על פני כדור הארץ, היא לדוגמה מערכת פולארית (נקראת בתחום: geodetic) כמו lat/long:

Latitude (בקיצור lat)
קו רוחב - מיקום הנקודה מעל או מתחת לקו המשווה.

Longitude (בקיצור long)
קו אורך - מיקום נקודה היא ממזרח או ממערב לקו גריניץ' - קו דמיוני שעובר בעיר לונדון.

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

בניגוד למערכת הקורדינטות שמקובלת בגרפיקה של מחשב, בהן נקודת ה 0,0 היא בפינה השמאלית עליונה של המסך וערכי הקורדינטות הם תמיד חיוביים, מרכז מערכת הצירים של מערכת ה lat-long נמצאת במרכז "המסך" (איפשהו במפרץ גאנה שבאפריקה) ויש לקורדינטות ערכים חיוביים ושליליים. טווח הערכים של lat היא 90- עד 90 מעלות, בעוד טווח הערכים של long הוא 180- עד 180 מעלות , כפי שניתן לראות בתרשים למטה.
את הערכים מייצגים בצורה עשרונית, למשל:

-71.060316 48.432044

lat/long (לפעמים נקראת lat/lon, ולפעמים הופכים את סדר הצירים: long/lat) היא המערכת המקובלת בתחום.
אתם יכולים לשחק דקה עם האתר latlong.net, בכדי לקבל מושג על הערכים שמתקבלים.

מערכת דומה מאוד היא המערכת בה משתמשים ב GPS, בה מעבר למעלות, מחלקים את השבר העשרוני ל "דקות" ו"שניות" (במקום נקודה עשרונית), ובמקום ערך שלילי/חיובי מציינים כיוון גיאוגרפי (צפון/דרום), מה שנראה כך:

40° 26′ 46″ N 79° 58′ 56″ W

חישוב מרחקים
כיצד מחשבים מרחק בין 2 נקודות?

חישוב המרחב הפשוט ביותר היא חישוב טריגונומטרי של משולש: צלע ראשונה היא ממרכז כדוה"א לנקודה א', צלע שנייה
היא מממרכז כדוה"א לנקודה ב' - וצלע שלישית היא המרחק.
חישוב נאיבי זה של מרחק (נקרא גם linear distance) הוא טוב למרחקים קצרים, אך איננו מדויק. המסלול בפועל בין 2 הנקודות הוא מעגלי - על פני כדוה"א. במצבים מסוימים (תלוי בנקודה לאורך כדור הארץ), מרחק אמיתי של 30 ק"מ יחושב כ 29.7 ק"מ בשיטה הטריגונומטרית. טווח זה של טעות מתחיל להיחשב כבעייתי עבור שימושים רבים.

ניתן כמובן לחשב angular distance, על בסיס כדור - מה שמספק קירוב לא-רע.
כאשר המרחקים גדולים (מאות קילומטרים) חשוב להשתמש להשתמש בנוסחאות המתארות צורה יותר מדויקת של כדור הארץ.מכיוון שכדור הארץ הוא כדורי-אליפטי (ellipsoid, או לדקדקנים: oblate spheroid), הערך של קו רוחב במטרים, למשל, איננו קבוע ומשתנה ממרכז לקצוות כדור הארץ. החישוב המדויק של מרחקים (או למשל: שטח) בהינתן תיאור ה ellipsoid הוא כבר דיי מורכב, וגוזל זמן חישוב גדול יותר.

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

אופן פישוט אחד לדוגמה הוא להתייחס  לכך שבממוצע, 111.32 ק"מ הם מעלה אחת של lat/long - כאשר יש הבדל (= טעות מירבית) של כ 1% בין קו המשווה לקוטב (בגלל הצורה האובלית של כדוה"א).

מקובל להשתמש בערך 0.000008998719243599958 בכדי לתאר בממוצע מטר, במעלות של lat/long.

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

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


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

עבור שימושים אחרים, דווקא הזמן הוא הנתון המעניין, ולכן מחשבים predicted traveling time. חיזוי זמני נסיעה הוא מדויק אף פחות, ותלוי במידה רבה בעומס התנועה בדרכים (מה שקשה לחזות. ל Waze יש ייתרון נהדר בתחום כי יש להם הרבה נתונים מעודכנים מהשטח, של נהגים עם אפליקציית Waze פתוחה, בעזרתם הם יכולים להגיע לרמת דיוק יוצאת דופן לטובה - באזורים בהם השימוש ב Waze הוא פופולרי, כמובן).

בעיות מידול של מפות כדוה"א, המשפיעות על מערכות Geospatial

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

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

מיפוי מפורסם למדי, למשל, נקרא Mercator Projection, שווריאציה שלו משתמשים המוצר Google Maps.
זהו מיפוי ממשפחת ה Cylindrical Projection, אשר נוטה לעוות יותר את הקטבים על חשבון עיוות פחות של קו המשווה.

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

תוצאה של Mercator Projection, אל מול הגודל האמיתי של אוסטרליה וגרינלנד. מקור: וויקיפדיה

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

ה Mercator Projection משמש גם כבסיס למערכת קורדינטות בשם UTM (קיצור של Universal Transverse Mercator). מערכת ה UTM מתעלמת מהקטבים (בהם העיוות של Mercator Projection הוא גדול במיוחד), ומחלקת את השטח שנותר ל 60 רצועות הנקראות UTM zones, ביניהן יש גם חפיפה קטנה:

UTM Zones של ארה"ב, על גבי projection קוני (לכן העיוות). מקור: וויקיפדיה.

בתוך ה UTM Zone הקורדינטות מחושבות במטרים, יחסית ל zone. מרכז ה UTM zone הוא 500,000 על 0. הסבר:
500,000 מטר למזרח (כך שניתן יהיה לתאר נקודה מערבית בערך חיובי), ובעוד הערך במטרים לצפון / דרום הוא גם חיובי, אך יש לציין N או S - האם הנקודה היא דרומית או צפונית לקו המשווה.

למשל מגדל CN בקנדה נמצא ב Zone 17, ובתוכו 630 ק"מ מזרחה ו 4833 ק"מ צפונה: 130 ק"מ מזרחית ממרכז ה zone, ו 4800 ק"מ צפונית מקו המשווה. בתחביר מקוצר מתארים זאת כ:

17N 630084 4833438

(להזכיר: הקורדינטות הן במטרים)

יש כל מיני הרחבות ל UTM (למשל: MGRS) שחוצות גם את ה zones לקווי רוחב, וכך מחלקים את המפה לריבועים.

מבני נתונים לתיאור מידע גיאוגרפי

את המידע הגאוגרפי (בבסיס נתונים, למשל), מייצגים בד"כ ע"י כמה מבני נתונים מקובלים:

Point

נקודה גיאוגרפית, שלרוב מיוצגת בעזרת הצמד lat ו long.

Polygon

סדרה של points המתארים צורה גאומטרית סגורה (כלומר: נקודה ראשונה = נקודה אחרונה) בעלת שטח שניתן לחישוב. שטח על המפה.

LineString (מחרוזת קווים)

סדרה של point, שאינה סגורה, המייצגת קירוב של תוואי שטח, כביש, וכו'. לרוב, את מה שאנו רוצים לייצג ב LineString ניתן יהיה לתאר בצורה מדויקת בעזרת curves - אבל אז רוב החישובים הנוגעים למידע זה יהיו מורכבים בהרבה. באופן דומה ומסיבות דומות, שימו לב שאין משתמשים בד"כ בעיגולים: כשרוצים לתאר עיגול מתארים מצולע משוכלל מסביב לנקודה, מה שנשמר כפוליגון.

נתקלתי בפורום כלשהו בסיפור הבא:
מישהו ניסה לשמור מעגלים מעל PostGIS, אבל לא מצא פקודה מתאימה. לשמחתו הוא מצא ספריית עזר שעושה זאת. הספרייה סיפקה פקודת create_circle ליצירת עיגול, אבל מתחת לקלעים יצרה תמיד מתומן (מצולע עם 8 צלעות) בשטח זהה לזה של המעגל המבוקש - ושמרה אותו כפוליגון. הפונקציה get_circle החזירה פרטים של עיגול אותו חישבו מהפוליגון שנשמר - ששימש את הבחור לתצוגה למשתמש.
הבעיה הגיעה בזמן ריצה: במקרה מסוים הבחור שמר מעגלים ברדיוס של 600 ק"מ ולא הבין למה פעמים רבות, נקודות שאמורות להיות במעגל - לא נמצאות בו (!!). #פשעי-אבסטרקציה.

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

מערכות שונות מוסיפות מבני נתונים משלהן: למשל PostGIS תומך גם ב CircularString (מחרוזת-קשתות) ו Polygon with holes (לדוגמה: לתיאור אגם עם אי). צורות נוספות הן ל יש גם מידע Raster (כמו תמונות לווין) שהן לא גיאומטריה אלא ממש bitmap - לא אתייחס אליהן בפוסט זה.

Geography
(התחייסות ל PostGIS או MS-SQL) - גאומטריה, המנוהלת בהכרח במערכת קורדינטות lat/long - אך ערכי החישוב בה (למשל: מרחק) הם במטרים - ולא במעלות, כפי שהיינו מקבלים מגיאומטריה המתוארת ב lat/long.



סמנטיקה

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

features 

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

Layer או Feature Class

קבוצות של features מאותו הסוג, למשל: אוסף כל הכבישים המהירים, כל הכבישים הרגילים, כל תחנות הרכבת או כל הקניונים. הרבה פעמים מאפשרים ב UI למשתמש להציג/להסתיר Layers (ומכאן המטאפורה / מקור השם).

Spatial Reference Systems

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

• ה ellipsoid (צורת כדור אליטפטי) שנבחר לייצג את כדור הארץ. אני למשל אוהב במיוחד את grs1980, אבל לא כולם כמוני...
• datum - (שיטת החישוב של) נקודת / נקודות הציון על פני כדור הארץ לפיה "מעמדים" את ה ellipsoid. הנקודות יכולות להיות במקומות שונים ובגבהים שונים. המטרה שלה להגדיר את ה geoid - המשטח הדמיוני של ה ellipsoid על פני כדור הארץ האמיתי. השיטה המקובלת ביותר היא WGS84, אך גם NAD27 ו NAD83 הן נפוצות. יש בסה"כ מאות שיטות קיימות.
• מערכת קורדינטות - כמו lat,long או זו של ה GPS. 
• מבנה הקובץ. מבנים מקובלים הם WTK (מבנה טקסטואלי מסוים), WTB (גרסה בינרית), GML (מבוסס XML), או GeoJSON.

שימוש ב datum שונה ממה שהתכוונו אליו - יכול לגרום לטעויות של מאות מטרים באיכון נקודות על המפה. שיטות קורדינטות שונות או מבנה קובץ שונים... אתם מבינים.

סה"כ יש שיטות המרה סטנדרטיות בין ה datums וה ellipsoids השונים, כך שאם ידוע פורמט המקור - מנוע החישוב שבו אתם משתמשים כנראה לא יתקשה לבצע את ההמרה. ב PostGIS, למשל, משתמשים בקוד בשם SRID (ערך לדוגמה: 4326) בכדי לבטא את ה reference system שבשימוש. משתמשים בו בכדי להגדיר את ה reference system של עמודה חדשה עם מידע גיאוגרפי שיוצרים, או בהכנסה של נתונים (שאז אם ה reference system הוא שונה - תתבצע המרה).

סיכום

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


שיהיה בהצלחה!



-----

לינקים רלוונטיים

USA National Map Viewer - מערכת GIS שמנוהלת ע"י ממשלת ארה"ב. ניתן להשתמש במערכת אונליין, או להוריד נתונים (באיכות טובה) על ארה"ב.