elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Estamos en la red social de Mastodon


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?  (Leído 5,366 veces)
ShadowA7X

Desconectado Desconectado

Mensajes: 19



Ver Perfil
Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« en: 26 Octubre 2014, 21:07 pm »
Hola, disculpen las molestias pero me gustaría saber como se hace esto en lenguaje C:

Tengo 4 puntos que representan dos segmentos en el plano cartesiano y cada uno de estos puntos está definido obviamente por dos coordenadas x e y.

EJ:

R1= (x1,y1) (x2,y2)
R2= (x3,y3) (x4,y4)

Bueno, en si tengo que hacer un programa que me pide muchas cosas, pero ésta parte en especifico (ver si dos segmentos se intercectan o no) no se me ha podido ocurrir. Alguien me puede orientar porfavor?

Mi problema fundamental es como se definen los puntos...

EJ: R1=A ,B (siendo A un punto y B otro)

Y lo que yo debo usar es:

R1=(x1,y1) (x2,y2) [siendo dos variables cartesianas (x e y) un punto, y otros dos el otro punto.

Entonces, como puedo decir que un punto es mayor o menor a otro si ocupo coordenadas cartesianas para definir a cada punto?

Se me ocurrió que x1>x2 && y1>y2, si se cumple entonces el punto (x1,y1) es mayor, y de forma analoga si x1<x2 && y1<y2 entonces el punto (x2,y2 es mayor). Pero que ocurre si por ejemplo x1<x2 && y1>y2? entonces el punto es mayor, menor o que?

Necesito dilucidar eso...


Muchas gracias de antemano por las molestias.
« Última modificación: 26 Octubre 2014, 21:50 pm por ShadowA7X » En línea
engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.514



Ver Perfil
Re: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« Respuesta #1 en: 26 Octubre 2014, 21:11 pm »
aplica las ecuaciones de recta para los puntos y la intercepciones de rectas
En línea
El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
ShadowA7X

Desconectado Desconectado

Mensajes: 19



Ver Perfil
Re: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« Respuesta #2 en: 26 Octubre 2014, 21:26 pm »
Cita de: engel lex en 26 Octubre 2014, 21:11 pm
aplica las ecuaciones de recta para los puntos y la intercepciones de rectas

Si se eso amigo, pero me joden ciertas cosas. Por ejemplo, tengo un prototipo en paython que ya me dio la idea, el cual es éste:

Código
  1. def area_triang(a,b,c):
  2.       return (b[0]-a[0])*(c[1]-a[1])-(c[0]-a[0])*(b[1]-a[1])
  3.  
  4. def side_p_to_seg(v1,v2,p):
  5.     area = area_triang(v1,v2,p)
  6.     if area > 0 :
  7.         lado = "izq"
  8.     elif area < 0 :
  9.         lado = "der"
  10.     else:
  11.         lado = "col"
  12.     return lado
  13.  
  14.  
  15. def seg_intersection(u1,u2,v1,v2):
  16.  if (side_p_to_seg(u1,u2,v1) == "col" or
  17.      side_p_to_seg(u1,u2,v2) == "col" or
  18.      side_p_to_seg(v1,v2,u1) == "col" or
  19.      side_p_to_seg(v1,v2,u2) == "col"):
  20.      return False
  21.  elif (((side_p_to_seg(u1,u2,v1) == "izq" and
  22.          side_p_to_seg(u1,u2,v2) == "der") or
  23.         (side_p_to_seg(u1,u2,v1) == "der" and
  24.          side_p_to_seg(u1,u2,v2) == "izq"))and
  25.        ((side_p_to_seg(v1,v2,u1) == "der" and
  26.          side_p_to_seg(v1,v2,u2) == "izq") or
  27.         (side_p_to_seg(v1,v2,u1) == "izq" and
  28.          side_p_to_seg(v1,v2,u2) == "der"))):
  29.   return True
  30.  else:
  31.   return False


Entiendo todo, pero mi problema es que en el programa (y en muchas otras partes que he buscado) definen cada punto del segmento con una sola variable:

EJ: R1=A ,B (siendo A un punto y B otro)

Y lo que yo debo usar es:

R1=(x1,y1) (x2,y2) [siendo dos variables cartesianas (x e y) un punto, y otros dos el otro punto.

Entonces, como puedo decir que un punto es mayor o menor a otro si ocupo coordenadas cartesianas para definir a cada punto?

Se me ocurrió que x1>x2 && y1>y2, si se cumple entonces el punto (x1,y1) es mayor, y de forma analoga si x1<x2 && y1<y2 entonces el punto (x2,y2 es mayor). Pero que ocurre si por ejemplo x1<x2 && y1>y2? entonces el punto es mayor, menor o que?

Necesito dilucidar eso...
En línea
leosansan


Desconectado Desconectado

Mensajes: 1.314


Ver Perfil
Re: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« Respuesta #3 en: 26 Octubre 2014, 22:12 pm »
Cita de: ShadowA7X en 26 Octubre 2014, 21:07 pm
Tengo 4 puntos que representan dos segmentos en el plano cartesiano y cada uno de estos puntos está definido obviamente por dos coordenadas x e y.

EJ:

R1= (x1,y1) (x2,y2)
R2= (x3,y3) (x4,y4)

Bueno, en si tengo que hacer un programa que me pide muchas cosas, pero ésta parte en especifico (ver si dos segmentos se interceptan o no) no se me ha podido ocurrir. Alguien me puede orientar por favor?
......................................

Si (y2 - y1 ) / ( x2 - x1 ) !=  (y4 - y3 )  / ( x4 - x3 ) ==> Se cortan.

Si (y2 - y1 ) / ( x2 - x1 ) =  (y4 - y3 )  / ( x4 - x3 ) ==> Son paralelas o coincidentes.

¡¡¡¡ Saluditos! ..... !!!!
« Última modificación: 26 Octubre 2014, 22:14 pm por leosansan » En línea
ShadowA7X

Desconectado Desconectado

Mensajes: 19



Ver Perfil
Re: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« Respuesta #4 en: 26 Octubre 2014, 23:01 pm »
Cita de: leosansan en 26 Octubre 2014, 22:12 pm
Si (y2 - y1 ) / ( x2 - x1 ) !=  (y4 - y3 )  / ( x4 - x3 ) ==> Se cortan.

Si (y2 - y1 ) / ( x2 - x1 ) =  (y4 - y3 )  / ( x4 - x3 ) ==> Son paralelas o coincidentes.

¡¡¡¡ Saluditos! ..... !!!!




Primero que todo, muchas gracias por darte el tiempo de contestar amigo, se agradece :). La formula que me dio hermano es para rectas, y como yo estoy trabajando con segmentos (es decir que tienen limite/extremos) no me sirve...

Igual muchas gracias :)
« Última modificación: 26 Octubre 2014, 23:14 pm por Eternal Idol » En línea
engel lex
Moderador Global
***
Desconectado Desconectado

