ALGORITMOS GEOMETRICOS

Grupo CUYS (Como usted ya sabe) | WWW.CUYS.COM.AR
Fac. Cs. Exactas (UNICEN) Hoja 1

Análisis y Diseño de Algoritmos II – Algoritmos Geométricos
➢

Algoritmos Geométricos:
Ademas de resolverproblemas geométricos, en la actualidad tiene otras
aplicación es como gráfica, robótica y diseño.

➢

Entidades Geométricas:
Punto: entidad mas básica formado por una coordenada X y una Y.Segmento o linea: Formado por 2 puntos A y B.
Polígono: Formado por n segmentos. Ejemplo: un cuadrado.
Poliedro: formado por n polígonos los cuales le dan profundidad a la figura.
Ejemplo: un cubo.

••
•
•

➢

Polígono Convexo:
Es el que tiene todos sus ángulos internos menores a 180º.

➢

Polígono No Convexo:
Es el que tiene algún angulo interno mayo a 180º.

➢

Problemasclásicos de Geometría:
➢ Verificar si un punto se encuentra a izquierda o derecha de un
segmento.
➢ Verificar corte de segmentos y punto de corte.
➢ Verificar si un punto se encuentra dentro de unpolígono.
➢ Calcular el área encerrada por un polígono.
➢ Encontrar el convex hull. (menor polígono convexo que encierra un
conjunto de puntos).
➢ Encontrar el par de puntos cuya distancia es la menor deun conjunto.

Grupo CUYS (Como usted ya sabe) | WWW.CUYS.COM.AR
Fac. Cs. Exactas (UNICEN) Hoja 2
➢

Verificar si un punto se encuentra a izquierda o derecha de un
segmento:
Conociendo laspropiedades del producto vectorial es muy simple sabes si
un punto esta a derecha o a izquierda de un segmento. Debemos seguir los
siguientes pasos:
1. Trasladamos todo al origen, generando 2vectores, uno del primer punto
del segmento a segundo, y otro del primer punto del segmento al punto que
quiero saber si se encuentra a izquierda o a derecha.

Para hacer el traslado y generar losvectores:
V1 = P – S.p1
V2 = S.p2 – S.p1

2. Aplicar producto vectorial, entre los vectores generados. Y sacar las
conclusiones desde ahí, como muestra la figura.
En nuestro caso V1 x V2, como el...