Autor Tema: Detectar si un punto px,py está en una recta rx1,ry1~rx2,ry2.

0 Usuarios y 1 Visitante están viendo este tema.

05 Mayo, 2016, 06:16 am
Leído 1263 veces

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Esto es común en programación, creo, pero va más allá: No hay que saber programación para responder esto, sino matemática.

Imaginen que tenemos un plano, que es como una gráfica, en el sentido de que tiene x e y. Hay una línea, que puede ser la gráfica en sí, y se nos dice que hay un punto en xy (se nos da el valor de cada uno, y también de la línea), y se nos pregunta si está o no en la línea. Normalmente miraríamos la gráfica, lo ubicaríamos, y listo, pero digamos que tenemos que explicarlo.

Acá tengo un programa que simula la cuestión, pero algo falla.
https://dl.dropboxusercontent.com/u/169164922/Punto%20y%20recta2.swf
Debería decir false cuando el punto no esté en la línea y true cuando sí. La línea cuando se agranda o achica se ve un poco mal, pero eso no importa. La cuestión es que, por lo visto falla cuando la línea empieza en puntos mayores que 0, y creo que también cuando el punto está exactamente donde empieza.

Bueno, uds podrían decirme un método para detectar si el punto está en la línea, pero soy durísimo para entender (ya me han mencionado la pendiente y una ecuación pero no entiendo de dónde sale ni por qué funciona) así que mejor ayúdenme con mi método.

Código: [Seleccionar]
if (Recta._x <= Punto._x && RectaXfin >= Punto._x) {
      if (Recta._y <= Punto._y && RectaYfin >= Punto._y) {
         Porce = Punto._x*100/(Recta._x+RectaXfin);
         if (RectaYfin*Porce/100+Recta._y == Punto._y) {
            Colision = true;
         }
      }
   }
}
Dice: Si el x del inicio de la recta (viendo desde la izquierda) es anterior que el x del punto, y si el x final de la recta es posterior al x del punto, entonces la línea está entre la distancia x de la recta. O dicho de otro modo, el punto no está en el área roja ni en la verde:

Luego dice lo mismo pero para la y, descartando entonces las áreas azul y amarilla, o sea, si se cumplen las 4 condiciones significa que el punto está en el área blanca.
Nota: La y tiene los valores al revés de lo normal, o sea crece hacia abajo.
Bueno, si se cumplen las 4 condiciones entonces lo que he pensado es ver su punto x, ver ese mismo x en la línea, ver cual es su y, y luego compararlo con el y del punto.
Supongamos que la línea empieza en 0,0 y llega hasta 100,100. Y el punto está en 50,50. ¿Qué y tiene el x 50 de la línea? Intuyo que 50, pero hay que ver por qué.
Cuando x es 0, y es 0.
Cuando x es 100, y es 100.
y=x, o y=100% de x.
¿Cómo se llega a saber que es 100%?
x - 100%
y - ??
O sea: y*100/x
En un caso: 0*100/0, no me da 100...  :P
En el otro: 100*100/100=100.
Sabiendo que y es el 100% de x, si decimos que x es 50...
50 - 100%
?? - 100%
50*100/100=50
O sea, el y de la línea, en el x 50, sería 50.
Cuando en el código pongo:
Porce = Punto._x*100/(Recta._x+RectaXfin);
Punto._x sería el 50 que dije, ese punto x que en la línea vamos a ver qué y tiene. Es como si trazáramos una línea que pase por el punto x verticalmente y choque entonces con un punto x de la línea. Vamos a ver qué y tiene ese punto.
...
En realidad veo que el método que estoy describiendo no es el mismo que usé. Disculpen, les dejo esto que había escrito:
http://sofosagora.net/offtopic-general/deteccion-colisiones-t6818.html#p142370

