מיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו

[אביי]

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

• א"א להשתמש בשירותי API מיפוי כלשהם, כי מדובר בכמות גדולה מידי של מאות ואפילו אלפים.

מגיגול קצר מצאתי שיש שיטה שנקראת nearest neighbor (שכן קרוב) שהרעיון הבסיסי שלה הוא למיין את רשימת הכתובות על סמך הקרבה שלהן זו לזו ע"י חישוב המרחק ביניהם.

ניסיתי ליישם את זה באמצעות נוסחת Haversine וכתבתי את הקוד הבא:

function haversineSort(coordinates) {
    var sortedCoords = [];
    var remainingCoords = coordinates.slice();

    var currentCoord = remainingCoords[0];
    sortedCoords.push(currentCoord);
    remainingCoords.splice(0, 1);

    while (remainingCoords.length > 0) {
        var closestCoord = null;
        var closestDistance = Number.POSITIVE_INFINITY;
        for (var i = 0; i < remainingCoords.length; i++) {
            var distance = haversineDistance(currentCoord, remainingCoords[i]);
            if (distance < closestDistance) {
                closestCoord = remainingCoords[i];
                closestDistance = distance;
            }
        }
        sortedCoords.push(closestCoord);
        remainingCoords.splice(remainingCoords.indexOf(closestCoord), 1);
        currentCoord = closestCoord;
    }
    return sortedCoords;
}

function haversineDistance(coord1, coord2) {
    var R = 6371e3;
    var lat1 = coord1[0] * Math.PI / 180;
    var lat2 = coord2[0] * Math.PI / 180;
    var deltaLat = (coord2[0] - coord1[0]) * Math.PI / 180;
    var deltaLng = (coord2[1] - coord1[1]) * Math.PI / 180;

    var a = Math.sin(deltaLat / 2) * Math.sin(deltaLat / 2) +
        Math.cos(lat1) * Math.cos(lat2) *
        Math.sin(deltaLng / 2) * Math.sin(deltaLng / 2);
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

    var distance = R * c;
    return distance;
}

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

ניסיתי גם מיון פשוט של

function coordinates() {
    var coordinates = [32.0789807, 34.9373663, 32.9903809, 34.8357482, 32.0991133, 34.8381311, 32.0992587, 34.8410008, 32.0761814, 34.8327112, 32.0811637, 34.8276694, 32.0744861, 34.8363304]

    var sortedCoordinates = sortCoordinates(coordinates);
    console.log(sortedCoordinates);
}

function sortCoordinates(coordinates) {
    coordinates.sort(function (a, b) {
        return a[0] - b[0];
    });
    return coordinates;
}

והתוצאה

[ 32.0789807,
  34.9373663,
  32.9903809,
  34.8357482,
  32.0991133,
  34.8381311,
  32.0992587,
  34.8410008,
  32.0761814,
  34.8327112,
  32.0811637,
  34.8276694,
  32.0744861,
  34.8363304 ]

[yossiz]

@אביי כתב במיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו:

coordinates.sort(function (a, b) {
        return a[0] - b[0];
    });

הפוקנציה לא מקבלת מערך אלא מספר,
צ"ל:

coordinates.sort(function (a, b) {
        return a - b;
    });

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

[dovid]

כפי ש@yossiz אמר כל מיקום אמור להכיל זוג מספרים, ולא מספר בודד. כנראה לכן זה לא עובד.
חוץ מזה זה נראה בסדר (הפונקציה haversineDistance לא נמצאת בקוד אבל אני מניח שהיא תקינה).

[אביי]

@yossiz כתב במיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו:

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

זה אכן שני מספרים, אבל ההפרדה ביניהם היא בפסיק, שים לב לרצף שאיבר אחד מתחיל ב32 (רוחב) והבא אחריו ב34 (אורך).

[אביי]

@dovid כתב במיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו:

הפונקציה haversineDistance

תסתכל בשורה 26

[אביי]

@dovid כתב במיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו:

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

אני אנסה לקבל את הקואורדינטות עם מקף מפריד במקום פסיק ונראה.

[yossiz]

פוסט זה נמחק!

[dovid]