Mensajes: 15.514



Ver Perfil
Re: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« Respuesta #5 en: 26 Octubre 2014, 23:22 pm »
lo que no entiendo es por qué no puedes adaptar el codigo... si es por las variables solo haces array y listo, busca sobre array en c++ y el pase como parametro
En línea
El problema con la sociedad actualmente radica en que todos creen que tienen el derecho de tener una opinión, y que esa opinión sea validada por todos, cuando lo correcto es que todos tengan derecho a una opinión, siempre y cuando esa opinión pueda ser ignorada, cuestionada, e incluso ser sujeta a burla, particularmente cuando no tiene sentido alguno.
ShadowA7X

Desconectado Desconectado

Mensajes: 19



Ver Perfil
Re: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« Respuesta #6 en: 27 Octubre 2014, 03:52 am »
Cita de: engel lex en 26 Octubre 2014, 23:22 pm
lo que no entiendo es por qué no puedes adaptar el codigo... si es por las variables solo haces array y listo, busca sobre array en c++ y el pase como parametro

Perdón por no expresarme tan bien amigo, error mio :-\.Ya se ocupar los arrays, eso no es problema.

Ya Hice todo lo que debía, adapté el programa anterior en C pero el programa no me funciona como quiero...

Aquí están las funciones adaptadas en C, espero me puedan decir si ven algo mal...

Código
  1. typedef struct nino{
  2. int X;
  3. int Y;
  4. }nino;
  5.  
  6. typedef struct muro{
  7. int X1;
  8. int X2;
  9. int Y1;
  10. int Y2;
  11. }muro;
  12.  
  13. void Analizar(nino vec_nino[] , muro vec_muro[], int cant_ninos, int cant_muros, int nino_bus,int cant_vistos[]);
  14. int Interseccion(nino vec_nino[],muro vec_muro[],int i,int j,int cant_muros);
  15. float formula_heron(float dis1, float dis2, float dis3);
  16. int lado_punto(float Area_trian);