Intentaré dejarme y dejarles las cosas más claras, pero si ya alguno puede ayudarme bienvenido sea. Quisiera usar porcentajes que es lo que entiendo (más o menos, según se ha visto u.u ), no pendientes ni cosas más avanzadas que evidentemente menos entiendo.

Gracias.

05 Mayo, 2016, 07:35 am
Respuesta #1

ingmarov

  • Moderador Global
  • Mensajes: 4,900
  • País: hn
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Creo que bastaría con probar que (suponiendo   \( \bf r_{x1}<p_x<r_{x2} \).  ):

\( \dfrac{r_{y2}-r_{y1}}{r_{x2}-r_{x1}}=\dfrac{p_y-r_{y1}}{p_x-r_{x1}} \)
No te confíes, revisa lo que escribo. Yo también me equivoco.
Odio el autocorrector de Android...

05 Mayo, 2016, 11:59 am
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 Hay un problema en la práctica para hacer este tipo de comprobaciones. En general cuando uno quiere comprobar una igualdad en programación, es fácil  que aunque en teoría se cumpla, en la práctica y debido a los errores de redondeo, el ordenador no la detecte.

 Entonces lo que suele hacerse es indicar una tolerancia.

 Es decir en lugar de comprobar que \( A=B \) se comprueba si \( |A-B|<tolerancia \), donde tolerancia es un número "pequeño" que tendremos que ajustar dependiendo del contexto.

 En tu caso además si las coordenadas del punto son coordenadas de un punto en una pantalla serán discretas, enteras, luego uno no puede esperar que la igualdad se cumpla de manera exacta aunque aparentemente en la pantalla el punto se vea dentro del segmento.

Saludos.

06 Mayo, 2016, 09:57 pm
Respuesta #3

Tachikomaia

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 208
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Creo que ya está, y la línea se ve mejor ahora.
https://dl.dropboxusercontent.com/u/169164922/Punto%20y%20recta3.swf

Código: [Seleccionar]
if (Recta._x<=Punto._x && RectaXfin>=Punto._x) {
    if (Recta._y<=Punto._y && RectaYfin>=Punto._y) {
        Porce = (Punto._x-Recta._x)*100/(RectaXfin-Recta._x);
        RectaYCorresondiente = (RectaYfin-Recta._y)*Porce/100+Recta._y;
        if (RectaYCorresondiente == Punto._y) {
            Colision = true;
        }
    }
}
Explicarlo lo dejo para otro momento, pero si quieren explicarlo uds mejor, o avisen si les parece que hay un error. Tenía algunos errores en las ecuaciones de antes y posiblemente me confundí en algún momento sobre lo que estaba calculando.

ingmarov:
Me hiciste notar que posiblemente no sea necesario chequear que el punto en y esté "por dentro" de los puntos de la recta. Total al final se chequea él en relación con el único punto de la recta que podría estar tocando. Chequear algo más amplio al inicio sirve para evitar que la computadora haga cálculos que la mayoría de las veces, si se hace dicho chequeo, no sería necesario hacer, por eso lo seguiré poniendo, pero no tengo mucha idea sobre qué da mejor rendimiento realmente

En cuanto a tu fórmula,el tema es que no entiendo por qué funciona, ya he visto más de una (o la misma más de una vez, ni idea), pero preferí seguir por el lado de los porcentajes que es algo más entendible para mí.

el_manco:
"En general cuando uno quiere comprobar una igualdad en programación, es fácil  que aunque en teoría se cumpla, en la práctica y debido a los errores de redondeo, el ordenador no la detecte."
¡Cuánta razón! En este caso es sólo una práctica (lo que realmente necesito es colisión circulo-triángulo), pero podría haberme cansado bastante revisando fórmulas que estuvieran bien pero que fallaran por el motivo que dices. Por ahora no encontré fallas, pero debe ser porque tiende a no verse pequeñas diferencias, o sea si le pongo que el punto está a 0.001 x del inicio de la recta a lo mejor considera que están en la misma posición xD