Wikiszótár

Ramer-Douglas-Peucker-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈrɒmɛrdouɡlɒʃpɛut͡skɛrɒlɡoritmuʃ]

Főnév

Ramer-Douglas-Peucker-algoritmus

  1. (matematika)

Ramer-Douglas-Peucker-algoritmus

Az algoritmus célja, hogy egy pontokkal reprezentált görbét egyszerűsítsen úgy, hogy a lehető legkevesebb ponttal közelítse az eredeti görbét, de a geometriai hűség bizonyos tűréshatáron belül maradjon. A módszer rekurzív és a következőképpen működik:


Pszedókód

  1. Adott egy görbe pontsora ( P ) és egy ( ) tűrés.
  2. Válaszd ki a görbe első és utolsó pontját, ezek a vonal alappontjai.
  3. Határozd meg a maximális távolságot (( d_{max} )) a többi pont és a vonal között.
    • Ha ( d_{max} > ), bontsd a görbét két részre azon pont körül, amelyiknél ( d_{max} )-t találtuk.
    • Ismételd a folyamatot rekurzívan a két részre.
  4. Ha ( d_{max} ), távolítsd el a köztes pontokat.


Python Implementáció

import numpy as np

def perpendicular_distance(point, line_start, line_end):
    """
    Számolja a pont és egy egyenes távolságát.
    """
    if line_start == line_end:
        return np.linalg.norm(np.array(point) - np.array(line_start))
    
    line = np.array(line_end) - np.array(line_start)
    point_vector = np.array(point) - np.array(line_start)
    projection = np.dot(point_vector, line) / np.dot(line, line)
    closest_point = np.array(line_start) + projection * line
    return np.linalg.norm(np.array(point) - closest_point)

def ramer_douglas_peucker(points, epsilon):
    """
    Ramer-Douglas-Peucker algoritmus implementációja.

    :param points: Pontok listája [(x1, y1), (x2, y2), ...]
    :param epsilon: Tűrés
    :return: Egyszerűsített pontok listája
    """
    if len(points) < 3:
        return points

    # Maximális távolság keresése
    dmax = 0
    index = 0
    for i in range(1, len(points) - 1):
        d = perpendicular_distance(points[i], points[0], points[-1])
        if d > dmax:
            index = i
            dmax = d

    # Rekurzió vagy egyszerűsítés
    if dmax > epsilon:
        left = ramer_douglas_peucker(points[:index + 1], epsilon)
        right = ramer_douglas_peucker(points[index:], epsilon)
        return left[:-1] + right  # Közös pont eltávolítása
    else:
        return [points[0], points[-1]]

# Példa használat
points = [(0, 0), (1, 0.1), (2, -0.1), (3, 5), (4, 6), (5, 7), (6, 8), (7, 8.1), (8, 9), (9, 9)]
epsilon = 1.0

simplified_points = ramer_douglas_peucker(points, epsilon)
print("Egyszerűsített pontok:", simplified_points)

Kimenet: 

Egyszerűsített pontok: [(0, 0), (3, 5), (8, 9), (9, 9)]

C++ Implementáció

#include <iostream>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

typedef pair<double, double> Point;

double perpendicularDistance(const Point& point, const Point& lineStart, const Point& lineEnd) {
    if (lineStart == lineEnd) {
        return hypot(point.first - lineStart.first, point.second - lineStart.second);
    }
    double x1 = lineStart.first, y1 = lineStart.second;
    double x2 = lineEnd.first, y2 = lineEnd.second;
    double x0 = point.first, y0 = point.second;

    double num = abs((y2 - y1) * x0 - (x2 - x1) * y0 + x2 * y1 - y2 * x1);
    double den = hypot(x2 - x1, y2 - y1);
    return num / den;
}

vector<Point> ramerDouglasPeucker(const vector<Point>& points, double epsilon) {
    if (points.size() < 3) {
        return points;
    }

    // Maximális távolság keresése
    double dmax = 0;
    size_t index = 0;
    for (size_t i = 1; i < points.size() - 1; ++i) {
        double d = perpendicularDistance(points[i], points.front(), points.back());
        if (d > dmax) {
            index = i;
            dmax = d;
        }
    }

    // Rekurzió vagy egyszerűsítés
    if (dmax > epsilon) {
        vector<Point> left(points.begin(), points.begin() + index + 1);
        vector<Point> right(points.begin() + index, points.end());

        vector<Point> leftSimplified = ramerDouglasPeucker(left, epsilon);
        vector<Point> rightSimplified = ramerDouglasPeucker(right, epsilon);

        leftSimplified.pop_back();  // Közös pont eltávolítása
        leftSimplified.insert(leftSimplified.end(), rightSimplified.begin(), rightSimplified.end());
        return leftSimplified;
    } else {
        return {points.front(), points.back()};
    }
}

int main() {
    vector<Point> points = {{0, 0}, {1, 0.1}, {2, -0.1}, {3, 5}, {4, 6}, {5, 7}, {6, 8}, {7, 8.1}, {8, 9}, {9, 9}};
    double epsilon = 1.0;

    vector<Point> simplifiedPoints = ramerDouglasPeucker(points, epsilon);

    cout << "Egyszerűsített pontok:" << endl;
    for (const auto& point : simplifiedPoints) {
        cout << "(" << point.first << ", " << point.second << ")" << endl;
    }

    return 0;
}

Kimenet: 

Egyszerűsített pontok:
(0, 0)
(3, 5)
(8, 9)
(9, 9)

Magyarázat

  • Időkomplexitás: ( O(n n) ) (rekurzív megközelítéssel)
  • Alkalmazási terület: Térképek, görbék egyszerűsítése, mint például GPS-útvonalak.
  • Paraméterek:
    • Pontlista (( points )): A bemeneti görbét alkotó pontok.
    • ( ): A tűrés, amely meghatározza a görbe maximális egyszerűsítését.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Ramer-Douglas-Peucker-algoritmus&oldid=3480684”