Código
  1. int main(){
  2.  
  3. 	int nino_bus,cant_ninos,cant_muros,i;
  4.  
  5. 	nino vec_nino[10000];
  6. 	muro vec_muro[10000];
  7. 	int cant_vistos[10000];
  8.  
  9. 	scanf("%d",&nino_bus);
  10. 	scanf("%d",&cant_ninos);
  11. 	scanf("%d",&cant_muros);
  12.  
  13. 	for (i = 0; i < cant_ninos; i++){
  14.  
  15. 		scanf("%d %d",&vec_nino[i].X,&vec_nino[i].Y);
  16. 	}
  17.  
  18. 	for (i = 0; i < cant_muros; i++){
  19.  
  20. 		scanf("%d %d %d %d",&vec_muro[i].X1,&vec_muro[i].Y1,&vec_muro[i].X2,&vec_muro[i].Y2);
  21. 	}
  22.  
  23. 	Analizar(vec_nino,vec_muro,cant_ninos,cant_muros,nino_bus,cant_vistos);
  24.  
  25. 	printf("\n");
  26.  
  27. 	for (i = 0; i < nino_bus; i++){
  28. 		printf("%d\n",cant_vistos[i]);
  29. 	}
  30.  
  31. 	return 0;
  32. }

Código
  1. void Analizar(nino vec_nino[] , muro vec_muro[], int cant_ninos, int cant_muros,int nino_bus, int cant_vistos[]){
  2.  
  3. 	int i,j;
  4.  
  5. 	for (i = 0; i < nino_bus; i++){
  6.  
  7. 		for (j = 0; j < cant_ninos; j++){
  8.  
  9. 			if (i!=j){
  10.  
  11. 				cant_vistos[i]=cant_vistos[i]+Interseccion(vec_nino,vec_muro,i,j,cant_muros);
  12.  
  13. 			}
  14. 		}
  15. 	}
  16. }
  17.  

Código
  1. int Interseccion(nino vec_nino[],muro vec_muro[],int i,int j,int cant_muros){
  2.  
  3. 	int k=0;
  4. 	float dis1;
  5. 	float dis2;
  6. 	float dis3;
  7. 	float Area_trian;
  8. 	int lado[4];
  9. 	int cont=0;
  10. 	int salida=0;
  11. 	int basura;
  12.  
  13. 	do{
  14.  
  15.  
  16. 		dis1=sqrt((pow((vec_muro[k].X2-vec_muro[k].X1),2) + pow((vec_muro[k].Y2-vec_muro[k].Y1),2)));
  17. 		dis2=sqrt((pow((vec_muro[k].X2-vec_nino[i].X),2) + pow((vec_muro[k].Y2-vec_nino[i].Y),2)));
  18. 		dis3=sqrt((pow((vec_muro[k].X1-vec_nino[i].X),2) + pow((vec_muro[k].Y1-vec_nino[i].Y),2)));
  19.  
  20. 		Area_trian=formula_heron(dis1,dis2,dis3);
  21. 		lado[cont]=lado_punto(Area_trian);
  22.  
  23. 		cont++;
  24. 		dis1=sqrt((pow((vec_muro[k].X2-vec_muro[k].X1),2) + pow((vec_muro[k].Y2-vec_muro[k].Y1),2)));
  25. 		dis2=sqrt((pow((vec_muro[k].X2-vec_nino[j].X),2) + pow((vec_muro[k].Y2-vec_nino[j].Y),2)));
  26. 		dis3=sqrt((pow((vec_muro[k].X1-vec_nino[j].X),2) + pow((vec_muro[k].Y1-vec_nino[j].Y),2)));
  27.  
  28. 		Area_trian=formula_heron(dis1,dis2,dis3);
  29. 		lado[cont]=lado_punto(Area_trian);
  30.  
  31. 		cont++;
  32. 		dis1=sqrt((pow((vec_nino[i].X-vec_nino[j].X),2) + pow((vec_nino[i].Y-vec_nino[j].Y),2)));
  33. 		dis2=sqrt((pow((vec_muro[k].X1-vec_nino[i].X),2) + pow((vec_muro[k].Y1-vec_nino[i].Y),2)));
  34. 		dis3=sqrt((pow((vec_muro[k].X1-vec_nino[j].X),2) + pow((vec_muro[k].Y1-vec_nino[j].Y),2)));
  35.  
  36. 		Area_trian=formula_heron(dis1,dis2,dis3);
  37. 		lado[cont]=lado_punto(Area_trian);
  38.  
  39. 		cont++;
  40. 		dis1=sqrt((pow((vec_nino[i].X-vec_nino[j].X),2) + pow((vec_nino[i].Y-vec_nino[j].Y),2)));
  41. 		dis2=sqrt((pow((vec_muro[k].X2-vec_nino[i].X),2) + pow((vec_muro[k].Y2-vec_nino[i].Y),2)));
  42. 		dis3=sqrt((pow((vec_muro[k].X2-vec_nino[j].X),2) + pow((vec_muro[k].Y2-vec_nino[j].Y),2)));
  43.  
  44. 		Area_trian=formula_heron(dis1,dis2,dis3);
  45. 		lado[cont]=lado_punto(Area_trian);
  46.  
  47. 		if (lado[0]==2 || lado[1]==2 || lado[2]==2 || lado[3]==2){
  48.  
  49. 			return 1;
  50.  
  51.  
  52. 		}else if (((lado[0]==1 && lado[1]==0) || (lado[0]==0 && lado[1]==1)) && ((lado[2]==0 && lado[3]==1) || (lado[2]==1 && lado[3]==0))){
  53.  
  54. 			salida=1;
  55. 		}else{
  56. 		}
  57.  
  58. 		cont=0;
  59. 		k++;
  60.  
  61. 	}while(k!=cant_muros-1 || salida!=1 );
  62.  
  63. 	if (k==cant_muros-1 && salida!=1){
  64.  
  65. 		return 1;
  66. 	}else{
  67.  
  68. 		return 0;
  69. 	}
  70.  
  71. }

