Рассчитать возможные линии из точек

Question

Я пытаюсь проверить позиции точек и определить, находятся ли они в строке, а затем вывести объект, содержащий возможные строки. Вопросы:

• Это лучший способ сделать это? эффективный с четырьмя петлями?
• Я также получаю дубликаты, соответствующие точкам в двойном цикле, что лучший способ их удалить?
• Если бы я хотел обнаружить фигуры, например. квадрат (90 градусов), равносторонний треугольник (60 градусов) и т. д., как бы я его расширил?
• Если бы я хотел выполнить расширенное обнаружение шаблонов в данных точки, например. одна точка при 90 градусах - 1 км, одна точка при 100 градусах - 1,5 км, одна точка в 110 км - 2 км и т. д. Матч будет: каждые 5 градусов расстояние увеличивается на + 50 км. Как я могу включить это?

Вот JS скрипка, где я получил:

http://jsfiddle.net/kmturley/RAQXf/1/

Мы знаем, что длинная и латы координаты точек 1 - 5. И мы хотим вычислить красные линии между их.

Начальная точка данных:

var points = [ 
    { 
     name: 'Point 1', 
     lat: 51.509440, 
     long: -0.126985 
    }, 
    { 
     name: 'Point 2', 
     lat: 51.509453, 
     long: -0.126180 
    }, 
    { 
     name: 'Point 3', 
     lat: 51.510076, 
     long: -0.124804 
    }, 
    { 
     name: 'Point 4', 
     lat: 51.510327, 
     long: -0.124133 
    }, 
    { 
     name: 'Point 5', 
     lat: 51.509440, 
     long: -0.124175 
    } 
]; 

Вот функции я использую:

var utils = { 
    distHaversine: function (lon1, lat1, lon2, lat2) { // calculate distance between two points 
     var R = 6371; // earth's mean radius in km 
     var dLat = this.toRad(lat2 - lat1); 
     var dLon = this.toRad(lon2 - lon1); 
     lat1 = this.toRad(lat1), 
     lat2 = this.toRad(lat2); 
     var a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(lat1) * Math.cos(lat2) * Math.sin(dLon/2) * Math.sin(dLon/2); 
     var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); 
     var d = R * c; 
     return d; 
    }, 
    bearing: function (lon1, lat1, lon2, lat2) { // calculate bearing between two points 
     lat1 = this.toRad(lat1); 
     lat2 = this.toRad(lat2); 
     var dLon = this.toRad(lon2 - lon1); 
     var y = Math.sin(dLon) * Math.cos(lat2); 
     var x = Math.cos(lat1) * Math.sin(lat2) - Math.sin(lat1) * Math.cos(lat2) * Math.cos(dLon); 
     return this.toBrng(Math.atan2(y, x)); 
    }, 
    toRad: function (val) { // convert degrees to radians 
     return val * Math.PI/180; 
    }, 
    toDeg: function (val) { // convert radians to degrees (signed) 
     return val * 180/Math.PI; 
    }, 
    toBrng: function (val) { // convert radians to degrees (as bearing: 0...360) 
     return (this.toDeg(val) + 360) % 360; 
    } 
}; 

И это, насколько я получил:

function calculate(items) { 
    var i = 0, 
     j = 0, 
     accuracy = 2, 
     bearings = {}; 

    // loop through the points and check the distance and bearing of each one 
    for (i = 0; i < items.length; i += 1) { 
     for (j = 0; j < items.length; j += 1) { 
      if (i !== j) { 
       var bearing = utils.bearing(items[i].long, items[i].lat, items[j].long, items[j].lat); 
       var distance = utils.distHaversine(items[i].long, items[i].lat, items[j].long, items[j].lat); 
       var key = Math.round(bearing/accuracy) * accuracy; 
       // push both points into the bearing array for the same line 
       if (!bearings[key]) { bearings[key] = {}; } 
       bearings[key][i] = true; 
       bearings[key][j] = true; 
       console.log(Math.round(distance * 1000) + 'm', Math.round(bearing) + '°', items[i].name + ' > ' + items[j].name); 
      } 
     } 
    } 
    return bearings; 
} 

