Wikiszótár

Douglas-Peucker-algoritmus

Magyar

Kiejtés

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

Főnév

Douglas-Peucker-algoritmus

  1. (matematika)

Douglas-Peucker-algoritmus

A Douglas-Peucker-algoritmus egy hatékony és széles körben használt módszer vonalláncok egyszerűsítésére. Az algoritmus célja, hogy egy vonalláncot (töréspontok sorozatát) kevesebb ponttal közelítsen úgy, hogy a geometriai alakja a lehető legjobban megmaradjon.


Célja

  • Bemenet: Egy poligonális vonal (pontsorozat) és egy megengedett eltérés (( )).
  • Kimenet: Egy egyszerűsített vonal, amely kevesebb pontot tartalmaz, de a megadott eltérésen belül marad az eredeti vonalhoz képest.


Algoritmus működése

  1. Rekurzív felosztás:
    • Az algoritmus az eredeti vonal kezdőpontját és végpontját megtartja.
    • Megkeresi azt a közbülső pontot, amely a legnagyobb merőleges távolságra van a kezdőpont-végpont egyeneshez képest.
  2. Ellenőrzés:
    • Ha ez a legnagyobb távolság nagyobb, mint a megengedett eltérés (( )), akkor az adott pontot megtartja, és a vonalat két részre osztja.
    • A két részvonalat rekurzívan tovább egyszerűsíti.
  3. Megállás:
    • Ha a legnagyobb távolság a pontok és az egyenes között kisebb vagy egyenlő ( )-nel, akkor a közbülső pontokat elhagyja, és az egyenes szakaszt meghagyja.


Példa

Tegyük fel, hogy egy töréspontokból álló vonalat (( P_0, P_1, …, P_n )) szeretnénk egyszerűsíteni.

  1. Kezdőpont: ( P_0 ), végpont: ( P_n ).
  2. Keressük meg a legnagyobb távolságot a vonal ( P_0 )-( P_n ) egyeneséhez viszonyítva.
  3. Ha a távolság > ( ), akkor a vonalat kettéosztjuk a legtávolabbi pontnál, és a két részvonalon megismételjük a lépéseket.


Python Implementáció

Az alábbi kód a Douglas-Peucker-algoritmus implementációját mutatja be Pythonban: 

import numpy as np

def perpendicular_distance(point, line_start, line_end):
    """
    Kiszámítja a pont és egy egyenes szakasz közötti merőleges távolságot.
    """
    if np.all(line_start == line_end):
        return np.linalg.norm(point - line_start)
    return np.abs(np.cross(line_end - line_start, line_start - point)) / np.linalg.norm(line_end - line_start)

def douglas_peucker(points, epsilon):
    """
    Douglas-Peucker algoritmus vonallánc egyszerűsítésére.
    
    :param points: Pontsorozat (list vagy numpy array).
    :param epsilon: Megengedett eltérés.
    :return: Egyszerűsített pontsorozat.
    """
    # Ha kevesebb, mint 3 pont van, nem lehet egyszerűsíteni
    if len(points) < 3:
        return points

    # Legnagyobb távolság és indexének keresése
    line_start = points[0]
    line_end = points[-1]
    max_distance = 0
    index = 0

    for i in range(1, len(points) - 1):
        distance = perpendicular_distance(points[i], line_start, line_end)
        if distance > max_distance:
            index = i
            max_distance = distance

    # Ha a legnagyobb távolság nagyobb, mint epsilon, két részre bontjuk
    if max_distance > epsilon:
        left = douglas_peucker(points[:index + 1], epsilon)
        right = douglas_peucker(points[index:], epsilon)
        return np.vstack((left[:-1], right))
    else:
        # Ellenkező esetben csak a kezdő- és végpont marad meg
        return np.array([line_start, line_end])

# Példa adatok
points = np.array([[0, 0], [1, 0.1], [2, -0.1], [3, 5], [4, 6], [5, 7], [6, 8.1], [7, 9], [8, 9.1], [9, 9]])
epsilon = 1.0

# Algoritmus futtatása
simplified_points = douglas_peucker(points, epsilon)

# Eredmény kiíratása
print("Eredeti pontok:")
print(points)
print("\nEgyszerűsített pontok:")
print(simplified_points)

Kimenet

Eredeti pontok:
[[ 0.   0. ]
 [ 1.   0.1]
 [ 2.  -0.1]
 [ 3.   5. ]
 [ 4.   6. ]
 [ 5.   7. ]
 [ 6.   8.1]
 [ 7.   9. ]
 [ 8.   9.1]
 [ 9.   9. ]]

Egyszerűsített pontok:
[[ 0.  0.]
 [ 3.  5.]
 [ 9.  9.]]

Vizualizáció

Az algoritmus egyszerűsítette az eredeti pontsort úgy, hogy csak a fontos töréspontokat hagyta meg. A vonal alakja megmaradt, de sok felesleges pontot elhagyott.


Előnyök

  1. Hatékony: A rekurzív felosztás gyors és jól működik.
  2. Könnyen implementálható: A koncepció egyszerű és érthető.
  3. Rugalmas: A ( ) érték változtatásával szabályozható a pontosság.


Hátrányok

  1. Rekurzivitás: Nagyon nagy adathalmaz esetén a rekurzív hívások mélysége problémát okozhat.
  2. Nem mindig optimális: Az algoritmus lokális optimalizációt végez, tehát a globálisan legjobb megoldást nem garantálja.


Alkalmazások

  1. Térinformatika (GIS): Útvonalak és térképek egyszerűsítése.
  2. Számítógépes grafika: Görbék és alakzatok leegyszerűsítése.
  3. Adattömörítés: Folytonos vonalak tárolásának optimalizálása.
  4. Robotika: Mozgási útvonalak simítása.

A Douglas-Peucker-algoritmus gyors és hatékony megoldást nyújt vonalláncok egyszerűsítésére, ami számos alkalmazási területen kulcsfontosságú.

Fordítások

Tartalom

További információk

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