¿en Que Lado Estoy?

[marcode]

 Tengo 2 puntos en un plano, que describen una línea que lo corta, y quiero saber si un punto dado está a un lado o al otro.

Ya lo tengo, pero me gustaría encontrar la forma más rápida posible. Tengo que comprobar muchos puntos, por lo que algunas operaciones se deberían poder aprovechar para hacerlas en un solo paso, el resto debería ser una comprobación rápida con cada uno de los puntos para averiguar en que lado se encuentra.

Lo ideal creo, es que la solución final me devuelva un número positivo si está a un lado, y negativo si está al otro.

[ZüNdFoLGe]

 No te entiendo. Si los 2 puntos están en el plano y "describen" una recta como dices, entonces ésta también forma parte del plano, pero no lo corta. Tendrías que especificar, tal vez haya algo que divida al plano en 2, o que los puntos estén fuera del plano.

[marcode]

 Ok, lo siento, es que quizás no se expresar correctamente lo que quiero.

Voy a intentar dibujarlo. Los puntos que tengo para describir la linea divisoria son A y B y los puntos que estan a un lado son o y los que estan a otro son x.

                  o           /
                            /                          x
                          /
                o      B
                      /
                    /     x
   o               /           x
                /    x
              A                                                   x
             /
           /
         /  x

Espero que esté ya claro lo que quiero decir. Los extremos son infinitos y el plano tambien. Pero con A y B lo puedo dividir imaginariamente.

[ZüNdFoLGe]

 ok...
lo que yo haría sería fijar un sistema de coordenadas (y no va a quedar otra...) y luego encontrar la ecuación de la recta que pasa por los 2 puntos A y B...

r= ax + b

luego para cada punto, pueden darse 3 situaciones...
- está a un lado de la recta
- está al otro lado
- está en la recta misma

entonces dado un punto de coordenadas (c1,c2)  primero hallo el punto de corte de la recta  x=c1 con la recta 'r' anterior, o sea, sustituyo la coordenada c1 en la recta r y luego simplemente se compara ese valor con la coordenada c2 del punto:
- si c2 es mayor que 'r' obtenido  --> está por "arriba" de la recta
- si c2 es menor que 'r' obtenido  --> está por "abajo" de la recta
- sino c2 pertenece a la recta (es decir que 'r'==c2)

espero que hayas entendido mi idea...

salu2

[senior wapo]

 Si lo he entendido bien, pides clasificarlos en 2D. Si es asi, la manera más rápida de clasificar un punto individual es usando la pendiente de la recta, es decir, cuanto aumenta una coordenada cuando incrementas la otra en 1. Tienes dos casos, que la recta se incline más de 45 grados, o menos.  Este cálculo te da a que lado de la recta está el punto usando simplemente una multiplicación.

Ojo: esto te dice a que lado está pero no a que distancia de la recta. Si necesitas la distancia, no te libras de hacer el cálculo completo (2 multiplicaciones).


Otra cosa: ¿ son puntos aleatorios ? Porque si son por ejemplo, los vertices de una caja y quieres saber a que lado está la caja, entonces, solo necesitas comprobar 2 vértices (si me apuras sólo 1): los vertices cuya diagonal es más perpendicular a la linea / plano de separación.

EDIT: se me adelantó ZüNdFoLGe con lo de la pendiente.

[Elvis Enmanuel]

 La distancia de un punto a un plano te devuelve un valor negativo si el punto está por detras del plano.
Si lo que quieres hacer es un clipping 2d, en mi web http://www.gamedusa.com
tengo un tutorial de cómo realizar el recorte de manera muy eficiente usando planos.

ains.

[marcode]

 Gracias por responder a los tres.

ZüNdFoLGe:

Pero el hallar la perpendicular para cada punto, ¿no será un coste en tiempos de ejecución demasiado elevado?, también recuerdo que la recta puede estar en cualquier posición del espacio, y A puede estar arriba y B abajo, o puede estar totalmente horizontal o totalmente vertical, ¿esto no requiere muchos cálculos?.

senior:
¿Lo que propones no tendrá un coste también muy elevado?.

La distancia no me interesa, y son un número elevado de puntos, pongamos 1000, es decir, no importa que haya que hacer un número relativamente elevado de cálculos previos que sirvan para todos, pero luego al comprobar en el bucle uno por uno en que lado está cada punto, sí debe ser rapidísimo.

Los puntos son al azar, en realidad pueden ser objetos pero mejor describirlos por el punto de posición, y debería servir por ejemplo para saber si ha traspasado una meta (usando una comprobación), para saber si están en el frustrum de una cámara (usando dos), o para saber si ha colisionado con un polígono (usando tantas comprobaciones como lados).

