mitchell-r
1/22/2014 - 8:08 PM

Triangulation of three points and radii

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