Ayuda porfavor,Programa en C para saber si dos segmentos se interceptan?

[ShadowA7X]

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.

[engel lex]

aplica las ecuaciones de recta para los puntos y la intercepciones de rectas

[ShadowA7X]

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 (python) [Seleccionar] Expandir

def area_triang(a,b,c):
      return (b[0]-a[0])*(c[1]-a[1])-(c[0]-a[0])*(b[1]-a[1])

def side_p_to_seg(v1,v2,p):
    area = area_triang(v1,v2,p)
    if area > 0 :
        lado = "izq"
    elif area < 0 :
        lado = "der"
    else:
        lado = "col"
    return lado


def seg_intersection(u1,u2,v1,v2):
if (side_p_to_seg(u1,u2,v1) == "col" or
     side_p_to_seg(u1,u2,v2) == "col" or
     side_p_to_seg(v1,v2,u1) == "col" or
     side_p_to_seg(v1,v2,u2) == "col"):
     return False
elif (((side_p_to_seg(u1,u2,v1) == "izq" and
         side_p_to_seg(u1,u2,v2) == "der") or
        (side_p_to_seg(u1,u2,v1) == "der" and
         side_p_to_seg(u1,u2,v2) == "izq"))and
       ((side_p_to_seg(v1,v2,u1) == "der" and
         side_p_to_seg(v1,v2,u2) == "izq") or
        (side_p_to_seg(v1,v2,u1) == "izq" and
         side_p_to_seg(v1,v2,u2) == "der"))):
  return True
else:
  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...

[leosansan]

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! ..... !!!!

[ShadowA7X]

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

[engel lex]

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

[ShadowA7X]

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 (c) [Seleccionar] Expandir

typedef struct nino{
int X;
int Y;
}nino;

typedef struct muro{
int X1;
int X2;
int Y1;
int Y2;
}muro;

void Analizar(nino vec_nino[] , muro vec_muro[], int cant_ninos, int cant_muros, int nino_bus,int cant_vistos[]);
int Interseccion(nino vec_nino[],muro vec_muro[],int i,int j,int cant_muros);
float formula_heron(float dis1, float dis2, float dis3);
int lado_punto(float Area_trian);

Código (c) [Seleccionar] Expandir

int main(){

int nino_bus,cant_ninos,cant_muros,i;

nino vec_nino[10000];
muro vec_muro[10000];
int cant_vistos[10000];

scanf("%d",&nino_bus);
scanf("%d",&cant_ninos);
scanf("%d",&cant_muros);

for (i = 0; i < cant_ninos; i++){

scanf("%d %d",&vec_nino[i].X,&vec_nino[i].Y);
}

for (i = 0; i < cant_muros; i++){

scanf("%d %d %d %d",&vec_muro[i].X1,&vec_muro[i].Y1,&vec_muro[i].X2,&vec_muro[i].Y2);
}

Analizar(vec_nino,vec_muro,cant_ninos,cant_muros,nino_bus,cant_vistos);

printf("\n");

for (i = 0; i < nino_bus; i++){
printf("%d\n",cant_vistos[i]);
}

return 0;
}

Código (c) [Seleccionar] Expandir

void Analizar(nino vec_nino[] , muro vec_muro[], int cant_ninos, int cant_muros,int nino_bus, int cant_vistos[]){

int i,j;

for (i = 0; i < nino_bus; i++){

for (j = 0; j < cant_ninos; j++){

if (i!=j){

cant_vistos[i]=cant_vistos[i]+Interseccion(vec_nino,vec_muro,i,j,cant_muros);

}
}
}
}


Código (c) [Seleccionar] Expandir

int Interseccion(nino vec_nino[],muro vec_muro[],int i,int j,int cant_muros){

int k=0;
float dis1;
float dis2;
float dis3;
float Area_trian;
int lado[4];
int cont=0;
int salida=0;
int basura;

do{


dis1=sqrt((pow((vec_muro[k].X2-vec_muro[k].X1),2) + pow((vec_muro[k].Y2-vec_muro[k].Y1),2)));
dis2=sqrt((pow((vec_muro[k].X2-vec_nino[i].X),2) + pow((vec_muro[k].Y2-vec_nino[i].Y),2)));
dis3=sqrt((pow((vec_muro[k].X1-vec_nino[i].X),2) + pow((vec_muro[k].Y1-vec_nino[i].Y),2)));

Area_trian=formula_heron(dis1,dis2,dis3);
lado[cont]=lado_punto(Area_trian);

cont++;
dis1=sqrt((pow((vec_muro[k].X2-vec_muro[k].X1),2) + pow((vec_muro[k].Y2-vec_muro[k].Y1),2)));
dis2=sqrt((pow((vec_muro[k].X2-vec_nino[j].X),2) + pow((vec_muro[k].Y2-vec_nino[j].Y),2)));
dis3=sqrt((pow((vec_muro[k].X1-vec_nino[j].X),2) + pow((vec_muro[k].Y1-vec_nino[j].Y),2)));

Area_trian=formula_heron(dis1,dis2,dis3);
lado[cont]=lado_punto(Area_trian);

cont++;
dis1=sqrt((pow((vec_nino[i].X-vec_nino[j].X),2) + pow((vec_nino[i].Y-vec_nino[j].Y),2)));
dis2=sqrt((pow((vec_muro[k].X1-vec_nino[i].X),2) + pow((vec_muro[k].Y1-vec_nino[i].Y),2)));
dis3=sqrt((pow((vec_muro[k].X1-vec_nino[j].X),2) + pow((vec_muro[k].Y1-vec_nino[j].Y),2)));

Area_trian=formula_heron(dis1,dis2,dis3);
lado[cont]=lado_punto(Area_trian);

cont++;
dis1=sqrt((pow((vec_nino[i].X-vec_nino[j].X),2) + pow((vec_nino[i].Y-vec_nino[j].Y),2)));
dis2=sqrt((pow((vec_muro[k].X2-vec_nino[i].X),2) + pow((vec_muro[k].Y2-vec_nino[i].Y),2)));
dis3=sqrt((pow((vec_muro[k].X2-vec_nino[j].X),2) + pow((vec_muro[k].Y2-vec_nino[j].Y),2)));

Area_trian=formula_heron(dis1,dis2,dis3);
lado[cont]=lado_punto(Area_trian);

if (lado[0]==2 || lado[1]==2 || lado[2]==2 || lado[3]==2){

return 1;


}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))){

salida=1;
}else{
}

cont=0;
k++;

}while(k!=cant_muros-1 || salida!=1 );

if (k==cant_muros-1 && salida!=1){

return 1;
}else{

return 0;
}

}

Código (c) [Seleccionar] Expandir

float formula_heron(float dis1, float dis2, float dis3){

float s,resultado;

s=(dis1+dis2+dis3)/2;
resultado = sqrt(s*(s-dis1)*(s-dis2)*(s-dis3));
return resultado;
}

Código (c) [Seleccionar] Expandir

int lado_punto(float Area_trian){

int lado;

if (Area_trian >0){

lado=1;
}else if (Area_trian<0){

lado=0;
}else{

lado=2;
}

return lado;
}


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.

[avesudra]

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 L_AB, 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.