Laskennallinen geometria

Laskennallinen geometria on tietojenkäsittelytieteen ala , joka käsittelee algoritmeja geometristen ongelmien ratkaisemiseksi.

Se käsittelee sellaisia tehtäviä kuin kolmiomittaus, kuperan rungon rakentaminen, objektien kuuluvuuden määrittäminen, niiden leikkauspisteiden löytäminen jne. Ne toimivat geometristen kohteiden kanssa, kuten: piste , jana , monikulmio , ympyrä ...

Laskennallista geometriaa käytetään hahmontunnistuksessa , tietokonegrafiikassa , suunnittelussa jne.

Vektorialgebra _

Usein numeeriseen käsittelyyn käytetään pisteen ja vektorin koordinaatteja.

Tässä tarkastellaan tavallista suorakulmaista koordinaattijärjestelmää .

Vektorin pituus on merkitty . ${\overrightarrow {a}}=(x,y,z)$ ${\displaystyle |{\overrightarrow {a}}|={\sqrt {x^{2}+y^{2}+z^{2))))$

Kahdelle vektorille ja niiden yhteenlasku on määritelty . ${\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})$

Vektorin kertolasku skalaarilla k määritellään muodossa . Tässä tapauksessa vektorin pituus muuttuu kertaa. Jos k < 0, niin vektorin suunta on käänteinen. ${\overrightarrow {a}}=(x,y,z)$ ${\overrightarrow {b}}=k{\overrightarrow {a}}=(kx,ky,kz)$ $|k|$

Vektorien ja skalaaritulo on yhtä suuri kuin . ${\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))$

Ristitulo vektorit ja on yhtä suuri kuin . Tämä on ainoa operaatio, jossa avaruuden ulottuvuuden pienennystä ei ole pelkistetty kolmannen koordinaatin yksinkertaiseksi hylkäämiseksi (korvaamalla se nollalla). Yleensä kaksiulotteisille vektoreille ristitulon arvoksi otetaan vastaavien kolmiulotteisten vektorien kolmas koordinaatti: . ${\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))$

Polygonien tyypit (polygonit)

Monikulmio on tasossa oleva suljettu käyrä, joka koostuu suorien viivojen segmenteistä. Jantoja kutsutaan monikulmion sivuiksi ja niiden päitä polygonin kärjeksi.

Monikulmiota kutsutaan yksinkertaiseksi, jos se ei leikkaa itseään.

Monikulmiota kutsutaan kuperaksi, jos kaikki sen sisäkulmat ovat pienempiä tai yhtä suuria kuin 180 astetta.

Piikkiketjua kutsutaan monotoniseksi, jos mikä tahansa pystysuora viiva leikkaa sen enintään kerran. Monikulmiota, joka koostuu kahdesta tällaisesta ketjusta, kutsutaan monotoniksi.

Algoritmit

Grahamin skannausalgoritmi on työvoimavaltainen . $O(n\log n)$
Nopea shell-algoritmi - työpanos , - keskimäärin. $O(n^{2})$ $O(n\log n)$
Kirkpatrickin algoritmi on kuperan rungon rakentaminen tason pistejoukosta " jakaa ja hallitse " -menetelmällä siltojen kautta. Työvoiman intensiteetti . $O(n\log n)$
Lahjojen pakkaamisen algoritmi (Jarvis) - työpanos , - kuperan rungon pisteiden lukumäärä. $O(nh)$ $h$
Chenin algoritmi - työläisyys , - kuperan rungon pisteiden lukumäärä. $O(n\log h)$ $h$
Monikulmion pisteen algoritmi - tarkastaa, kuuluuko tietty piste yksinkertaiseen monikulmioon . $Päällä)$
Sädemenetelmä - pisteen kuuluminen yksinkertaiseen monikulmioon . $Päällä)$
Algoritmi Bentley - Ottmann - etsi kaikki segmenttien leikkauspisteet tasossa , - leikkauspisteiden lukumäärä. $O((n+k)\log n)$ $k$

Katso myös

Laskennallisen geometrian algoritmit
18 pisteen ongelma
Laskentatopologia

Kirjallisuus

Preparata F., Shaimos M. Laskennallinen geometria Johdanto. - M .: Mir, 1989. - 478 s.
Berg M., Cheong O., Creveld M., Overmars M. Laskennallinen geometria. Algoritmit ja sovellukset = Computational Geometry: Algorithms and Applications. - M. : DMK-Press, 2016. - 438 s. - ISBN 978-5-97060-406-9 .
Fox A., Pratt M. Laskennallinen geometria. Sovellus suunnittelussa ja tuotannossa. - M .: Mir, 1982. - 304 s.
Laszlo M. Laskennallinen geometria ja tietokonegrafiikka C++:ssa. - M .: BINOM, 1997. - 304 s.
Skvortsov A.V. Delaunay-triangulaatio ja sen soveltaminen. - Tomsk: Tomsk University Publishing House, 2002. - 128 s.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Luku 33 Laskennallinen geometria // Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. – 2. painos. - M . : "Williams", 2005. - S. 1047 - 1084. - ISBN 5-8459-0857-4 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Laskennallinen geometria: Algoritmit ja sovellukset. - Springer, 2000. - 368 s.
David M Mount. Laskennallinen geometria. - Marylandin yliopisto, 2002. - 122 s.
Elmar Langetepe, Gabriel Zachmann. Geometriset tietorakenteet tietokonegrafiikkaa varten. - A. K. Peters, 2006. - 362 s. — ISBN 1568812353 .
Hormoz Pirzadeh. Laskennallinen geometria pyörivillä paksuilla. - McGill University, 1999. - 118 s.
Jacob E. Goodman, Joseph O'Rourke. Diskreetin ja laskennallisen geometrian käsikirja. - CRC Press LLC, 1997. - 956 s.
Jianer Chen. Laskennallinen geometria: menetelmät ja sovellukset. — Texas A&M University, 1996. — 228 s.
Joseph O'Rourke. Computational Geometry in C. - Cambridge University Press, 1998. - 362 s.
AR Forrest. Laskennallinen geometria. - sarja 4. - Proc. Royal Society London, 1971. - 321 s.