function lines(bearings, items) { 
    var item = {}, 
     key = '', 
     lines = []; 

    // loop though the bearings and create lines 
    for (item in bearings) { 
     if (utils.size(bearings[item]) > 2) { 
      var line = { name: 'Line ' + item + '°', points: [] }; 
      for (key in bearings[item]) { 
       line.points.push(items[parseInt(key)]); 
      } 
      lines.push(line); 
     } 
    } 
    return lines; 
} 

var bearings = calculate(points); 
var lines = lines(bearings, points); 

console.log('--------'); 
console.log(lines); 

Ожидаемый результат:

var lines = [ 
    { 
     name: 'Line 1', 
     points: [ 
      { 
       name: 'Point 1', 
       lat: 51.509440, 
       long: -0.126985 
      }, 
      { 
       name: 'Point 2', 
       lat: 51.509453, 
       long: -0.126180 
      }, 
      { 
       name: 'Point 5', 
       lat: 51.509440, 
       long: -0.124175 
      } 
     ] 
    }, 
    { 
     name: 'Line 2', 
     points: [ 
      { 
       name: 'Point 2', 
       lat: 51.509453, 
       long: -0.126180 
      }, 
      { 
       name: 'Point 3', 
       lat: 51.510076, 
       long: -0.124804 
      }, 
      { 
       name: 'Point 4', 
       lat: 51.510327, 
       long: -0.124133 
      } 
     ] 
    } 
]; 

Вот JS скрипку, где я получил:

http://jsfiddle.net/kmturley/RAQXf/1/

Answer 1

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

При отсутствии каких-либо иных отношений между точками (например, зная, на каких улицах они находятся), вы должны начать с рассмотрения всех сегментов линии между парами точек. Есть Binomial[n, 2] сегментов для n баллов, поэтому было бы хорошо, если бы вы могли добавить эвристику, чтобы не учитывать некоторые из этих сегментов.

У нас есть эти сегменты, мы можем связать каждый отрезок линии с конкретным вектором L(S) на плоскости (назовем это плоскостью L). Два линейных сегмента S1 и S2 будут коллинеарными тогда и только тогда, когда L(S1) == L(S2).

L(S) определяется как вектор из некоторой фиксированной точки начала O до ближайшей точки (бесконечной) линии, простирающейся от S. Если два сегмента находятся в одной строке, то они будут использовать одну и ту же ближайшую точку до O, а если нет, они не будут.Итак, теперь вы можете использовать пространственное дерево, такое как quadtree на плоскости L, чтобы увидеть, какие сегменты коллинеарны.

Вы можете вычислить вектор L(S) используя хорошо документированный метод нахождения ближайшей точки на линии в другую точку, но вот краткое напоминание.

Грязных детали: Дела идут плохо, когда ваше происхождение коллинеарно с любым сегментом. Вы должны будете справиться с этим делом. Я думаю, что лучший способ справиться с этим делом - отложить эти сегменты, перенести начало координат и затем применить алгоритм только к этим сегментам.

Кроме того, толерантность, которую вы хотите использовать для шкал совпадений, находится на расстоянии от O.

Answer 2

Так что я уже удалось решить эту проблему с помощью этого сценария:

http://www.movable-type.co.uk/scripts/latlon.js

, а затем следующий код:

var p1 = new LatLon(item1.lat, items1.long); 
var p2 = new LatLon(item2.lat, items2.long); 
var p3 = new LatLon(item3.lat, items3.long); 
var distance = Math.abs(Math.asin(Math.sin(p1.distanceTo(p3)/R) * Math.sin(p1.bearingTo(p3).toRad() - p1.bearingTo(p2).toRad())) * R); 

У меня был один важный вопрос: подшипник был в градус, но нужно было быть в радианах!

p1.bearingTo(p3).toRad() - p1.bearingTo(p2).toRad() 

Вы можете увидеть рабочую версию здесь (с использованием нескольких точек, чтобы найти линии между ними):

http://jsfiddle.net/kmturley/Cq2DV/1/