Сортировка координат широты и долготы в четырехугольник по часовой стрелке - PullRequest
31 голосов
/ 18 мая 2010

Задача

Пользователи могут предоставить до четырех координат широты и долготы в любом порядке. Они делают это с Google Maps. Используя Google Polygon API (v3), выбранные ими координаты должны выделять выделенную область между четырьмя координатами.

Вопрос

Как отсортировать массив координат широты и долготы в (против) направлении по часовой стрелке?

Решения и поиски

Вопросы StackOverflow

Похожие сайты

Известные алгоритмы

  • сканирование Грэма (слишком сложное)
  • Алгоритм Джарвиса Марча (обрабатывает N точек)
  • Рекурсивный выпуклый корпус (удаляет точку)

Код

Вот что у меня есть:

// Ensures the markers are sorted: NW, NE, SE, SW
function sortMarkers() {
  var ns = markers.slice( 0 );
  var ew = markers.slice( 0 );

  ew.sort( function( a, b ) {
    if( a.position.lat() < b.position.lat() ) {
      return -1;
    }
    else if( a.position.lat() > b.position.lat() ) {
      return 1;
    }

    return 0;
  });

  ns.sort( function( a, b ) {
    if( a.position.lng() < b.position.lng() ) {
      return -1;
    }
    else if( a.position.lng() > b.position.lng() ) {
      return 1;
    }

    return 0;
  });

  var nw;
  var ne;
  var se;
  var sw;

  if( ew.indexOf( ns[0] ) > 1 ) {
    nw = ns[0];
  }
  else {
    ne = ns[0];
  }

  if( ew.indexOf( ns[1] ) > 1 ) {
    nw = ns[1];
  }
  else {
    ne = ns[1];
  }

  if( ew.indexOf( ns[2] ) > 1 ) {
    sw = ns[2];
  }
  else {
    se = ns[2];
  }

  if( ew.indexOf( ns[3] ) > 1 ) {
    sw = ns[3];
  }
  else {
    se = ns[3];
  }

  markers[0] = nw;
  markers[1] = ne;
  markers[2] = se;
  markers[3] = sw;
}

Спасибо.

Ответы [ 3 ]

39 голосов
/ 19 мая 2010

Учитывая баллы:

   4  +        [d]            [g]                 
      |                             
   3 [a]            [e]                 
      |                             
   2  +                  [f]       [h]    
      |                             
   1  +   [b]                             
      |                             
   0  +----+---[c]---+----+----+----+
      0    1    2    3    4    5    6