Elvis:

La distancia de un punto a un plano te devuelve un valor negativo si el punto está por detras del plano.

Esto no lo acabo de entender.

He mirado tu tutorial por encima y creo que lo que busco es más sencillo y simple que eso, en cualquier caso son bienvenidos los tutoriales en pdf y seguro que será útil en otro momento. Por cierto, que os costará escribirlos también en castellano :P (Offtopic).

Y comentaros también que ya tengo implementado el algoritmo que hice yo mismo hace tiempo, es bastante rápido. Hago una serie de cálculos previos y después para cada uno de los puntos hago en total 2 multiplicaciones, 1 suma y 2 restas, y una comprobación de <0, si no doy con otro mejor y a alguien le interesa lo puedo explicar, pero me parecería raro que no hubiera otra forma un poco más rápida.  

[Elvis Enmanuel]

 Prueba con esto, te devolverá la distancia (con signo) dependiendo a que lado se encuentre el punto.
En mi tutorial esta explicado como optimizar la fórmula de la distancia de un punto a un plano, para aplicarlo
en 2d.

(px,py) = posición del punto en 2d
(x1,y1) = primer punto de la línea
(x2,y2) = segundo punto de la línea

float distancePointToLine(float px,float py,float x1,float y1,float x2,float y2) const {
   return ((y1 - y2)*px) + ((x2 - x1)*py) + (x1 * y2) - (x2 * y1);
}

ó si prefieres (devolverá true si se encuentra a una distancia negativa)

bool pointSide(float px,float py,float x1,float y1,float x2,float y2) const {
   return (((y1 - y2)*px) + ((x2 - x1)*py) + (x1 * y2) - (x2 * y1))>=0.0f;
}

NOTA: la forma en que le pases los valores de la linea influye mucho, ya que si los inviertes (x1 en vez de x2 e y1 en lugar de y2)
el signo te saldria también invertido.

ains.

[Elvis Enmanuel]

 

ó si prefieres (devolverá true si se encuentra a una distancia negativa)

positiva, quería decir...

ains.

[ZüNdFoLGe]

ZüNdFoLGe:

Pero el hallar la perpendicular para cada punto, ¿no será un coste en tiempos de ejecución demasiado elevado?, también recuerdo que la recta puede estar en cualquier posición del espacio, y A puede estar arriba y B abajo, o puede estar totalmente horizontal o totalmente vertical, ¿esto no requiere muchos cálculos?.

*calcular el corte de la perpendicular con la recta es de orden 1, ya que basta con retornar (inline) la sustitución de la coordenada c1 en la recta.

*encontrar la recta que determinan A y B también es de orden constante, la cantidad de operaciones (en flops) son 2 ya que se hacen 2 restas, 1 producto y 1 división.

El tema de optimizar los costos depende de la idea que tengas en concreto. Yo no se si los puntos A y B son aleatorios  o fijos, ni tampoco la cantidad de los demas puntos.

[senior wapo]

 ¿ Lento ?  Si la recta no se mueve, es fija entre frames, solo tienes que precalcular su pendiente (ancho/alto o alto/ancho según orientación). Lo único a tener en cuenta es el ángulo de la recta porque la pendiente tiende a infinito a medida que el ángulo se aproxima a 90 grados (linea vertical).

A ver. te lo explico con la alternativa más sencilla de entender, usando división. Tienes la recta con el punto A (A.x, A.y) el punto B (B.x, B.y) y un punto a comprobar P (P.x, P.y )
precalculas:  Pendiente_recta = (B.y - A.y) / ( B.x - A.x)

para comprobar un punto:

Pendiente_punto = (P.y - A.y) / (P.x - A.x)
si Pendiente_punto > Pendiente_recta, esta por encima, si es menor por debajo, si es igual, está en la línea).

Eso es usando división porque no almacenamos información extra de la recta, solo sus puntos, que era más facil de entender.

Podemos mejorarlo cambiando la división por una multiplicación (son menos caras):
En lugar de comparar pendientes:
precalculas:  recta_tan = tangente del angulo que forma la linea de A a B.

para comprobar un punto:
valor = recta_tangente * ( P.x - A.x );
si valor > P.y el punto esta a un lado, si menor, al otro, si es igual, está en la línea.


Como ves, solo requiere una multiplicación. Lo único a tener en cuenta es que el ángulo sea inferior o igual a 45, y si es mayor, intercambias x e y en las fórmulas (y ajustas signos)

EDIT: Otra vez XD O yo escribo lento o todos posteamos a la vez =p

[marcode]

 

