Алгоритм Рамера-Дугласа-Пекера

Так непросто называется известный и широко применяемый при работе с векторной графикой и картографическими данными алгоритм уменьшения количества точек кривой, аппроксимированной большей серией точек.

Ниже показана консольная рекурсивная реализация алгоритма Рамера-Дугласа-Пекера на C++, проверенная в консоли Visual Studio 2019.

#include <iostream>
#include <cmath>
#include <utility>
#include <vector>
#include <stdexcept>
#include <clocale>
#include <Windows.h> /* только для русификации в консоли */
using namespace std;

typedef std::pair<double, double> Point;

double calculateDistance(const Point& pt, const Point& lineStart, const Point& lineEnd) {
 double dx = lineEnd.first - lineStart.first;
 double dy = lineEnd.second - lineStart.second;
 //Нормализовать
 double mag = pow(pow(dx, 2.0) + pow(dy, 2.0), 0.5);
 if (mag > 0.0) {
  dx /= mag; dy /= mag;
 }
 double pvx = pt.first - lineStart.first;
 double pvy = pt.second - lineStart.second;
 //Получить скалярное произведение (проекция pv на нормализованное направление)
 double pvdot = dx * pvx + dy * pvy;
 //Вектор направления
 double dsx = pvdot * dx;
 double dsy = pvdot * dy;
 //Вычесть его из pv
 double ax = pvx - dsx;
 double ay = pvy - dsy;
 return pow(pow(ax, 2.0) + pow(ay, 2.0), 0.5);
}

void mainAlgorithm(const vector<Point>& pointList, double epsilon, vector<Point>& out) {
 if (pointList.size() < 2) throw invalid_argument("Передано меньше 2 точек");

 //Найти точку с максимальным расстоянием от отрезка [start; end]
 double dmax = 0.0;
 size_t index = 0;
 size_t end = pointList.size() - 1;
 for (size_t i = 1; i < end; i++) {
  double d = calculateDistance(pointList[i], pointList[0], pointList[end]);
  if (d > dmax) {
   index = i; dmax = d;
  }
 }
 if (dmax > epsilon) {
  //Если максимальное расстояние больше epsilon, рекурсивно упростить
  vector<Point> recResults1;
  vector<Point> recResults2;
  vector<Point> firstLine(pointList.begin(), pointList.begin() + index + 1);
  vector<Point> lastLine(pointList.begin() + index, pointList.end());
  mainAlgorithm(firstLine, epsilon, recResults1);
  mainAlgorithm(lastLine, epsilon, recResults2);
  //Построить список с результатами
  out.assign(recResults1.begin(), recResults1.end() - 1);
  out.insert(out.end(), recResults2.begin(), recResults2.end());
  if (out.size() < 2)
   throw runtime_error("Проблема с построением списка вывода");
 }
 else {
  //Иначе вернуть точки start и end
  out.clear();
  out.push_back(pointList[0]);
  out.push_back(pointList[end]);
 }
}

int main() {
 setlocale(LC_ALL, "Rus");
 SetConsoleCP(1251); SetConsoleOutputCP(1251); //Только Studio


 vector<Point> pointList;
 vector<Point> pointListOut;
 pointList.push_back(Point(0.0, 0.0));
 pointList.push_back(Point(1.0, 0.1));
 pointList.push_back(Point(2.0, -0.1));
 pointList.push_back(Point(3.0, 5.0));
 pointList.push_back(Point(4.0, 6.0));
 pointList.push_back(Point(5.0, 7.0));
 pointList.push_back(Point(6.0, 8.1));
 pointList.push_back(Point(7.0, 9.0));
 pointList.push_back(Point(8.0, 9.0));
 pointList.push_back(Point(9.0, 9.0));

 mainAlgorithm(pointList, 1.0, pointListOut);

 cout << "Результаты" << endl;
 for (size_t i = 0; i < pointListOut.size(); i++) {
  cout << pointListOut[i].first << "," << pointListOut[i].second << endl;
 }
 
 cin.get();
 return 0;
}

30.11.2019, 12:41 [2079 просмотров]