Сглаживание кривых линий для Google-карт и не только

Постановка задачи

Представьте себе такую задачу. Есть кривая, состоящая из N точек на плоскости. Требуется построить кривую, повторяющую контур исходной, но состоящую из меньшего количества точек. Так вот, одно из решений этой задачи заключается в использовании алгоритмов аппроксимации.

Кривая А

Кривая B

Требуется выполнить аппроксимацию точек кривой А и в результате получить кривую B.

Рассмотрим алгоритм аппроксимации на примере полигона, отрисованного на Google-карте. Как видим, на каждой границе полигона наблюдается большое скопление точек, решим эту проблему с помощью рассматриваемого алгоритма.

Полигон до применения аппроксимации

После аппроксимации на каждой из границ присутствуют лишь необходимые точки. Особенностью применения алгоритма на объектах карты является то, что для достижения хорошей степени аппроксимации необходимо подбирать параметр E_max для каждого масштаба карты.

Полигон после применения аппроксимации

Описание алгоритма

Имеется функция F, принимающая на вход множество K, представляющее собой совокупность всех точек кривой,  E_max — максимально допустимое расстояние от точки до прямой, проходящей через крайние точки участка кривой. Параметр E_max необходимо подбирать эмпирическим путем, от этого параметра зависит степень аппроксимации кривой.

Пошаговое описание алгоритма:

1. Строим прямую P₁P₂ между крайними точками множества K.

2. Находим максимально отдаленную от P₁P₂ точку L_max.

3. Если L_max больше, чем заданный параметр E_max , то разбиваем множество K на два подмножества K_l и K_r , относительно точки L_max и рекурсивно повторяем функции F(K_l) и F(K_r) для каждого из подмножеств.

4. Если же L_max меньше или равно E_max , то формируется множество R из крайних точек множества K (начальная и конечная точки участка кривой).

Пример реализации на JavaScript

Ниже приведена реализация алгоритма на языке JavaScript.

self.approximate = function (latLngArray, epsilon, 
latLngExtractor) {
    var approximatedPath = [];
    if (latLngArray.length < 3) {
        return latLngArray;
    }

// Перевод координат начальной точки из Географической системы 
// в Декартову 
    var startLinePoint = self.convertToCartesian(
        latLngExtractor(latLngArray[0]).lat,
        latLngExtractor(latLngArray[0]).lng);

// Перевод координат конечной точки из Географической системы 
// в Декартову 
    var endLinePoint = self.convertToCartesian(
        latLngExtractor(latLngArray.slice(-1)[0]).lat,
        latLngExtractor(latLngArray.slice(-1)[0]).lng);

// Построение уравнения прямой, между начальной и конечной 
// точкой, в нормальном виде
    var lineEquation = self.buildLineEquation(startLinePoint, 
endLinePoint);
    var maxDistance = -1;
    var maxDistancePointIndex = 0;

// Нахождение максимально отдаленной от прямой точки 
    for (var i = 1; i < latLngArray.length - 1; i++) {            
        var distance = 
self.calculateDistanceToLine(self.convertToCartesian(
            latLngExtractor(latLngArray[i]).lat,                
            latLngExtractor(latLngArray[i]).lng), lineEquation);

        if (distance != "undefined" && distance >= maxDistance) {
            maxDistance = distance;
            maxDistancePointIndex = i;
        }
    }

// Если максимальное расстояние до прямой больше Emax, то 
// разбиваем множество координат на два подмножества и вызываем 
// функцию рекурсивно 
    if (maxDistance >= epsilon) {
        approximatedPath = 
approximatedPath.concat(self.approximate(
            latLngArray.slice(0, maxDistancePointIndex + 1),
            epsilon, latLngExtractor));

        approximatedPath = 
approximatedPath.concat(self.approximate(
            latLngArray.slice(maxDistancePointIndex),
            epsilon, latLngExtractor));

        return approximatedPath;
    }

// Иначе возвращаем крайние точки кривой 
    else {
        return [
            latLngArray[0],
            latLngArray[latLngArray.length - 1]
        ];
    }
};

// Построение уравнения прямой, между начальной и конечной точкой, 
// в нормальном виде  
self.buildLineEquation = function (startXY, endXY) {
    var aParam = (endXY.y - startXY.y);
    var bParam = -1 * (endXY.x - startXY.x);
    var cParam = -1 * startXY.x * (endXY.y - startXY.y) + 
startXY.y * (endXY.x - startXY.x);
    return {a: aParam, b: bParam, c: cParam, startPoint: startXY, 
endPoint: endXY};
   };

// Нахождение расстояние от точки до прямой, заданной уравнением 
// в нормальном виде
self.calculateDistanceToLine = function (pointCoords, lineEquation) {
    return Math.abs(lineEquation.a * pointCoords.x + 
lineEquation.b * pointCoords.y + lineEquation.c) /
        Math.sqrt(Math.pow(lineEquation.a, 2) + 
Math.pow(lineEquation.b, 2));
};