Алгоритм Рамера-Дугласа-Пекера
Так непросто называется известный и широко применяемый при работе с векторной графикой и картографическими данными алгоритм уменьшения количества точек кривой, аппроксимированной большей серией точек.
Ниже показана консольная рекурсивная реализация алгоритма Рамера-Дугласа-Пекера на 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 [2092 просмотра]