Código
  1. float formula_heron(float dis1, float dis2, float dis3){
  2.  
  3. 	float s,resultado;
  4.  
  5. 	s=(dis1+dis2+dis3)/2;
  6. 	resultado = sqrt(s*(s-dis1)*(s-dis2)*(s-dis3));
  7. 	return resultado;
  8. }

Código
  1. int lado_punto(float Area_trian){
  2.  
  3. 	int lado;
  4.  
  5. 	if (Area_trian >0){
  6.  
  7. 		lado=1;
  8. 	}else if (Area_trian<0){
  9.  
  10. 		lado=0;
  11. 	}else{
  12.  
  13. 		lado=2;
  14. 	}
  15.  
  16. 	return lado;
  17. }


Puse todo para que se entendiera de donde saqué las cosas simplemente. Me parece que la función Intersección tiene un fallo al momento de realizar los operadores lógicos en el If y else(recordar que es una adaptación del código python que postee).

Si pueden ver algo malo en la adaptación de la función intersección porfavor digame, aunque sea una idea puede que sea acertada.
En línea
avesudra


Desconectado Desconectado

Mensajes: 724


Intentando ser mejor cada día :)


Ver Perfil
Re: Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?
« Respuesta #7 en: 28 Octubre 2014, 20:03 pm »
Hola, buenas tardes, antes de nada quería decirle a ShadowA7X que en vez de poner el código completo, deberias poner un ejemplo con las mínimas cosas para que funcione, y así podemos corregirlo bien.

Por añadir algo a este problema, siguiendo con la solución propuesta por Engel Ex, es una solución buena pero como dice ShadowA7X, él está trabajando con segmentos.

Bien para solucionar el problema solo tenemos que ver si las rectas en las que están contenidas esos segmentos se cortan o no. En caso de que no se corten, es obvio que los segmentos tampoco lo hacen, finalizando aquí nuestro problema. Continuando por la otra rama, nos saldría un punto I de corte de las dos rectas.

Ahora viene nuestro problema, ¿cómo demonios comprobamos que ese punto pertenece a los dos segmentos a la vez?

Para comprobar esto, sabemos que el segmento R1 tiene dos puntos que lo definen, A y B, y la longitud de dicho segmento es LAB, si la longitud del segmento IA (punto de corte - punto que define a R1) más la longitud del segmento IB, es la longitud del segmento original, entonces ese punto está en el segmento R1 si ningún tipo de duda.

Pero también tendremos que comprobar esto para el segmento R2 que está definido por los puntos C y D de la misma manera.

Si uno de los dos al menos NO contiene al punto de corte I, entonces los segmentos no se cortan.

Saludos.
« Última modificación: 28 Octubre 2014, 20:05 pm por avesudra » En línea
Regístrate en
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[MOD] Ayuda con programa para saber codec de archivo
Multimedia 		circus2003 1 2,195 Último mensaje 27 Abril 2005, 19:16 pm
por arda-lothi
Ayuda con VBscript para saber Version de programa
Scripting 		zack0zack 0 2,533 Último mensaje 10 Junio 2007, 00:09 am
por zack0zack
ayuda porfavor con este programa
Ejercicios 		krustybart 1 3,179 Último mensaje 7 Febrero 2010, 00:41 am
por Amerikano|Cls
Interceptan a un menor que intercambiaba vídeos pedófilos con compañeros de ...
Noticias 		wolfbcn 3 1,359 Último mensaje 7 Febrero 2018, 01:16 am
por Machacador
Generar un .exe, desde un programa en RAM con IDA?. Composición de segmentos.
Ingeniería Inversa 		ludocop 1 2,052 Último mensaje 18 Febrero 2019, 12:49 pm
por Geovane
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines