Алгоритм позиционирования полилинейной метки

Я ищу указатели на алгоритмы, которые помогут автоматически расположить метку на полилинии.

В этом конкретном случае полилиния определяется как последовательность точек [x, y]. Первая точка — исходная, последняя — конечная. Линия между двумя точками всегда прямая (т.е. не кривая/дуга/безье).

В настоящее время я выбираю «средний» сегмент линии и размещаю метку в середине этого сегмента.

Это может привести к нечетному размещению меток, если каждый сегмент линии не будет примерно одинаковой длины. Если один отрезок линии намного длиннее, то метка «выглядит странно».

Итак... какие-нибудь мысли о том, что я должен гуглить?

Спасибо!


javascript label algorithm line
person user505765    schedule 17.12.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Вдохновленный комментарием Петра Иванова:

//
// 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];
}
person user505765    schedule 17.12.2011

arrow_upward
0
arrow_downward

Почему бы просто не поставить этикетку посередине. Это вычисляет общую длину сегментов линии, затем берет половину ее и размещает метку на этом расстоянии (следуя пути).

person Petar Ivanov    schedule 17.12.2011