Page 1 of 1

Geometria computacional

Posted: Mon Nov 16, 2015 3:48 pm
by isaac
Para los que les gusta la geometria computacional, tengo en mis manos un archivo .h que creo que les puede servir para muchas cosas de la geometria. Quizas no les sirva para los ejercicios del COJ pero si para el entrenamiento individual y la especializacion en esta area de la programacion. La biblioteca consiste en una clase que sirve para trabajar con vectores en 3D. En su interior posee todos los metodos necesarios y suficientes para realizar las operaciones basicas con vectores en 3 dimensiones, como la suma, la resta, la multiplicacion por un escalar, el producto cruz, producto punto, rotacion, cambio de tamaño etc... además esta montado sobre una plantilla, asi que si quieres un vector 3d que tenga siempre componentes enteras, declaras vec3d<int> y listo. Si a alguno le interesa, puede escribir a isaacv@fecrd.cujae.edu.cu. Es bastante util conocer las propiedades de los vectores porque son cruciales en la geometria. Saludos a todos.

Re: Geometria computacional

Posted: Mon Nov 30, 2015 12:03 am
by isaac
Ahi les va unas cositas acerca de la geometria computacional:

1-> Un calculo bastante bueno es la aplicacion del producto cruzado a dos vectores 2d. Si se tienen los puntos A, B y C, el producto cruzado de los vectores AB y AC da < 0 si ABC hace una rotacion hacia la derecha, > 0 si rotan hacia la izquierda y cero si son colineales. Ademas, el valor absoluto de este producto dividido por 2 da como resultado el area del triangulo ABC. El calculo es el siguiente:

cross(PT a, PT b, PT c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

Lo que se hace es resolver el determinante formado por las coordenadas x e y de los vectores ab y ac respectivamente el cual es:

| (b.x - a.x) (b.y - a.y) |
| (c.x - a.x) (c.y - a.y) |

2-> Para saber el area del triangulo formado por tres puntos, podemos tambien usar la siguiente formula:

|x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2) |
-------------------------------------------------------
2

3-> Si se tienen los tres lados de un triangulo se puede calcular el area por las siguientes formas:
1-> sqrt(p * (p - a) * (p - b) * (p - c)) donde p es el semiperimetro = (a + b + c) / 2.
2-> sqrt((a + b - c) * (a - b + c) * (-a + b + c) * (a + b + c)) / 4.
3-> (a + b + c) * r / 2 donde r es el radio de la circunferencia inscrita al triangulo.
4-> a * b * c / 4R donde R es el radio de la circunferencia circunscrita al triangulo.

4-> Si se quiere saber cual es el punto donde se encuentra el centro de una circunferencia tal que pase por los puntos a, b y c, todo lo que hay que hacer es ver donde se cortan las rectas que pasan por D y E y son perpendiculares a los segmentos ab y ac respectivamente donde D es el punto medio de ab y E el de ac.

5-> Si se tiene un vector con origen en (0; 0) y extremo en (x; y) y se quiere rotar T grados hacia la izquierda, las nuevas componentes X e Y se calcularian del siguiente modo:

X = x * coseno(T) - y * seno(T)
Y = x * seno(T) + y * coseno(T)

Cabe señalar que la suma de dos vectores es un vector que cumple con la condicion de ser el cuarto punto de un paralelogramo formado por este, el origen (0; 0) y los extremos de los dos vectores sumados.

Ejemplo:
V1 = (3, 2)
V2 = (1; 5)
V1 + V2 = (3 + 1; 2 + 5) = (4; 7). Pueden comprobarlo manualmente.

Espero que le sirva a alguien, Si no se entendio algo please...escribanlo y tratare de aclarar las dudas.

Re: Geometria computacional

Posted: Sat Dec 19, 2015 1:31 pm
by HaZard
¿cómo se calcula el centro de masas de un polígono no convexo?

Re: Geometria computacional

Posted: Sun Dec 20, 2015 6:19 pm
by isaac
El metodo general para encontrar el centro de masa de un poligono es:

X = sumatoria de( Y[i+1] - Y) * (X[i+1]*X[i+1] + X*X[i+1] + X*X ) / 6 * AREA_DEL_POLIGONO;
Y = sumatoria de ( X - X[i+1]) * (Y[i+1]*Y[i+1] + Y*Y[i+1] + Y*Y ) / 6 * AREA_DEL_POLIGONO;

El area de un poligono es:

sumatoria de ( X * Y[i + 1] ) - sumatoria de (X[i+1] * Y)

Re: Geometria computacional

Posted: Mon Dec 21, 2015 6:00 pm
by HaZard
ta bueno, voy a probarlo