Polyline label positioning algorithm

Question

I'm looking for pointers to algorithms that will help with automatically positioning a label on a polyline.

In this specific case the polyline is defined as a series of [x,y] points. The first point is the origin, the last point is the destination. A line between two points is always straight (ie. not a curve/arc/bezier).

Currently I'm picking the "middle" line segment and positioning the label at the middle of that segment.

This can leads to odd label placements unless each line segment is roughly the same length. If one line segment is much longer then the label "looks odd".

So... any thoughts on what I should be googling for?

Thanks!

Answer 1

Inspired by Petar Ivanov's comment:

//
// Calculate the distance between two points
//
function distance(a, b) {
    var dx = a.x - b.x;
    var dy = a.y - b.y;
    return Math.sqrt(dx * dx + dy * dy);
}

//
// Given a line between point1 and point2 return a point that 
// is distance away from point1
//
function lineInterpolate(point1, point2, distance) {
    var xabs = Math.abs(point1.x - point2.x);
    var yabs = Math.abs(point1.y - point2.y);
    var xdiff = point2.x - point1.x;
    var ydiff = point2.y - point1.y;

    var length = Math.sqrt((Math.pow(xabs, 2) + Math.pow(yabs, 2)));
    var steps = length / distance;
    var xstep = xdiff / steps;
    var ystep = ydiff / steps;

    return { x: point1.x + xstep, y: point1.y + ystep };
}

//
// Return the point that is the midpoint for the line
//
function lineMidpoint(lineSegments) {
    //
    // Sum up the total distance of the line
    //
    var TotalDistance = 0;
    for (var i = 0; i < lineSegments.length - 1; i += 1) {
        TotalDistance += distance(lineSegments[i], lineSegments[i + 1]);
    }

    //
    // Find the middle segemnt of the line
    //
    var DistanceSoFar = 0;
    for (var i = 0; i < lineSegments.length - 1; i += 1) {
        //
        // If this linesegment puts us past the middle then this
        // is the segment in which the midpoint appears
        //
        if (DistanceSoFar + distance(lineSegments[i], lineSegments[i + 1]) > TotalDistance / 2) {
            //
            // Figure out how far to the midpoint
            //
            var DistanceToMidpoint = TotalDistance / 2 - DistanceSoFar;

            //
            // Given the start/end of a line and a distance return the point
            // on the line the specified distance away
            //
            return lineInterpolate(lineSegments[i], lineSegments[i + 1], DistanceToMidpoint);
        }

        DistanceSoFar += distance(lineSegments[i], lineSegments[i + 1]);
    }

    //
    // Can happen when the line is of zero length... so just return the first segment
    //
    return lineSegments[0];
}