javascript - Calculate possible lines from points -

i trying check points positions , detect whether in line, output object containing possible lines. questions:

• is best way it? efficient having 4 loops?
• i getting duplicates matching points within double loop, what's best way remove those?
• if wanted detect shapes e.g. square (90 degrees angles), equilateral triangle (60 degrees angles) etc, how extend it?
• if wanted advanced detection of patterns in point data e.g. 1 point @ 90 degrees 1km, 1 point @ 100 degrees 1.5km, 1 point @ 110km 2km etc. match be: every 5 degrees distance increases +50km. how enable that?

here js fiddle of got to:

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

we know long , lat co-ordinates of points 1 - 5. , want calculate red lines between them.

starting point data:

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     } ]; 

here functions i'm using:

var utils = {     disthaversine: function (lon1, lat1, lon2, lat2) { // calculate distance between 2 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 = 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 2 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 radians         return val * math.pi / 180;     },     todeg: function (val) { // convert radians degrees (signed)         return val * 180 / math.pi;     },     tobrng: function (val) { // convert radians degrees (as bearing: 0...360)         return (this.todeg(val) + 360) % 360;     } }; 

and far i've got:

function calculate(items) {     var = 0,         j = 0,         accuracy = 2,         bearings = {};      // loop through points , check distance , bearing of each 1     (i = 0; < items.length; += 1) {         (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 bearing array 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 bearings , create lines     (item in bearings) {         if (utils.size(bearings[item]) > 2) {             var line = { name: 'line ' + item + '°', points: [] };             (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); 

expected output:

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             }         ]     } ]; 

here js fiddle of got to:

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

i prefer answer in language independent way, makes answer more useful programmers encountering same problem use different language.

in absence of other relationship between points (e.g. knowing streets they're on), must start considering line segments between pairs of points. there binomial[n, 2] segments n points, if add heuristics avoid considering of these segments.

one have line segments, can associate each line segment particular vector l(s) on plane (let's call l plane). 2 line segments s1 , s2 collinear if , if l(s1) == l(s2).

l(s) defined vector fixed origin point o nearest point on (infinite) line extending s. if 2 segments on same line, they'll share same nearest point o, , if not, won't. can use spatial tree such quadtree on l plane see segments collinear.

you can compute vector l(s) using well-documented method of finding nearest point on line point, here's quick reminder.

dirty details: things go bad when origin collinear segment. you'll have handle case. think best way deal case put segments aside, move origin, , re-apply algorithm segments.

also, tolerance you'll want use coincidence scales distance o.