Prueba con esto....
.....
.....
.....

NOTA: la forma en que le pases los valores de la linea influye mucho, ya que si los inviertes (x1 en vez de x2 e y1 en lugar de y2)
el signo te saldria también invertido.

ains.

Sí, exactamente esto es lo que busco, una fórmula muy precisa, y que el invertir A y B de como resultado el invertir el signo también.

Entonces, como lo que me interesa es tratar grupos de cientos o miles a la vez, he reescrito la función para tratar por ejemplo 1000 puntos, ya que algunas operaciones son las mismas para todos que se pueden aprovechar.

Ahora recibe las coordenadas en estructuras de vértice, y el punto en un array de 1000 puntos a comprobar, cuya estructura tiene además una propiedad para guardar en ella si es positivo o negativo o lo que es lo mismo, si está dentro o fuera.

Código [Seleccionar] Expand


bool pointSideGroup(VERTICE V1, VERTICE V2, PUNTO Punto[1000])
{
  float DifY = V1.y - V2.y;
  float DifX = V2.x - V1.x;
  float DifMult = V1.x * V2.y - V2.x * V1.y;

  for (int i=0;i<1000;i++)
  {
     P[i].bDentro =  ( ( DifY * Punto[i].x ) + ( DifX * Punto[i].y ) + DifMult ) >= 0.0f;
  }
}

Creo que esto debería valer, todavía no lo he probado, se usan 2 multiplicaciones y 2 sumas (me ganas y además es más elegante), ¿crees que funcionará así?. Lo probaré.

--------

Ahora estoy leyendo lo de senior y ZüNdFoLGe, y no se si serán mejor, la de senior parece que usa pocos cálculos. Hay que tener en cuenta que la dirección y posición de los puntos o ángulo que describe la línea imaginaria varía continuamente y por supuesto los puntos a comprobar también. Pero la ventaja es que se comprueba la misma línea para todos los puntos, y ahí es donde me interesa la optimización, en poder comprobar muchísimos puntos de golpe rápidamente.

Si estáis todos en lo cierto tendría varias alternativas en las que se usan todo tipo de operaciones, pero no se cual es la mejor para lo que pretendo, a ver si podemos encontrar la más óptima.

Creo que la de senior es como la mia, pero optimizada, es decir, yo hago el doble de cálculos más una suma en lugar de hacer la comprobación de los 45 grados y creo que ahí puede estar la fórmula buena.

PD: Joder, vaya lio que me estoy haciendo ya, escribís tan rápido que no da tiempo a pensar XD.

[tewe76]

 

NOTA: la forma en que le pases los valores de la linea influye mucho, ya que si los inviertes (x1 en vez de x2 e y1 en lugar de y2)
el signo te saldria también invertido.

¿Y en qué orden se deben de pasar entonces? Entiendo que la distancia es negativa para los puntos que quedan a tu izquierda si estás en X1Y1 mirando hacia X2Y2. ¿Es así?

[marcode]

 Se ha de pasar en el orden dependiendo de si consideras un lado de la línea dentro y el otro fuera.

si quieres obtener los puntos que hay dentro de dos lineas paralelas hay que pasar a la función una de las dos invertidas. La primera te daría positivo (dentro) los puntos que están a la derecha, y la otra te daría positivo los puntos que están a la izquierda.

Es decir por razones prácticas mejor considerar positivo aquellos que estén dentro (a su derecha), ya sea de la meta, del frustrum, o de un polígono. Y solo hay que preocuparse de pasar en el orden correcto los puntos de cada línea.

         |      o  |      x
         B        A
    x   |  o      |
         |          |      x
  x     |      o  |           x
        A        B
         |          |

Para saber si hay un punto dentro de una región se puede pasar el orden de los puntos de las líneas en el sentido de las agujas del reloj. si en alguna de las comprobaciones A-B, B-C, C-D, D-A, te da negativo (a su izquierda relativa), se puede estar seguro de que está fuera de la región y no hace falta comprobar el resto, si todas dan positivo es que está dentro.

            /   x   |             
      ---B------C--
    x   /      o   |  x
       /  o     o   |      x
   --A--------- D---
    /     x        |           

Despues de mirar las distintas opciones, aunque no me han quedado del todo claras, para mi caso en la que quiero comprobar miles de puntos sobre las mismas lineas, creo que es mejor lo que propuso senior. Calculo la tangente una vez y despues compruebo con una sencilla operación todos los puntos.

[Marci]

 La de senior parece la mejor, lo máximo que yo consigo son dos multiplicaciones y una resta por punto (nooo), lo saco haciendo productos vectoriales y mirando si la normal es positiva o negativa.