@אביי אין טעם לשנות איך אתה מקבל, השאלה איך המבנה של coordinates.
הפונקציה מניחה שcoordinates נראה ככה:

[
     [32.0789807, 34.9373663],
     [32.9903809, 34.8357482]
]

מהפלט שהבאת נראה שהקלט לא במבנה הזה.
לא צריך לשנות את המקור שמביא לך, אפשר לעבד אותו מאיך שהוא נראה, רק צריך להתכונן אליו נכון. אם תביא את הקלט (ע"י consol.log בשורה 2 של coordinates נכוון אותך מה לעשות).

[אביי]

@dovid כתב במיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו:

אם תביא את הקלט

[32.0789807 , 34.8373663, 32.0903809 , 34.8357482, 32.0991133 , 34.8381311, 32.0992587 , 34.8410008, 32.0761814 , 34.8327112, 32.0811637 , 34.8276694, 32.0744861 , 34.8363304]

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

[dovid]

תוסיף בשורה 2 את הקוד הבא:

let newArr = [];
for (let i = 0; i < coordinates.length / 2; i++)    
  newArr[i] = [coordinates[i*2], coordinates[(i*2)+1]];
 
coordinates = newArr;

@אביי הבאתי קוד שגוי, תיקנתי כעת.

[אביי]

@dovid כתב במיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו:

@אביי הבאתי קוד שגוי, תיקנתי כעת.

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

שמתי כך

let newArr = [];
for (let i = 0; i < coordinates.length / 2; i++)    
  newArr[i] = [coordinates[i*2]];
coordinates = newArr;

כי איך שהבאת הוא הקיף כל שני זוגות בסוגריים.

אבל כעת הוא נתקע בשורה 28 הוא טוען שcoord1 מגיע ריק, והוא אכן צודק coord1 מגיע ריק ואילו coord2 מגיע מלא.

[dovid]

@אביי כתב במיון קוארודינטות לפי סדר גיאוגרפי הגיוני כלשהו:

כי איך שהבאת הוא הקיף כל שני זוגות בסוגריים.

אז הקלט שלך מתעתע בך כנראה. כלומר לפי איך שהראית כעת, הקלט כבר טוב מראש.

[אביי]

@dovid כתבתי כעת מחדש את הקוד שלי תוך שימת לב לקלט שמגיע בפועל, וזה אכן עובד מעולה.

let coordinates = `[32.0809247 , 34.8426006, 32.0856592 , 34.840563, 32.0903809 , 34.8357482, 32.084932 , 34.835226, 32.0762743 , 34.8356051, 32.0766089 , 34.8085407]`

function haversineSort(coordinates) {
    var sortedCoords = [];
    var remainingCoords = coordinates.slice();

    var currentCoord = remainingCoords[0].split(", ").map(Number);
    sortedCoords.push(currentCoord);
    remainingCoords.splice(0, 1);

    while (remainingCoords.length > 0) {
        var closestCoord = null;
        var closestDistance = Number.POSITIVE_INFINITY;
        for (var i = 0; i < remainingCoords.length; i++) {
            var distance = haversineDistance(currentCoord, remainingCoords[i].split(", ").map(Number));
            if (distance < closestDistance) {
                closestCoord = remainingCoords[i];
                closestDistance = distance;
            }
        }

        sortedCoords.push(closestCoord.split(", ").map(Number));
        remainingCoords.splice(remainingCoords.indexOf(closestCoord), 1);
        currentCoord = closestCoord.split(", ").map(Number);
    }

    return sortedCoords;
}

function haversineDistance(coord1, coord2) {
    var R = 6371e3;
    var lat1 = coord1[0] * Math.PI / 180;
    var lat2 = coord2[0] * Math.PI / 180;
    var deltaLat = (coord2[0] - coord1[0]) * Math.PI / 180;
    var deltaLon = (coord2[1] - coord1[1]) * Math.PI / 180;

    var a = Math.sin(deltaLat / 2) * Math.sin(deltaLat / 2) +
        Math.cos(lat1) * Math.cos(lat2) *
        Math.sin(deltaLon / 2) * Math.sin(deltaLon / 2);
    var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));

    return R * c;
}

תודה ענקית על העזרה וההכוונה, זה לא מובן מאליו