Beregningsgeometri

Beregningsgeometri er en gren af datalogi , der beskæftiger sig med algoritmer til løsning af geometriske problemer.

Det beskæftiger sig med sådanne opgaver som triangulering, bygning af et konveks skrog, afgør, om et objekt tilhører et andet, at finde deres skæringspunkt osv. De opererer med sådanne geometriske objekter som: punkt , linjestykke , polygon , cirkel ...

Beregningsgeometri bruges i mønstergenkendelse , computergrafik , ingeniørdesign mv.

Vektoralgebra _

Ofte brugt til numeriske manipulationer er koordinaterne for et punkt og en vektor.

Her betragter vi tilfældet med det sædvanlige kartesiske koordinatsystem .

Længden af en vektor er angivet med . ${\overrightarrow {a}}=(x,y,z)$ ${\displaystyle |{\overrightarrow {a}}|={\sqrt {x^{2}+y^{2}+z^{2))))$

For to vektorer og deres addition er defineret som . ${\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})$

Multiplikationen af en vektor med en skalar k er defineret som . I dette tilfælde ændres vektorens længde i gange. Hvis k < 0, så vendes vektorens retning. ${\overrightarrow {a}}=(x,y,z)$ ${\overrightarrow {b}}=k{\overrightarrow {a}}=(kx,ky,kz)$ $|k|$

Det skalære produkt af vektorer og er lig med . ${\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))$

Krydsproduktet af vektorer og er lig med . Dette er den eneste operation, hvor reduktionen af rumdimensionen ikke reduceres til en simpel afvisning af den tredje koordinat (erstatning af den med nul). Normalt for todimensionelle vektorer tages den tredje koordinat af de tilsvarende tredimensionelle vektorer som værdien af krydsproduktet: . ${\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))$

Typer af polygoner (polygoner)

En polygon er en lukket kurve i et plan, der består af segmenter af lige linjer. Segmenterne kaldes polygonens sider, og deres ender kaldes polygonens hjørner.

En polygon kaldes simpel, hvis den ikke skærer sig selv.

En polygon kaldes konveks, hvis alle dens indre vinkler er mindre end eller lig med 180 grader.

En kæde af hjørner kaldes monoton, hvis en lodret linje højst skærer den én gang. En polygon sammensat af to sådanne kæder kaldes monoton.

Algoritmer

Grahams scanningsalgoritme er arbejdskrævende . $O(n\log n)$
Hurtig shell-algoritme - arbejdsindsats , - i gennemsnit. $O(n^{2})$ $O(n\log n)$
Kirkpatricks algoritme er konstruktionen af et konvekst skrog af et sæt punkter på et plan ved hjælp af " del og hersk "-metoden gennem broer. Arbejdsintensitet . $O(n\log n)$
Algoritme til indpakning af gaver (Jarvis) - arbejdsindsats , - antallet af punkter i det konvekse skrog. $O(nh)$ $h$
Chens algoritme - besværligt , - antallet af punkter i det konvekse skrog. $O(n\log h)$ $h$
Algoritme for et punkt i en polygon - kontrollerer om et givet punkt hører til en simpel polygon . $På)$
Strålemetode - et punkts tilhørsforhold til en simpel polygon . $På)$
Algoritme Bentley - Ottmann - søg efter alle skæringspunkter for segmenter på planet , - antallet af skæringspunkter. $O((n+k)\log n)$ $k$

Se også

Computational Geometri Algoritmer
18 point problem
Computertopologi

Litteratur

Preparata F., Shaimos M. Computational Geometry En introduktion. — M .: Mir, 1989. — 478 s.
Berg M., Cheong O., Creveld M., Overmars M. Computational geometri. Algoritmer og applikationer = Computational Geometry: Algoritmer og applikationer. - M. : DMK-Press, 2016. - 438 s. - ISBN 978-5-97060-406-9 .
Fox A., Pratt M. Beregningsgeometri. Anvendelse i design og produktion. — M .: Mir, 1982. — 304 s.
Laszlo M. Beregningsgeometri og computergrafik i C++. - M. : BINOM, 1997. - 304 s.
Skvortsov A.V. Delaunay-triangulering og dens anvendelse. - Tomsk: Tomsk University Publishing House, 2002. - 128 s.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 33 Beregningsgeometri // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. — 2. udgave. - M . : "Williams", 2005. - S. 1047 - 1084. - ISBN 5-8459-0857-4 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Beregningsgeometri: Algoritmer og applikationer. - Springer, 2000. - 368 s.
David M Mount. Beregningsgeometri. - University of Maryland, 2002. - 122 s.
Elmar Langetepe, Gabriel Zachmann. Geometriske datastrukturer til computergrafik. - A. K. Peters, 2006. - 362 s. — ISBN 1568812353 .
Hormoz Pirzadeh. Beregningsgeometri med de roterende kalibere. - McGill University, 1999. - 118 s.
Jacob E. Goodman, Joseph O'Rourke. Håndbog i diskret og beregningsmæssig geometri. - CRC Press LLC, 1997. - 956 s.
Jianer Chen. Beregningsgeometri: Metoder og anvendelser. — Texas A&M University, 1996. — 228 s.
Joseph O'Rourke. Computational Geometry in C. - Cambridge University Press, 1998. - 362 s.
AR Skov. Beregningsgeometri. - serie 4. - Proc. Royal Society London, 1971. - 321 s.