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*a << std::endl;
}
A fenti program matematikai várakozásainkkal szemben a következő eredményre vezet:
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
