convex hull

Angol

Főnév

convex hull (tsz. convex hulls)

1. (informatika) konvex burok

---

A convex hull (konvex burok) egy adott pontkészlet legkisebb konvex halmaza, amely tartalmazza az összes pontot. Geometriailag elképzelheted úgy, mint amikor egy rugalmas gumiszálat feszítesz ki a pontok köré – a gumiszál körbefogja a pontokat, ez a konvex burok.

---

1. Definíció

Formálisan: Legyen ${\textstyle S\subset \mathbb {R} ^{n}}$ egy pontkészlet.

A convex hull (jele: ${\textstyle {\text{conv}}(S)}$) az összes olyan konvex kombináció halmaza, amely a ${\textstyle S}$ pontjaiból áll:

$${\text{conv}}(S)=\left\{\sum _{i=1}^{k}\lambda _{i}x_{i}\ {\Bigg \vert }\ x_{i}\in S,\ \lambda _{i}\geq 0,\ \sum _{i=1}^{k}\lambda _{i}=1\right\}$$

Ez tehát a legkisebb konvex halmaz, amely tartalmazza ${\textstyle S}$-t.

---

2. Geometriai intuíció

• 2D-ben: a pontokat összekötő konvex sokszög (poligon), ami nem szakad meg és nem hajlik be.
• 3D-ben: a pontokból képzett konvex poliéder.
• Általánosan: konvex test ${\textstyle \mathbb {R} ^{n}}$-ben.

---

3. Tulajdonságok

Tulajdonság	Leírás
Konvex	Bármely két pont közti szakasz is benne van
Legkisebb	Nincs kisebb konvex halmaz, ami tartalmazza az összes pontot
Zárt	A konvex burok mindig zárt halmaz
Síkban	Legkevesebb ${\textstyle \leq n}$ pont határozza meg (sokszög)

---

4. Alkalmazási területek

• Számítógépes grafika: objektumok határolása, ütközésvizsgálat
• Gépi tanulás: klaszterek burkolása
• Számítógépes geometria: térkitöltés, alakfelismerés
• Optimalizálás: megengedett tartomány definiálása
• Robotika: pályatervezés akadályok között
• GIS (térinformatika): területek körbehúzása térképeken

---

5. Algoritmusok a konvex burok meghatározására (2D)

a) Graham scan – ${\textstyle O(n\log n)}$

1. Legalsó pont kiválasztása
2. Sorba rendezés polárszög szerint
3. Stack-alapú építés (fordulásvizsgálat)

b) Jarvis march (gift wrapping) – ${\textstyle O(nh)}$

1. Legbaloldalibb ponttal indul
2. Körbejárja a pontokat a következő „legbalra eső” irányban

---

6. 2D példa – Graham Scan (vizuális)

Adott pontok:

(0,0), (1,1), (2,2), (0,3), (3,0), (3,3), (1,2)

A konvex burok ezek köré húzott minimális konvex sokszög:

(0,0) → (3,0) → (3,3) → (0,3) → vissza (0,0)

A belső pontok, mint (1,1) vagy (1,2), nem részei a burokperemnek.

---

7. C++ példa – Graham Scan vázlat

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

struct Point {
    int x, y;
};

int cross(const Point& O, const Point& A, const Point& B) {
    return (A.x - O.x)*(B.y - O.y) - (A.y - O.y)*(B.x - O.x);
}

std::vector<Point> convexHull(std::vector<Point> P) {
    int n = P.size(), k = 0;
    if (n <= 3) return P;
    std::vector<Point> H(2*n);

    std::sort(P.begin(), P.end(), [](Point a, Point b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

    // Alsó burok
    for (int i = 0; i < n; ++i) {
        while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    // Felső burok
    for (int i = n-2, t = k+1; i >= 0; --i) {
        while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
        H[k++] = P[i];
    }

    H.resize(k-1);
    return H;
}

---

8. Konvex burok Pythonban (matplotlib + scipy)

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull

points = np.random.rand(30, 2)
hull = ConvexHull(points)

plt.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
plt.fill(points[hull.vertices,0], points[hull.vertices,1], 'lightblue', alpha=0.3)
plt.title("Convex Hull")
plt.show()

---

9. Tulajdonságok, amiket használunk

• Konvex kombináció: a burok minden pontja ilyen
• Extrém pontok: csak azok szerepelnek a konvex burok peremén
• Affine invariancia: a konvex burok affine transzformáció alatt invariáns (arányok, eltolás megtartott)

---

10. Összefoglalás

Fogalom	Jelentés
Convex hull	Legkisebb konvex halmaz, amely tartalmaz egy adott pontkészletet
Matematikai alak	Minden konvex kombinációja a pontoknak
2D jelentés	Konvex sokszög, ami körbezárja a pontokat
Algoritmusok	Graham scan, Jarvis march, QuickHull
Felhasználás	Grafika, AI, térinformatika, klaszterezés, optimalizáció

---

A konvex burok segít geometriai struktúrák egyszerűsítésében, komplex rendszerek körülhatárolásában és matematikai optimalizálásban. Elengedhetetlen a számítógépes geometria alapfogalmai között.

További információk

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