En

JazzTeam Software Development Company

Agile Java Development

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

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

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

Curve A

Кривая А

Curve B

Кривая B

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

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

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

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

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

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

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

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

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

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

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

2. Находим максимально отдаленную от P1P2 точку Lmax.

image00

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

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

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

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

  1. self.approximate = function (latLngArray, epsilon,
  2. latLngExtractor) {
  3. var approximatedPath = [];
  4. if (latLngArray.length < 3) {
  5. return latLngArray;
  6. }
  7.  
  8. // Перевод координат начальной точки из Географической системы
  9. // в Декартову
  10. var startLinePoint = self.convertToCartesian(
  11. latLngExtractor(latLngArray[0]).lat,
  12. latLngExtractor(latLngArray[0]).lng);
  13.  
  14. // Перевод координат конечной точки из Географической системы
  15. // в Декартову
  16. var endLinePoint = self.convertToCartesian(
  17. latLngExtractor(latLngArray.slice(-1)[0]).lat,
  18. latLngExtractor(latLngArray.slice(-1)[0]).lng);
  19.  
  20. // Построение уравнения прямой, между начальной и конечной
  21. // точкой, в нормальном виде
  22. var lineEquation = self.buildLineEquation(startLinePoint,
  23. endLinePoint);
  24. var maxDistance = -1;
  25. var maxDistancePointIndex = 0;
  26.  
  27. // Нахождение максимально отдаленной от прямой точки
  28. for (var i = 1; i < latLngArray.length - 1; i++) {
  29. var distance =
  30. self.calculateDistanceToLine(self.convertToCartesian(
  31. latLngExtractor(latLngArray[i]).lat,
  32. latLngExtractor(latLngArray[i]).lng), lineEquation);
  33.  
  34. if (distance != "undefined" && distance >= maxDistance) {
  35. maxDistance = distance;
  36. maxDistancePointIndex = i;
  37. }
  38. }
  39.  
  40. // Если максимальное расстояние до прямой больше Emax, то
  41. // разбиваем множество координат на два подмножества и вызываем
  42. // функцию рекурсивно
  43. if (maxDistance >= epsilon) {
  44. approximatedPath =
  45. approximatedPath.concat(self.approximate(
  46. latLngArray.slice(0, maxDistancePointIndex + 1),
  47. epsilon, latLngExtractor));
  48.  
  49. approximatedPath =
  50. approximatedPath.concat(self.approximate(
  51. latLngArray.slice(maxDistancePointIndex),
  52. epsilon, latLngExtractor));
  53.  
  54. return approximatedPath;
  55. }
  56.  
  57. // Иначе возвращаем крайние точки кривой
  58. else {
  59. return [
  60. latLngArray[0],
  61. latLngArray[latLngArray.length - 1]
  62. ];
  63. }
  64. };
  65.  
  66. // Построение уравнения прямой, между начальной и конечной точкой,
  67. // в нормальном виде
  68. self.buildLineEquation = function (startXY, endXY) {
  69. var aParam = (endXY.y - startXY.y);
  70. var bParam = -1 * (endXY.x - startXY.x);
  71. var cParam = -1 * startXY.x * (endXY.y - startXY.y) +
  72. startXY.y * (endXY.x - startXY.x);
  73. return {a: aParam, b: bParam, c: cParam, startPoint: startXY,
  74. endPoint: endXY};
  75. };
  76.  
  77. // Нахождение расстояние от точки до прямой, заданной уравнением
  78. // в нормальном виде
  79. self.calculateDistanceToLine = function (pointCoords, lineEquation) {
  80. return Math.abs(lineEquation.a * pointCoords.x +
  81. lineEquation.b * pointCoords.y + lineEquation.c) /
  82. Math.sqrt(Math.pow(lineEquation.a, 2) +
  83. Math.pow(lineEquation.b, 2));
  84. };

, ,

Leave a Reply

Your email address will not be published. Required fields are marked *