Beräkningsgeometri

Beräkningsgeometri är en gren inom datavetenskap som sysslar med algoritmer för att lösa geometriska problem.

Det handlar om sådana uppgifter som triangulering, bygga ett konvext skrov, bestämma om ett objekt tillhör ett annat, hitta deras skärningspunkt, etc. De arbetar med sådana geometriska objekt som: punkt , linjesegment , polygon , cirkel ...

Beräkningsgeometri används inom mönsterigenkänning , datorgrafik , ingenjörsdesign , etc.

Vektoralgebra _

Ofta används för numeriska manipulationer koordinaterna för en punkt och en vektor.

Här överväger vi fallet med det vanliga kartesiska koordinatsystemet .

Längden på en vektor betecknas med . ${\overrightarrow {a}}=(x,y,z)$ ${\displaystyle |{\overrightarrow {a}}|={\sqrt {x^{2}+y^{2}+z^{2))))$

För två vektorer och deras addition definieras 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 av en vektor med en skalär k definieras som . I det här fallet ändras vektorns längd i tider. Om k < 0, så är vektorns riktning omvänd. ${\overrightarrow {a}}=(x,y,z)$ ${\overrightarrow {b}}=k{\overrightarrow {a}}=(kx,ky,kz)$ $|k|$

Den skalära produkten av vektorer och är lika 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))$

Korsprodukten av vektorer och är lika med . Detta är den enda operationen där minskningen av utrymmesdimensionen inte reduceras till ett enkelt förkastande av den tredje koordinaten (ersätter den med noll). Vanligtvis för tvådimensionella vektorer tas den tredje koordinaten för motsvarande tredimensionella vektorer som värdet på korsprodukten: . ${\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 av polygoner (polygoner)

En polygon är en sluten kurva i ett plan, som består av segment av räta linjer. Segmenten kallas polygonens sidor och deras ändar kallas polygonens hörn.

En polygon kallas enkel om den inte skär sig själv.

En polygon kallas konvex om alla dess inre vinklar är mindre än eller lika med 180 grader.

En kedja av hörn kallas monoton om någon vertikal linje skär den högst en gång. En polygon som består av två sådana kedjor kallas monoton.

Algoritmer

Grahams skanningsalgoritm är arbetskrävande . $O(n\log n)$
Snabb skalalgoritm - arbetsinsats , - i genomsnitt. $O(n^{2})$ $O(n\log n)$
Kirkpatricks algoritm är konstruktionen av ett konvext skrov av en uppsättning punkter på ett plan med hjälp av " dela och erövra "-metoden genom broar. Arbetsintensitet . $O(n\log n)$
Algoritm för att slå in presenter (Jarvis) - arbetsinsats , - antalet punkter i det konvexa skrovet. $O(nh)$ $h$
Chens algoritm - mödosamt , - antalet punkter i det konvexa skrovet. $O(n\log h)$ $h$
Algoritm för en punkt i en polygon - kontrollera om en given punkt tillhör en enkel polygon . $På)$
Strålmetod - en punkts tillhörighet till en enkel polygon . $På)$
Algoritm Bentley - Ottmann - sök efter alla skärningspunkter för segment på planet , - antalet skärningspunkter. $O((n+k)\log n)$ $k$

Se även

Algoritmer för beräkningsgeometri
18 poäng problem
Datortopologi

Litteratur

Preparata F., Shaimos M. Computational Geometry En introduktion. — M .: Mir, 1989. — 478 sid.
Berg M., Cheong O., Creveld M., Overmars M. Computational geometri. Algoritmer och applikationer = Computational Geometry: Algoritmer och applikationer. - M. : DMK-Press, 2016. - 438 sid. - ISBN 978-5-97060-406-9 .
Fox A., Pratt M. Computational geometry. Tillämpning inom design och produktion. — M .: Mir, 1982. — 304 sid.
Laszlo M. Beräkningsgeometri och datorgrafik i C++. - M. : BINOM, 1997. - 304 sid.
Skvortsov A.V. Delaunay-triangulering och dess tillämpning. - Tomsk: Tomsk University Publishing House, 2002. - 128 sid.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 33 Beräkningsgeometri // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. — 2:a upplagan. - M . : "Williams", 2005. - S. 1047 - 1084. - ISBN 5-8459-0857-4 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Beräkningsgeometri: Algoritmer och tillämpningar. - Springer, 2000. - 368 sid.
David M Mount. Beräkningsgeometri. - University of Maryland, 2002. - 122 sid.
Elmar Langetepe, Gabriel Zachmann. Geometriska datastrukturer för datorgrafik. - A. K. Peters, 2006. - 362 sid. — ISBN 1568812353 .
Hormoz Pirzadeh. Beräkningsgeometri med roterande bromsok. - McGill University, 1999. - 118 sid.
Jacob E. Goodman, Joseph O'Rourke. Handbok för diskret och beräkningsgeometri. - CRC Press LLC, 1997. - 956 sid.
Jianer Chen. Beräkningsgeometri: Metoder och tillämpningar. — Texas A&M University, 1996. — 228 sid.
Joseph O'Rourke. Computational Geometry in C. - Cambridge University Press, 1998. - 362 sid.
AR Forrest. Beräkningsgeometri. - serie 4. - Proc. Royal Society London, 1971. - 321 sid.