Számítógépes geometria

A számítási geometria a számítástechnikának egy olyan ága , amely geometriai problémák megoldására szolgáló algoritmusokkal foglalkozik.

Olyan feladatokkal foglalkozik, mint a háromszögelés, konvex hajótest építése, annak meghatározása, hogy egy objektum egy másikhoz tartozik-e, metszéspontjuk megtalálása stb. Olyan geometriai objektumokkal operálnak, mint: pont , vonalszakasz , sokszög , kör ...

A számítási geometriát mintafelismerésben , számítógépes grafikában , mérnöki tervezésben stb. használják.

Vektoralgebra _

A numerikus manipulációkhoz gyakran használják egy pont és egy vektor koordinátáit.

Itt a szokásos derékszögű koordinátarendszer esetét vesszük figyelembe .

Egy vektor hosszát jelöli . ${\overrightarrow {a}}=(x,y,z)$ ${\displaystyle |{\overrightarrow {a}}|={\sqrt {x^{2}+y^{2}+z^{2))))$

Két vektor és azok összeadása a következőképpen van meghatározva . ${\overrightarrow {a}}=(x_{1},y_{1},z_{1})$ ${\overrightarrow {b}}=(x_{2},y_{2},z_{2})$ ${\overrightarrow {a}}+{\overrightarrow {b}}=(x_{1}+x_{2},y_{1}+y_{2},z_{1}+z_{2})$

Egy vektor k skalárral való szorzatát a következőképpen határozzuk meg . Ebben az esetben a vektor hossza időnként változik. Ha k < 0, akkor a vektor iránya megfordul. ${\overrightarrow {a}}=(x,y,z)$ ${\overrightarrow {b}}=k{\overrightarrow {a}}=(kx,ky,kz)$ $|k|$

A és vektorok skaláris szorzata egyenlő . ${\overrightarrow {a}}=(x_{1},y_{1},z_{1})$ ${\overrightarrow {b}}=(x_{2},y_{2},z_{2})$ ${\displaystyle x_{1}x_{2}+y_{1}y_{2}+z_{1}z_{2))$

A és vektorok keresztszorzata egyenlő . Ez az egyetlen művelet, ahol a térdimenzió csökkentése nem redukálódik a harmadik koordináta egyszerű elutasítására (nullára cserélve). Általában kétdimenziós vektorok esetén a megfelelő háromdimenziós vektorok harmadik koordinátáját veszik fel a keresztszorzat értékének: . ${\overrightarrow {a}}=(x_{1},y_{1})$ ${\overrightarrow {b}}=(x_{2},y_{2})$ $\left\{y_{1}z_{2}-z_{1}y_{2},~z_{1}x_{2}-x_{1}z_{2}, ~x_{1}y_ {2}-y_{1}x_{2}\right\}$ ${\displaystyle x_{1}y_{2}-x_{2}y_{1))$

Sokszögek (sokszögek) típusai

A sokszög egy zárt görbe egy síkban, amely egyenes szakaszokból áll. A szakaszokat a sokszög oldalainak, a végeit pedig a sokszög csúcsainak nevezzük.

Egy sokszöget egyszerűnek nevezünk, ha nem metszi önmagát.

Egy sokszöget konvexnek nevezünk, ha minden belső szöge kisebb vagy egyenlő 180 fokkal.

Egy csúcsláncot monotonnak nevezünk, ha bármely függőleges vonal legfeljebb egyszer metszi azt. A két ilyen láncból álló sokszöget monotonnak nevezzük.

Algoritmusok

Graham szkennelési algoritmusa munkaigényes . $O(n\log n)$
Gyors shell algoritmus - munkaerő ráfordítás , - átlagosan. $O(n^{2})$ $O(n\log n)$
A Kirkpatrick-algoritmus egy ponthalmaz konvex testének felépítése egy síkon az „ oszd meg és uralkodj ” módszerrel hidakon keresztül. Munkaintenzitás . $O(n\log n)$
Ajándékcsomagolás algoritmusa (Jarvis) - munkaerő-ráfordítás , - a pontok száma a konvex hajótestben. $O(nh)$ $h$
Chen algoritmusa - munkaigény , - a pontok száma a konvex hajótestben. $O(n\log h)$ $h$
Egy sokszög pontjának algoritmusa - annak ellenőrzése, hogy egy adott pont egy egyszerű sokszöghez tartozik-e . $Tovább)$
Ray metódus - egy pont egy egyszerű sokszöghez való tartozása . $Tovább)$
Algoritmus Bentley - Ottmann - a szegmensek összes metszéspontjának keresése a síkon , - a metszéspontok száma. $O((n+k)\log n)$ $k$

Lásd még

Számítógépes geometriai algoritmusok
18 pontos probléma
Számítástechnikai topológia

Irodalom

Preparata F., Shaimos M. Számítógépes geometria Bevezetés. — M .: Mir, 1989. — 478 p.
Berg M., Cheong O., Creveld M., Overmars M. Számítógépes geometria. Algoritmusok és alkalmazások = Computational Geometry: Algorithms and Applications. - M. : DMK-Press, 2016. - 438 p. - ISBN 978-5-97060-406-9 .
Fox A., Pratt M. Számítógépes geometria. Alkalmazás a tervezésben és a gyártásban. — M .: Mir, 1982. — 304 p.
M. László Számítógépes geometria és számítógépes grafika C++ nyelven. - M. : BINOM, 1997. - 304 p.
Skvortsov A.V. Delaunay-háromszögelés és alkalmazása. - Tomszk: Tomszki Egyetemi Kiadó, 2002. - 128 p.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. 33. fejezet Számítógépes geometria // Algoritmusok: Konstrukció és elemzés = Bevezetés az algoritmusokba. — 2. kiadás. - M . : "Williams", 2005. - S. 1047 - 1084. - ISBN 5-8459-0857-4 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Számítógépes geometria: Algoritmusok és alkalmazások. - Springer, 2000. - 368 p.
David M Mount. Számítógépes geometria. - Marylandi Egyetem, 2002. - 122 p.
Elmar Langetepe, Gabriel Zachmann. Geometriai adatszerkezetek számítógépes grafikához. - A. K. Peters, 2006. - 362 p. — ISBN 1568812353 .
Hormoz Pirzadeh. Számítógépes geometria a forgó féknyergekkel. - McGill Egyetem, 1999. - 118 p.
Jacob E. Goodman, Joseph O'Rourke. A diszkrét és számítási geometria kézikönyve. - CRC Press LLC, 1997. - 956 p.
Jianer Chen. Számítógépes geometria: módszerek és alkalmazások. – Texas A&M University, 1996. – 228 p.
Joseph O'Rourke. Computational Geometry in C. - Cambridge University Press, 1998. - 362 p.
AR Forrest. Számítógépes geometria. - 4. sorozat. - Proc. Royal Society London, 1971. - 321 p.