Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Geometría Computacional: Transformaciones Algebráicas

No description
by

Monserrat Urzua

on 20 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Geometría Computacional: Transformaciones Algebráicas

Geometría Computacional: Transformaciones Algebráicas
Más definiciones
Los
objetos geométricos
se convierten en
estructuras de datos
y sus metodologías de resolución en
algoritmos
eficientes.

Los
algoritmos geométricos
eficientes son útiles en gráficas por computadora, estadística, procesamiento de imágenes y diseño de la integración a gran escala (VLSI).
Ejercicios
Aplicaciones
Imaginen que caminan en el Campus Universitario deseando realizar una llamada urgente; existen varios teléfonos públicos y claro, deseamos ir al más cercano.

¿Cuál será?
¿Cómo calculamos esto?
"El par más cercano"
Dados n puntos en el plano, se debe encontrar el par más cercano.

1.- El algoritmo comienza por encontrar una línea vertical
l
que divide los puntos en 2 partes iguales.
2.- Sea δL la distancia entre un par más cercano en la parte izquierda y δR en la parte derecha.
3.- δ = min{δL, δR}
4.- δ quizás no sea la distancia entre un par más cercano en el conjunto original...
5.- Observaremos la distancia entre par de puntos, que deben estar en una franja vertical con 2δ de ancho centrada en
l
restringiendo la búsqueda a esa área.
Algoritmos
Divide y vencerás
Línea plano/ barrido
Búsqueda binaria
Dualidad
Basados en aleatoriedad
Paralelismo
Estructuras de datos
Teselado de plano / espacio
Diagramas de Voronoi
Triangulaciones
Basadas en árboles
Segment - Trees
K-D Trees
Quadtrees / Octrees
Árboles de intervalos
BSP
6.- Ordenamos los puntos de la franja vertical con ancho 2δ centrada en
l
en orden no decreciente respecto a sus coordenadas y examinamos los puntos en ese orden.
7.- Se calculan las distancias entre cada punto y los que le siguen.
8.- Las distancias se comparan con δ.

¿Preguntas?
Algunas definiciones
: )

Gracias.
Geometría Computacional
se refiere al diseño y análisis de los algoritmos para resolver problemas geométricos.

Las
transformaciones algebraicas
se refieren a todo tipo de operaciones que involucran expresiones algebraicas.

Ejemplo:
2x + 4y + x - 3y = 3x + y

"El casco convexo"
Estadística
Puntos extremos no representativos de los datos.
Gráficas
Procesamiento de imágenes

Aplicaciones
"Dado un finito de
S
puntos en el plano, un punto
p
en
S
es un
punto del casco
si existe una línea recta
L
que pasa por
p
tal que todos los puntos en
S
excepto
p
están de un lado de
L
(y a excepción de
p,
ninguno está sobre
L
)".

Definición
El punto p1 es el punto con la coordenada
Y
mínima , en caso de que varios puntos tengan la misma coordenada
Y
mínima, p1 es el que tiene la coordenada
X
mínima.

Definiendo el problema
Algoritmo de Graham
Algoritmo de Graham
Se utiliza para determinar el casco convexo, primero se encuentra el punto p1 con la coordenada
Y
mínima, después se ordenan todos los puntos
p
en
S
según el ángulo de la horizontal hasta el segmento de la recta p1,p.

Algoritmo de Graham
1.-
2.-
3.-
4.-
5.-
6.-
7.-
8.-
9.-
10.-
Cálculo de intersecciones
El cálculo de intersecciones es necesaria en los sistemas de información geográfica, ya que se genera un problema entre las redes de carretera, ríos, vías férreas, etc.

En robótica se utiliza para detectar y evitar colisiones.

En gráficas computacionales existe el método ray shooting utilizado para renderizar, siendo necesario determinar la intersección de rayos con objetos.
Aplicaciones
"Dado un conjunto
S
de
n
segmentos cerrados en el plano, reportar todos los puntos de intersección entre los segmentos en
S
".

Definición
Es necesario un algoritmo cuyo tiempo de ejecución dependa no solo del número de segmentos de la entrada, sino también sobre el número de puntos de intersección, un algoritmo "Sensible a la Salida".

¿Tenemos que probar con todos los segmentos?

Definiendo el problema
Algoritmos
Los puntos de evento son almacenados en un "Árbol de búsqueda binaria"
Se define el intervalo
Y
de cada uno de los segmentos del conjunto
S
que es la proyección ortogonal sobre el eje
Y
.

"Algoritmo de Barrido Plano"
El estado de la línea de Barrido es el conjunto de segmentos que se intersección.

Es estado cambia cuando un "Punto de evento" aparece, se actualiza y se hacen pruebas de intersección.

Si el punto de evento es el extremo superior de un segmento...

Se prueba contra los otros segmentos que ya estan en la línea de barrido.
"Algoritmo de Barrido Plano"
Si el punto de evento es el punto final más bajo...

Serán probados aquellos que tengan adyacencia horizontal.

No solo se actualiza el estado en los extremos de los segmentos, ahora también debe actualizarse de acuerdo al a secuencia ordenada de segmentos

Full transcript