Вы хотите найти следующую связанную прогулку:

   4  +     ___[d]------------[g]                 
      |  __/                     \    
   3 [a]/           [e]__         \       
      | \             \_ ```---    \  
   2  +  \              `[f]   \___[h]    
      |   \           __/            
   1  +   [b]      __/                   
      |      \    /                
   0  +----+--`[c]---+----+----+----+
      0    1    2    3    4    5    6

Если это правильно, вот способ:

  • найдите самую верхнюю точку, P top , в наборе точек. В случае ничьей выберите точку с наименьшей координатой х
  • Сортировка всех точек путем сравнения наклонов m i и m j линий каждой пары точек (исключая P top !) P i и P j делают при прохождении через P top
    • , если m i и m j равны, пусть точка P i или P j ближе всего к P top первым
    • , если m i положительно и m j отрицательно (или ноль), P j идет первым
    • если m i и m j либо положительны, либо отрицательны, пусть точка, принадлежащая линии с наибольшим наклоном, стоит первой

Вот краткое демо для карты:

enter image description here

(Я немного знаю JavaScript, поэтому мог или, возможно, нарушил некоторые соглашения по коду JavaScript ...):

var points = [
    new Point("Stuttgard", 48.7771056, 9.1807688),
    new Point("Rotterdam", 51.9226899, 4.4707867),
    new Point("Paris", 48.8566667, 2.3509871),
    new Point("Hamburg", 53.5538148, 9.9915752),
    new Point("Praha", 50.0878114, 14.4204598),
    new Point("Amsterdam", 52.3738007, 4.8909347),
    new Point("Bremen", 53.074981, 8.807081),
    new Point("Calais", 50.9580293, 1.8524129),
];
var upper = upperLeft(points);

print("points :: " + points);
print("upper  :: " + upper);
points.sort(pointSort);
print("sorted :: " + points);

// A representation of a 2D Point.
function Point(label, lat, lon) {

    this.label = label;
    this.x = (lon + 180) * 360;
    this.y = (lat + 90) * 180;

    this.distance=function(that) {
        var dX = that.x - this.x;
        var dY = that.y - this.y;
        return Math.sqrt((dX*dX) + (dY*dY));
    }

    this.slope=function(that) {
        var dX = that.x - this.x;
        var dY = that.y - this.y;
        return dY / dX;
    }

    this.toString=function() {
        return this.label;
    }
}

// A custom sort function that sorts p1 and p2 based on their slope
// that is formed from the upper most point from the array of points.
function pointSort(p1, p2) {
    // Exclude the 'upper' point from the sort (which should come first).
    if(p1 == upper) return -1;
    if(p2 == upper) return 1;

    // Find the slopes of 'p1' and 'p2' when a line is 
    // drawn from those points through the 'upper' point.
    var m1 = upper.slope(p1);
    var m2 = upper.slope(p2);

    // 'p1' and 'p2' are on the same line towards 'upper'.
    if(m1 == m2) {
        // The point closest to 'upper' will come first.
        return p1.distance(upper) < p2.distance(upper) ? -1 : 1;
    }

    // If 'p1' is to the right of 'upper' and 'p2' is the the left.
    if(m1 <= 0 && m2 > 0) return -1;

    // If 'p1' is to the left of 'upper' and 'p2' is the the right.
    if(m1 > 0 && m2 <= 0) return 1;

    // It seems that both slopes are either positive, or negative.
    return m1 > m2 ? -1 : 1;
}

// Find the upper most point. In case of a tie, get the left most point.
function upperLeft(points) {
    var top = points[0];
    for(var i = 1; i < points.length; i++) {
        var temp = points[i];
        if(temp.y > top.y || (temp.y == top.y && temp.x < top.x)) {
            top = temp;
        }
    }
    return top;
}

Примечание: вы должны удвоить или утроить проверку преобразований с lat,lon до x,y, поскольку я новичок, если речь идет о ГИС !!! Но, возможно, вам даже не нужно ничего конвертировать. Если вы этого не сделаете, функция upperLeft может просто вернуть самую низкую точку вместо самой высокой, в зависимости от местоположения рассматриваемых точек. Опять же: трижды проверьте эти предположения!

При выполнении приведенного выше фрагмента выводится следующее:

points :: Stuttgard,Rotterdam,Paris,Hamburg,Praha,Amsterdam,Bremen,Calais
upper  :: Hamburg
sorted :: Hamburg,Praha,Stuttgard,Paris,Bremen,Calais,Rotterdam,Amsterdam

Функция альтернативного расстояния

function distance(lat1, lng1, lat2, lng2) {
  var R = 6371; // km
  var dLat = (lat2-lat1).toRad();
  var dLon = (lng2-lng1).toRad();
  var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
          Math.cos(lat1.toRad()) * Math.cos(lat2.toRad()) *
          Math.sin(dLon/2) * Math.sin(dLon/2);
  var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
  return R * c;
}
4 голосов
/ 18 мая 2010

Идея алгоритма: усредните четыре точки, чтобы получить точку внутри многоугольника. Затем вычислите угол луча между этой центральной точкой и каждой точкой, используя обратные тригонометрические функции, как описано здесь . Тогда сортируй по углам. Это должно дать вам (против) порядок по часовой стрелке, в зависимости от порядка сортировки и того, что вы считаете "нулевым градусом".

UPDATE: вот код В основном непроверенный, но это идея.

function sorted_points(points) {
    points = points.slice(0); // copy the array, since sort() modifies it
    var stringify_point = function(p) { return p.x + ',' + p.y; };

    // finds a point in the interior of `pts`
    var avg_points = function(pts) {
        var x = 0;
        y = 0;
        for(i = 0; i < pts.length; i++) {
            x += pts[i].x;
            y += pts[i].y;
        }
        return {x: x/pts.length, y:y/pts.length};
    }
    var center = avg_points(points);

    // calculate the angle between each point and the centerpoint, and sort by those angles
    var angles = {};
    for(i = 0; i < points.length; i++) {
        angles[stringify_point(points[i])] = Math.atan(points[i].x - center.x, points[i].y - center.y);
    }
    points.sort(function(p1, p2) {
        return angles[stringify_point(p1)] - angles[stringify_point(p2)];
    });
    return points;
}

Сортирует точки (массив объектов типа {x: 1, y: 1}) против часовой стрелки.

1 голос
/ 05 августа 2011

Для тех, кто прибывает сюда с подобной проблемой год спустя:

Я не согласен с выбранным ответом. Не существует единственного решения для заказа даже с заданным направлением часов. Выпуклая оболочка данных координат устраняет точки e и f. Затем они могут быть прикреплены в любом месте пути. Объективно h, e, f, c можно улучшить до h, f, e, c, сохраняя направление компонента x постоянным - в данном случае отрицательным.

Значение этого делает невозможным гарантировать включение какого-либо местоположения на карте в результирующую область, ограниченную выбранной прогулкой.

...