Geometrie computațională

Geometria computațională este o ramură a informaticii care se ocupă de algoritmi pentru rezolvarea problemelor geometrice.

Se ocupă de sarcini precum triangularea, construirea unei carcase convexe, determinarea dacă un obiect aparține altuia, găsirea intersecției lor etc. Acestea operează cu obiecte geometrice precum: punct , segment de linie , poligon , cerc ...

Geometria computațională este utilizată în recunoașterea modelelor , grafica pe computer , proiectarea inginerească etc.

Algebră vectorială

Deseori folosite pentru manipulări numerice sunt coordonatele unui punct și ale unui vector.

Aici luăm în considerare cazul sistemului de coordonate carteziene obișnuit .

Lungimea unui vector se notează cu . ${\overrightarrow {a}}=(x,y,z)$ $|{\overrightarrow {a}}|={\sqrt {x^{2}+y^{2}+z^{2)))$

Pentru doi vectori și adăugarea lor este definită ca . ${\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})$

Înmulțirea unui vector cu un scalar k este definită ca . În acest caz, lungimea vectorului se modifică în timp. Dacă k < 0, atunci direcția vectorului este inversată. ${\overrightarrow {a}}=(x,y,z)$ ${\overrightarrow {b}}=k{\overrightarrow {a}}=(kx,ky,kz)$ $|k|$

Produsul scalar al vectorilor și este egal cu . ${\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))$

Produsul încrucișat al vectorilor și este egal cu . Aceasta este singura operație în care reducerea dimensiunii spațiului nu se reduce la o simplă respingere a celei de-a treia coordonate (înlocuind-o cu zero). De obicei, pentru vectorii bidimensionali, a treia coordonată a vectorilor tridimensionali corespunzători este luată ca valoare a produsului încrucișat: . ${\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))$

Tipuri de poligoane (poligoane)

Un poligon este o curbă închisă într-un plan, constând din segmente de linii drepte. Segmentele sunt numite laturile poligonului, iar capetele lor sunt numite vârfuri ale poligonului.

Un poligon se numește simplu dacă nu se intersectează.

Un poligon se numește convex dacă toate unghiurile sale interioare sunt mai mici sau egale cu 180 de grade.

Un lanț de vârfuri se numește monoton dacă orice linie verticală îl intersectează cel mult o dată. Un poligon compus din două astfel de lanțuri se numește monoton.

Algoritmi

Algoritmul de scanare al lui Graham necesită forță de muncă . $O(n\log n)$
Algoritm rapid shell - input de muncă , - în medie. $O(n^{2})$ $O(n\log n)$
Algoritmul lui Kirkpatrick este construirea unei carcase convexe a unui set de puncte pe un plan folosind metoda „ împărțiți și cuceriți ” prin poduri. Intensitatea muncii . $O(n\log n)$
Algoritm pentru împachetarea cadourilor (Jarvis) - forță de muncă , - numărul de puncte din carcasa convexă. $O(nh)$ $h$
Algoritmul lui Chen - laboriozitatea , - numărul de puncte din carcasa convexă. $O(n\log h)$ $h$
Algoritmul unui punct dintr-un poligon - verificarea dacă un punct dat aparține unui poligon simplu . $Pe)$
Metoda raze - apartenența unui punct la un poligon simplu . $Pe)$
Algoritmul Bentley - Ottmann - caută toate punctele de intersecție ale segmentelor de pe plan , - numărul de puncte de intersecție. $O((n+k)\log n)$ $k$

Vezi și

Algoritmi de geometrie computațională
Problema cu 18 puncte
Topologie de calcul

Literatură

Preparata F., Shaimos M. Computational Geometry O introducere. — M .: Mir, 1989. — 478 p.
Berg M., Cheong O., Creveld M., Overmars M. Computational geometry. Algoritmi și aplicații = Computational Geometry: Algorithms and Applications. - M. : DMK-Press, 2016. - 438 p. - ISBN 978-5-97060-406-9 .
Fox A., Pratt M. Computational geometry. Aplicare în proiectare și producție. — M .: Mir, 1982. — 304 p.
Laszlo M. Geometrie computațională și grafică pe computer în C++. - M. : BIOM, 1997. - 304 p.
Skvortsov A.V. Triangulația Delaunay și aplicarea acesteia. - Tomsk: Editura Universității Tomsk, 2002. - 128 p.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capitolul 33 Geometrie computațională // Algoritmi: Construcție și analiză = Introducere în algoritmi. — ediția a II-a. - M . : „Williams”, 2005. - S. 1047 - 1084. - ISBN 5-8459-0857-4 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Geometrie computațională: algoritmi și aplicații. - Springer, 2000. - 368 p.
David M Mount. Geometrie computațională. - Universitatea din Maryland, 2002. - 122 p.
Elmar Langetepe, Gabriel Zachmann. Structuri geometrice de date pentru grafică pe computer. - A. K. Peters, 2006. - 362 p. — ISBN 1568812353 .
Hormoz Pirzadeh. Geometrie computațională cu șubletele rotative. - Universitatea McGill, 1999. - 118 p.
Jacob E. Goodman, Joseph O'Rourke. Manual de geometrie discretă și computațională. - CRC Press LLC, 1997. - 956 p.
Jianer Chen. Geometrie computațională: metode și aplicații. — Universitatea Texas A&M, 1996. — 228 p.
Joseph O'Rourke. Computational Geometry in C. - Cambridge University Press, 1998. - 362 p.
AR Forrest. Geometrie computațională. - seria 4. - Proc. Royal Society London, 1971. - 321 p.