convex hull

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.

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:

$${\displaystyle {\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.

• 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.

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)

• 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

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

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

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.

#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, H, P) <= 0) k--;
        H = P;
    }

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

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

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, points, 'o')
for simplex in hull.simplices:
    plt.plot(points, points, 'k-')
plt.fill(points, points, 'lightblue', alpha=0.3)
plt.title("Convex Hull")
plt.show()

• 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)

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.

• 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)