Geometría Computacional

La geometría computacional es una rama de la informática que se ocupa de los algoritmos para resolver problemas geométricos.

Se ocupa de tareas como la triangulación, la construcción de un casco convexo, la determinación de si un objeto pertenece a otro, la búsqueda de su intersección, etc. Operan con objetos geométricos tales como: punto , segmento de línea , polígono , círculo ...

La geometría computacional se utiliza en el reconocimiento de patrones , gráficos por computadora , diseño de ingeniería , etc.

Álgebra vectorial

A menudo se utilizan para manipulaciones numéricas las coordenadas de un punto y un vector.

Aquí consideramos el caso del sistema de coordenadas cartesiano usual .

La longitud de un vector se denota por . ${\overrightarrow {a}}=(x,y,z)$ ${\displaystyle |{\overrightarrow {a}}|={\sqrt {x^{2}+y^{2}+z^{2))))$

Para dos vectores y su suma se define como . ${\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})$

La multiplicación de un vector por un escalar k se define como . En este caso, la longitud del vector cambia en tiempos. Si k < 0, entonces la dirección del vector se invierte. ${\overrightarrow {a}}=(x,y,z)$ ${\overrightarrow {b}}=k{\overrightarrow {a}}=(kx,ky,kz)$ ${\ estilo de visualización | k |}$

El producto escalar de vectores y es igual a . ${\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))$

El producto vectorial de vectores y es igual a . Esta es la única operación donde la reducción de la dimensión espacial no se reduce a un simple rechazo de la tercera coordenada (reemplazándola por cero). Por lo general, para vectores bidimensionales, la tercera coordenada de los vectores tridimensionales correspondientes se toma como el valor del producto vectorial: . ${\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}\derecho\}$ ${\displaystyle x_{1}y_{2}-x_{2}y_{1))$

Tipos de polígonos (polígonos)

Un polígono es una curva cerrada en un plano, que consta de segmentos de líneas rectas. Los segmentos se llaman lados del polígono y sus extremos se llaman vértices del polígono.

Un polígono se llama simple si no se corta a sí mismo.

Un polígono se dice convexo si todos sus ángulos interiores son menores o iguales a 180 grados.

Una cadena de vértices se llama monótona si cualquier línea vertical la corta como máximo una vez. Un polígono compuesto por dos cadenas de este tipo se llama monótono.

Algoritmos

El algoritmo de exploración de Graham requiere mucha mano de obra . $O(n\log n)$
Algoritmo de caparazón rápido - entrada de mano de obra , - en promedio. $O(n^{2})$ $O(n\log n)$
El algoritmo de Kirkpatrick es la construcción de un casco convexo de un conjunto de puntos en un plano utilizando el método de " divide y vencerás " a través de puentes. Intensidad laboral . $O(n\log n)$
Algoritmo para envolver regalos (Jarvis) - trabajo de entrada , - el número de puntos en el casco convexo. $O(nh)$ $h$
Algoritmo de Chen - laboriosidad , - el número de puntos en el casco convexo. $O(n\log h)$ $h$
Algoritmo de un punto en un polígono - comprobar si un punto dado pertenece a un polígono simple . $En)$
Método del rayo - Pertenencia de un punto a un polígono simple . $En)$
Algoritmo Bentley - Ottmann - búsqueda de todos los puntos de intersección de segmentos en el plano , - el número de puntos de intersección. $O((n+k)\log n)$ $k$

Véase también

Algoritmos de geometría computacional
problema de 18 puntos
Topología informática

Literatura

Preparata F., Shaimos M. Geometría computacional Una introducción. — M .: Mir, 1989. — 478 p.
Berg M., Cheong O., Creveld M., Overmars M. Geometría computacional. Algoritmos y Aplicaciones = Geometría Computacional: Algoritmos y Aplicaciones. - M. : DMK-Press, 2016. - 438 p. - ISBN 978-5-97060-406-9 .
Fox A., Pratt M. Geometría computacional. Aplicación en diseño y producción. — M .: Mir, 1982. — 304 p.
Laszlo M. Geometría computacional y gráficos por computadora en C++. - M. : BINOM, 1997. - 304 p.
Skvortsov A. V. Triangulación de Delaunay y su aplicación. - Tomsk: Editorial de la Universidad de Tomsk, 2002. - 128 p.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capítulo 33 Geometría Computacional // Algoritmos: Construcción y Análisis = Introducción a los Algoritmos. — 2ª edición. - M. : "Williams", 2005. - S. 1047 - 1084. - ISBN 5-8459-0857-4 .
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Geometría Computacional: Algoritmos y Aplicaciones. - Springer, 2000. - 368 págs.
David M Monte. Geometría Computacional. - Universidad de Maryland, 2002. - 122 p.
Elmar Langetepe, Gabriel Zachmann. Estructuras geométricas de datos para gráficos por computadora. - A. K. Peters, 2006. - 362 p. — ISBN 1568812353 .
Hormoz Pirzadeh. Geometría Computacional con Calibradores Rotativos. - Universidad McGill, 1999. - 118 p.
Jacob E. Goodman, Joseph O'Rourke. Manual de geometría discreta y computacional. - CRC Press LLC, 1997. - 956 p.
Jianer Chen. Geometría Computacional: Métodos y Aplicaciones. — Universidad de Texas A&M, 1996. — 228 p.
Joseph O'Rourke. Geometría Computacional en C. - Cambridge University Press, 1998. - 362 p.
ARForrest. Geometría Computacional. - serie 4. - Proc. Royal Society Londres, 1971. - 321 p.