Ing. Sistemas

ALGORITMOS GEOMÉTRICOS

Análisis y diseño de algoritmos II- 2009

Algoritmos geométricos
La geometría computacional es una rama de la ciencia de la computación que estudia algoritmos para resolver problemas geométricos. Aplicaciones Computación gráfica, CAD (Computer-Aided Design), robótica, diseño de circuitos integrados, GIS (Geographic information System),…

Algoritmos geométricosLos algoritmos geométricos operan sobre objetos geométricos tales como puntos, segmentos o polígonos. Analizaremos algoritmos en dos dimensiones en los que cada objeto geométrico es representado como un conjunto de puntos {pi} donde pi=(xi,yi) con xi, yi ∈ R Por ejemplo, un polígono de n vértices es representado por una secuencia de sus vértices.

Algoritmos geométricos
Interesantes problemasde geometría computacional se presentan actualmente en espacios 3D o de orden superior. En este curso ejemplificaremos técnicas de geometría computacional en 2D que son la base para manipular entidades geométricas de mayores dimensiones.

Algoritmos geométricos
Propiedades de segmentos Una combinación convexa de dos puntos distintos p1=(x1,y1) y p2=(x2,y2) es algún punto p3=(x3,y3) tal que paraalgún α en el rango 0≤α≤ 1 resultan x3= α x1 + (1-α) x2 y3= α y1 + (1-α) y2 Intuitivamente, p3 =α p1 + (1-α) p2 denota a un punto que pertenece a la recta que pasa por p1 y p2 y está sobre o entre p1 y p2.

Algoritmos geométricos
Segmento Dados dos puntos p1 y p2, el segmento p1p2 es el conjunto de combinaciones convexas de p1 y p 2. Vector Un segmento orientado entre p1 y p2 se denota p1p2.Si p1 es el origen (0,0) p1p2 es el vector p2

Algoritmos geométricos
Problemas simples Dados dos segmentos p0p1 y p0p2, ¿ p0p1 está en sentido horario desde p0p2 con respecto al extremo p0? Dados p1p2 y p2p3, si recorremos p1p2 y luego p2p3, giramos a la izquierda en p2? Dados dos segmentos p1p2 y p3p4, se intersecan?

Algoritmos geométricos
Los algoritmos geométricos se basan en cálculossimples que usan sumas, restas, multiplicaciones y comparaciones.

No calculan divisiones ni funciones trigonométricas por razones de costo y error de redondeo.

Algoritmos geométricos
Producto cruzado Los problemas vinculados con segmentos se basan en el cálculo de productos cruzados. Dados dos vectores p1 y p2, el producto cruzado p1xp2 puede interpretarse como el área del paralelogramoformado por (0,0), p1, p2 y p1+p2.

Algoritmos geométricos

Producto cruzado

Algoritmos geométricos
Otra definición de producto cruzado

Si p1 x p2 >0, p1 está en sentido horario desde p2 con respecto al origen (0,0)

Si p1x p2 < 0, p1 está en sentido antihorario desde p2 con respecto al origen (0,0)

Algoritmos geométricos
Antihorario desde p Producto cruzado 0

Algoritmosgeométricos
Dados p0p1 y p1p2, si recorremos p0p1 y luego p1p2, giramos a la izquierda o a la derecha en p2?

antihorario

horario

(p2-p0) x (p1-p0) < 0

(p2-p0) x (p1-p0) > 0

(p2-p0) x (p1-p0) = 0 Colineales

Algoritmos geométricos
Ejemplos de problemas que podemos resolver simplemente aplicando producto cruzado Dado un punto p el segmento p1p2 está a la derecha o a la izquierda dep. Dado un polígono convexo, determinar si un punto es interior

Algoritmos geométricos
Determinar la intersección entre dos segmentos
Hay intersección entre dos segmentos p1p2 y p3p4 si y sólo sí se cumplen una (o ambas) de las siguientes condiciones: p1 queda a uno de los lados de la línea que contiene a p3p4 y p2 en el otro (p1p2 “ a horcajadas de “ p3p4); p3 queda a uno de los lado de lalínea que contiene a p1p2 y p4 en el otro. El extremo de un segmento cae sobre el otro segmento.

Algoritmos geométricos Intersección de segmentos
p1p2 “a horcajadas de “ p3p4

p3p4 “a horcajadas de “ p1p2

Algortimos geométricos Intersección de segmentos
p1p2 no está a horcajadas de p3p4 p3p4 “a horcajadas “ p1p2

0

Algoritmos geométricos Intersección de segmentos

p3 colineal...