Created
January 22, 2014 20:08
-
-
Save alanchrt/8566411 to your computer and use it in GitHub Desktop.
Triangulation of three points and radii
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var distancePoints = function(p1, p2) { | |
// Find the distance between two points | |
return Math.sqrt(Math.pow(p2[0] - p1[0], 2) + Math.pow(p2[1] - p1[1], 2)); | |
}; | |
var intersectCircles = function (c1, r1, c2, r2) { | |
// Find the points of intersection for two circles | |
// Based on: http://stackoverflow.com/a/3349134 | |
var d = distancePoints(c1, c2); | |
if (d > r1 + r2) // Circles do not overlap | |
return []; | |
if (d < Math.abs(r1 - r2)) // One circle contains the other | |
return []; | |
if (d == 0 && r1 == r2) // These are the same circle | |
return []; | |
// Find distances of dimensions from the first point | |
var a = (Math.pow(r1, 2) - Math.pow(r2, 2) + Math.pow(d, 2)) / (2 * d); | |
var h = Math.sqrt(Math.pow(r1, 2) - Math.pow(a, 2)); | |
// Determine point on the line between centers perpendicular to intersects | |
var p = [ | |
c1[0] + a * (c2[0] - c1[0]) / d, | |
c1[1] + a * (c2[1] - c1[1]) / d | |
]; | |
// Calculate intersection points | |
return [ | |
[ | |
p[0] + h * (c2[1] - c1[1]) / d, | |
p[1] - h * (c2[0] - c1[0]) / d | |
], | |
[ | |
p[0] - h * (c2[1] - c1[1]) / d, | |
p[1] + h * (c2[0] - c1[0]) / d | |
] | |
]; | |
}; | |
var triangulate = function(c1, r1, c2, r2, c3, r3) { | |
// A circle object | |
var Circle = function(c, r) { | |
this.center = c; | |
this.radius = r; | |
}; | |
// Initialize circles | |
var circles = [ | |
new Circle(c1, r1), | |
new Circle(c2, r2), | |
new Circle(c3, r3) | |
]; | |
// Triangulate with all combinations | |
var points = []; | |
for (var i = 0; i < 3; i ++) { | |
var crossPoints = intersectCircles( | |
circles[i].center, circles[i].radius, | |
circles[(i+1)%3].center, circles[(i+1)%3].radius | |
); | |
var thirdPoint = circles[(i+2)%3]; | |
var offsets = [ | |
Math.abs(distancePoints(crossPoints[0], thirdPoint.center) - thirdPoint.radius), | |
Math.abs(distancePoints(crossPoints[1], thirdPoint.center) - thirdPoint.radius) | |
]; | |
points.push([crossPoints[0], offsets[0]]); | |
points.push([crossPoints[1], offsets[1]]); | |
} | |
// Find the most precisely triangulated point | |
var pointIndex = 0; | |
for (var i = 0; i < points.length; i ++) { | |
if (points[i][1] < points[pointIndex][1]) | |
pointIndex = i; | |
} | |
return points[pointIndex][0]; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks, precisely what I was looking for.
Btw: turns out this is actually trilateration.
Triangulation is another form of position calculation which requires knowledge of angles, too.