Geometria computacional

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Geometria computacional

Post by isaac » 3 years ago

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.



User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: Geometria computacional

Post by isaac » 3 years ago

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.

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: Geometria computacional

Post by HaZard » 2 years ago

¿cómo se calcula el centro de masas de un polígono no convexo?
teruel

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: Geometria computacional

Post by isaac » 2 years ago

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)

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: Geometria computacional

Post by HaZard » 2 years ago

ta bueno, voy a probarlo
teruel

Post Reply

Return to “Algorithms”