Wikiszótár

Kirkpatrick-Seidel-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈkirkpɒtrit͡skʃɛjidɛlɒlɡoritmuʃ]

Főnév

Kirkpatrick-Seidel-algoritmus

  1. (matematika)

A Kirkpatrick-Seidel-algoritmus egy hatékony algoritmus a kétdimenziós sík konvex burkának meghatározására. Az algoritmus a “QuickHull” vagy a “Delaunay-háromszögezés” alternatívájaként ismert, és gyakran nevezik “szalag algoritmusnak” (“Divide and Conquer”) a megközelítése miatt. Ez a módszer különösen hatékony, mivel időbonyolultsága (O(n n)).


Probléma definiálása

Adott (n) darab pont a kétdimenziós síkon, cél a pontok konvex burkának meghatározása. A konvex burok az a legkisebb konvex sokszög, amely tartalmazza az összes pontot.


Algoritmus működése

Az algoritmus a “divide and conquer” (oszd meg és uralkodj) stratégiát alkalmazza: 1. Rendezés: - Először a pontokat növekvő sorrendbe rendezi az (x)-koordináták szerint. 2. Felbontás: - Az algoritmus először meghatározza a konvex burok felső részét. - Majd külön az alsó részt számolja ki. 3. Felső konvex rész meghatározása: - Az (x)-tengely mentén felosztja a síkot egy középpontra (median). - Az alhalmazokból iteratív módon kiválasztja azokat a pontokat, amelyek hozzájárulnak a konvex burokhoz. 4. Összeállítás: - A felső és az alsó részt összeilleszti, így megkapjuk a teljes konvex burkot.

Az algoritmus hatékonysága abban rejlik, hogy a részek összeállítása lineáris időben történik.


Pszeudokód

function KirkpatrickSeidel(points):
    Rendezd a pontokat növekvő sorrendbe az x-koordinájuk alapján.
    oszd meg a pontokat bal és jobb alhalmazokra a medián alapján.

    Felső_burok = Meghatározza a konvex burok felső részét:
        - Kiválasztja a legfelső pontot, majd iteratív módon azokat a pontokat, amelyek kívül esnek az aktuális konvex burokon.
    
    Alsó_burok = Meghatározza a konvex burok alsó részét:
        - Hasonló eljárás az alsó rész kiszámítására.

    Térj vissza Felső_burok + Alsó_burok

Python implementáció

def cross_product(o, a, b):
    """Kereszttermék a pontok között: o a középpont."""
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def kirkpatrick_seidel(points):
    # Rendezés x-koordináták szerint
    points = sorted(points)

    # Felső konvex burok meghatározása
    upper = []
    for p in points:
        while len(upper) >= 2 and cross_product(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    # Alsó konvex burok meghatározása
    lower = []
    for p in reversed(points):
        while len(lower) >= 2 and cross_product(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    # A teljes konvex burok (az utolsó pontokat ne ismételjük meg)
    return upper[:-1] + lower[:-1]


# Példa használat
points = [(0, 0), (1, 1), (2, 2), (3, 0), (0, 3), (3, 3)]
convex_hull = kirkpatrick_seidel(points)
print("Konvex burok pontjai:", convex_hull)

C++ implementáció

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
    bool operator<(const Point& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

// Kereszttermék számítása
int crossProduct(Point o, Point a, Point b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

// Kirkpatrick-Seidel algoritmus
vector<Point> kirkpatrickSeidel(vector<Point>& points) {
    sort(points.begin(), points.end()); // Rendezés x szerint

    // Felső konvex burok
    vector<Point> upper;
    for (const auto& p : points) {
        while (upper.size() >= 2 && crossProduct(upper[upper.size() - 2], upper.back(), p) <= 0) {
            upper.pop_back();
        }
        upper.push_back(p);
    }

    // Alsó konvex burok
    vector<Point> lower;
    for (auto it = points.rbegin(); it != points.rend(); ++it) {
        while (lower.size() >= 2 && crossProduct(lower[lower.size() - 2], lower.back(), *it) <= 0) {
            lower.pop_back();
        }
        lower.push_back(*it);
    }

    // Összesítés, az utolsó pontokat ne ismételjük meg
    upper.pop_back();
    lower.pop_back();
    upper.insert(upper.end(), lower.begin(), lower.end());

    return upper;
}

int main() {
    vector<Point> points = {{0, 0}, {1, 1}, {2, 2}, {3, 0}, {0, 3}, {3, 3}};
    vector<Point> convexHull = kirkpatrickSeidel(points);

    cout << "Konvex burok pontjai:" << endl;
    for (const auto& p : convexHull) {
        cout << "(" << p.x << ", " << p.y << ")" << endl;
    }

    return 0;
}

Példa bemenet és kimenet

Bemenet

Pontok: ((0,0), (1,1), (2,2), (3,0), (0,3), (3,3))

Kimenet

Konvex burok pontjai: - Python: [(0, 0), (3, 0), (3, 3), (0, 3)] - C++: (0, 0), (3, 0), (3, 3), (0, 3)


Összegzés

A Kirkpatrick-Seidel algoritmus előnye a hatékonysága ((O(n n))), valamint az egyszerű és logikus oszd-meg-és-uralkodj megközelítés. Ez különösen hasznos nagyobb pontkészletek esetén, például térinformatikai vagy számítógépes grafikai alkalmazásokban.

Fordítások

Tartalom

További információk

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