convex hull problem

Angol

Főnév

convex hull problem (tsz. convex hull problems)

(informatika) konvex burok feladat

A konvex burok (angolul: convex hull) egy adott síkbeli (vagy térbeli) pont halmaz legkisebb konvex alakzata, amely tartalmazza az összes pontot. Képzeljük el, hogy a pontok köré egy rugalmas gumiszálat feszítünk – amikor elengedjük, a szál visszahúzódik és a pontok legkülső burkolatát képezi: ez a konvex burok.

Matematikailag: A konvex burok egy minimális konvex sokszög (vagy poliéder), amely tartalmazza az összes bemeneti pontot.

2. Miért fontos a konvex burok?

A konvex burok az egyik legalapvetőbb probléma a számítógépes geometria területén, és számos területen alkalmazható:

🌍 Alkalmazások:

Számítógépes grafika: objektumok körvonalának meghatározása
Robotika: akadálykerülés, térbeli navigáció
Adatbányászat: klaszterhatárok felismerése
Fizika: testek egyensúlyi állapotának vizsgálata
Geográfia: területhatárok, térképi elemzés

3. Konvexitás – alapfogalom

Egy síkbeli alakzat konvex, ha bármely két pontját összekötő egyenes teljesen benne marad az alakzaton belül.

Példa:

Konvex: kör, négyzet, háromszög
Nem konvex: csillag alakzat, homorú sokszög

4. A konvex burok formális definíciója

Legyen ${\textstyle P=\{p_{1},p_{2},...,p_{n}\}}$ egy pontok halmaza a síkban. A konvex burok:

${\text{Conv}}(P)={\text{legkisebb konvex halmaz, amely tartalmazza }}P{\text{-t.}}$

5. A konvex burok problémája

Bemenet:

Egy ${\textstyle n}$ darab síkbeli pontból álló halmaz.

Kimenet:

Ezek közül azon pontok sorozata (óramutató járásával megegyezően vagy ellentétesen), amelyek a konvex burkot alkotják – vagyis a legkülső pontokat összekötő konvex sokszöget.

6. Algoritmusok a konvex burok meghatározására

🔹 1. Graham-scan algoritmus

Rendezési alapú módszer
Először kiválasztja a „legalacsonyabb” pontot
Ezután a többi pontot szög szerinti sorrendbe rendezi
A burkot fokozatosan építi ki, közben konkáv fordulókat töröl

Időigény: O(n log n)

🔹 2. Jarvis march („Gift wrapping”)

Lépésenként „becsomagolja” a pontokat, mindig a legközelebbi balfordulóval lép
Jó kevés pont esetén

Időigény: O(nh), ahol ${\textstyle h}$ a burok pontjainak száma

🔹 3. Chan’s algoritmus

A Graham-scan és Jarvis-march kombinációja
Lineáris idejű az ${\textstyle h}$ ismeretében

Időigény: O(n log h)

7. Graham-scan lépései (részletesen)

Keresd meg a legalsó (legkisebb y-koordinátájú) pontot, ez lesz a referencia.
Rendezd a többi pontot a referenciaponthoz mért szög szerinti sorrendbe.
Menj végig a pontokon, és egy verem segítségével mindig csak akkor adj új pontot a burkolathoz, ha az balra fordulást jelent (nem konkáv).
A veremben lévő pontok végül a konvex burkot adják.

8. Balra vagy jobbra fordulás eldöntése

Ehhez használjuk a kereszt szorzatot:

Legyen három pont: ${\textstyle A,B,C}$ A következő vektorokat képezzük:

${\vec {AB}}=B-A,\quad {\vec {AC}}=C-A$

A következő determináns:

${\vec {AB}}\times {\vec {AC}}=(x_{B}-x_{A})(y_{C}-y_{A})-(y_{B}-y_{A})(x_{C}-x_{A})$

Ha ez > 0 → balra fordulás
Ha < 0 → jobbra fordulás
Ha = 0 → kollineáris (egy egyenesen vannak)

9. Példa – Konvex burok Pythonban (Graham-scan)

import matplotlib.pyplot as plt

def orientation(p, q, r):
    # Bal/jobb/egyenes meghatározás
    return (q[0]-p[0])*(r[1]-p[1]) - (q[1]-p[1])*(r[0]-p[0])

def convex_hull(points):
    points = sorted(points)
    lower = []
    for p in points:
        while len(lower) >= 2 and orientation(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and orientation(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

# Tesztpontok
pts = [(1,1), (2,5), (3,3), (5,3), (3,2), (2,2)]
hull = convex_hull(pts)

# Kirajzolás
x, y = zip(*pts)
hx, hy = zip(*(hull + [hull[0]]))
plt.plot(x, y, "o")
plt.plot(hx, hy, "r-")
plt.title("Konvex burok")
plt.grid(True)
plt.show()

10. Összefoglalás – kulcspontok

A konvex burok egy pontsokaság legkisebb konvex tartalmazó sokszöge
Fontos szerepet játszik a számítógépes geometriában és sok alkalmazási területen
A probléma megoldása hatékony algoritmusokkal történik: Graham-scan, Jarvis-march, Chan
A döntés, hogy egy pont „balra fordul-e”, geometriai műveletekkel (keresztszorzat) végezhető
Egyszerű Pythonban is implementálni és vizualizálni

További információk

convex hull problem - Szótár.net (en-hu)
convex hull problem - Sztaki (en-hu)
convex hull problem - Merriam–Webster
convex hull problem - Cambridge
convex hull problem - WordNet
convex hull problem - Яндекс (en-ru)
convex hull problem - Google (en-hu)
convex hull problem - Wikidata
convex hull problem - Wikipédia (angol)