Skip to content

Instantly share code, notes, and snippets.

@alanchrt
Created January 22, 2014 20:08
Show Gist options
  • Save alanchrt/8566411 to your computer and use it in GitHub Desktop.
Save alanchrt/8566411 to your computer and use it in GitHub Desktop.
Triangulation of three points and radii
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];
};
@skerit
Copy link

skerit commented Jun 28, 2016

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment