NézetNyomtat

26. óra
Címkék > Óra

Grafikai algoritmusok: töröttvonal és konvex burok

Peregi Tamás

Alapok

Problémafelvetés

Adott N pont a 2 v. 3 dimenziós térben, koordinátákkal megadva. A koordináták egész számok. A ponthalmazzal kapcsolatos geometriai objektumokat állítunk elő.

Miért nem számolunk lebegőpontos számokkal?

#include<iostream>
#include<cmath>

int main() {
    double a = 13622342.2746364;
    double b = 4673563.2384912;

    std::cout << 12*a*b-12*b*<< std::endl;
}
A fenti program matematikai várakozásainkkal szemben a következő eredményre vezet:
-0.125
Ennek oka az, hogy a lebegőpontos számok aritmetikája nem azonos a valós számok aritmetikájával. További részletek a számábrázolással foglalkozó írásokban találhatók. Például: számábrázolások.

Pontok rendezése az 1-es síknegyedben

$ B>A \Leftrightarrow \beta > \alpha \Leftrightarrow \tan \beta > \tan \alpha \Leftrightarrow \frac{y_B}{x_B} > \frac{y_A}{x_A} \Leftrightarrow y_B\cdot x_A > y_A\cdot x_B \Leftrightarrow 0 > y_Ax_B-y_Bx_A $
Ha két pont forgásiránya azonos, akkor origótól mért távolságuk szerint rendezhetők. Ehhez nem kell négyzetre emelni, elég az x koordinátákat összehasonlítani, vagy ha azok is egyenlők, akkor az y koordinátákat.

Egy pont egy egyenes melyik partján van?

Ha azt szeretnénk tudni, hogy egy $P_2$ pont a $P_0P_1$ egyenes melyik partján van, akkor elég a $\overrightarrow{P_0P_1}$ és $\overrightarrow{P_0P_2}$ vektorok forgásirányát összehasonlítani.

Forgás irány függvény

Pontok összekötése nem metsző töröttvonallal

Adott N pont az első síknegyedben. Kössük össze őket önmagát nem metsző töröttvonallal.

Algoritmus

A pontokat rendezzük forgásirány, és azon belül origótól való távolság szerint. Ezután a rendezés sorrendjében történő összekötés megfelelő.






Példa

.BE.KI
6
2 0
1 4
0 2
3 2
2 4
2 6
6
1 4 5 6 2 3

Konvex burok

Adott N pont az első síknegyedben. Határozzuk meg a pontok konvex burkát!

Tesztadatok