Geometria

PEQUEÑO ENSAYO GEOMETRICO


Análisis y Diseño de Algoritmos II – Algoritmos Geométricos
➢ Algoritmos Geométricos:
Ademas de resolver problemas geométricos, en la actualidad tiene otrasaplicació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: Formadopor 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 ángulosinternos menores a 180º.
➢ Polígono No Convexo:
Es el que tiene algún angulo interno mayo a 180º.
➢ Problemas clásicos de Geometría:
➢ Verificar si un punto se encuentra a izquierda o derecha de unsegmento.
➢ Verificar corte de segmentos y punto de corte.
➢ Verificar si un punto se encuentra dentro de un polí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 de un 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 las propiedades del producto vectorial es muy simple sabes si
un punto esta a derecha o aizquierda de un segmento. Debemos seguir los
siguientes pasos:
1. Trasladamos todo al origen, generando 2 vectores, uno del primer punto
del segmento a segundo, y otro del primer punto del segmento alpunto que
quiero saber si se encuentra a izquierda o a derecha.
Para hacer el traslado y generar los vectores:
V1 = P – S.p1
V2 = S.p2 – S.p1
2. Aplicar producto vectorial, entre los vectoresgenerados. Y sacar las
conclusiones desde ahí, como muestra la figura.
En nuestro caso V1 x V2, como el punto esta a la derecha nos da positivo,
siguiendo la regla del tirabuzón. Si nos diese...