Geometría: posición relativa de un punto respecto a una línea.

[jplj]

Hola:

El problema que trato de resolver es el siguiente:

Dada una línea definida por n puntos, a su vez definidos por sus coordenadas (x,y), determinar la posición relativa (derecha, izquierda) de otro punto dado.

Agradecería cualquier sugerencia, referencia, ... que me ayudara a resolverlo.

Muchas gracias de antemano.

[Neftali [Germán.Estévez]]

Si no entindo mal, dado tu punto P(Px, Py), lo que deberías saber es cual es el punto que corresponde a la recta que tiene la misma coordenada Y que el tuyo (pare eso sería perfecto saber la función que define la recta).

Si no tienes la función supongo que debes hacerlo por interpolación de los puntos existentes en la recta.

Una vez que sepas el punto A(Ax, Ay) que corresponde a la recta y que su coordenada Y (Ay) es igual a la de tu punto (Py), basta con que compares las otras dos, Ax y Px para saber si queda a izquierda o derecha.

[roman]

No me queda claro el problema. Una recta se determina por sólo dos puntos, de manera que hablar de n puntos que determinen una recta suena raro.

Por otra parte, la derecha e izquierda de una recta son conceptos relativos a la dirección en la que recorres la recta, así que primero hay que establecer un vector de dirección de la recta. Si tienes dos puntos P0 y P1 de la recta, el vector P1 - P0 es el vector que va de P0 a P1.

Necesitas un vector ortogonal a la recta que apunte hacia la izquierda de ésta, y este sería, si no me equivoco, Q=(-(y1-y0), x1-x0), suponiendo que P0=(x0,y0) y P1=(x1,y1).

Ya con esto, y nuevamente si no me equivoco porque la geometría analítica la tengo totalmente oxidada, dado un punto P=(x,y), para determinar si está a la izquierda o derecha de la recta dirigida, debes tomar su producto escalar (trasladando al origen) con el vector ortogonal:

(P-P0)*Q

El valor de este producto es

0 si el punto está sobre la recta
>0 si el punto está a la izquierda de la recta
<0 si el punto está a la derecha de la recta

// Saludos

[jplj]

Creo que no he expresado bien el problema.

• La posición la quiero saber respecto a una línea -no una recta- arbitraria como pudiera ser la definida por una línea electrica de alta tensión. El trazado podría ser más sinuoso.
• Los puntos -en coordenadas cartesianas- son indeterminados, aunque no creo que en la práctica llegen a 100.
• Por último, para poder obtener la posición relativa del punto dado, el usuario deberá determinar un punto de referencia/observación e introducir los puntos que designan la línea de izquierda a derecha respecto a este punto.

[jplj]

Por si pudiera interesar, la solucion que he implementado es la siguiente:

Siendo:

.- True -> Dentro / Detrás / Derecha
.- False -> Fuera / Delante / Izquiera

Código Delphi [-]

TMc_Punto = record
  x: double;
  y: double;
end;
TMc_Lista_Puntos = array of TMC_Punto;


function Posicion_relativa(Puntos_Zona: TMc_Lista_Puntos;
                             Punto: TMC_Punto): Boolean;
function Convert_LineaToZona(Puntos_Linea: TMc_Lista_Puntos;
                     Fondo: Integer; Lado: Boolean): TMc_Lista_Puntos;overload;
function Convert_LineaToZona(Puntos_Linea: TMc_Lista_Puntos;
                               Lado: Boolean): TMc_Lista_Puntos;overload;


////////////////////////// Control zona poligonal ///////////////////////////
//                                                                         //
//  Permite evaluar un punto para saber si está dentro de una zona         //
//    poligonal dada.                                                      //
//                                                                         //
//  La zona está marcada por los vértices que vienen dados por FPuntos,    //
//    que es un array dinámico de un registro con dos variables (x, y).    //
//                                                                         //
//  El punto a evaluar que se debe pasar a la función es un registro de    //
//    dos variables (x, y).                                                //
//                                                                         //
//    Desarrollo:                                                          //
//      - Se toman vectores desde el punto a evaluar y cada uno de los     //
//         vertices del polígono.                                          //
//      - Obtenemos el signo del producto vectorial de cada vector y el    //
//         siguiente.                                                      //
//      - Se calcula el ángulo entre un vector y el siguiente.             //
//      - Se suman todos los ángulos (si el signo del producto vectorial   //
//         es negativo, el ángulo a sumar es negativo.                     //
//      - Por último se comprueba si la suma da un valor próximo a Pi(está //
//         dentro) o próximo a cero (fuera).                               //
//                                                                         //
//  La función devuelve 'true' si el punto está dentro y 'false' si no.    //
//                                                                         //
/////////////////////////////////////////////////////////////////////////////
function Posicion_relativa(Puntos_Zona: TMc_Lista_Puntos;
                           Punto: TMC_Punto): Boolean;
var
  vector: TMc_Lista_Puntos;
  difAngulo: array of double;
  situac: boolean;
  i, h, vertice: integer;
  d, m, c, v, anguloTotal: double;
  moduloV1: double;
  moduloV2: double;
  prodVectSigno: double;
begin
  anguloTotal := 0;
  vertice := 0;
  for i := 0 to Length(Puntos_Zona) - 1 do //bucle igual al número de vértices.
  begin
    h:= i+1;
    if h > Length(Puntos_Zona) - 1 then h:= 0;
      if i = 0 then
      begin
        SetLength(vector, Length(vector) + 1); // ampliamos el array.
        vector[i].x := Puntos_Zona[i].x - punto.x; // creamos un vector entre el punto a evaluar y el primer vértice.
        vector[i].y := Puntos_Zona[i].y - punto.y;
      end;

      if (i >= 0) and (i < Length(Puntos_Zona) - 1) then
      begin
        Setlength(vector, Length(vector) + 1); // ampliamos el array.
        Setlength(difAngulo, Length(difAngulo) + 1); // ampliamos el array.
        vector[h].x := Puntos_Zona[h].x - punto.x; // creamos un vector entre el punto a evaluar y el segundo vértice.
        vector[h].y := Puntos_Zona[h].y - punto.y; // idem pero para la coordenada "y".
      end;

      if ((vector[i].x = 0) and (vector[i].y = 0)) or ((vector[h].x = 0) and (vector[h].y = 0)) then vertice := 1 // si el punto a evaluar coincide con un vector directamente se devuelve "dentro" para evitar una indeterminación de 0/0.
      else
      begin
        prodVectSigno := (vector[i].x * vector[h].y) - (vector[i].y * vector[h].x); // calcula el signo del producto vectorial de un vector y el siguiente.
        moduloV1 := Sqrt(Power(vector[i].x, 2) + Power(vector[i].y, 2)); // calcula el módulo del primer vector.
        moduloV2 := Sqrt(Power(vector[h].x, 2) + Power(vector[h].y, 2)); // calcula el módulo del segundo.

        v:= (vector[i].x * vector[h].x + vector[i].y * vector[h].y); // se calcula el producto escalar del primer y segundo vector.
        m:= (moduloV1 * moduloV2);
        c:= v/m; // para hallar el coseno del ángulo entre dos vectores, se divide el producto escalar entre el producto de sus módulos.

        if (c > 1) or (c < -1) then // acotamos el coseno del ángulo entre -1 y 1 para evitar errores.
        begin
          c:= Int(c)
        end;

        d:= ArcCos( c ); // calculamos el ángulo entre dos vectores consecutivos.
        if prodVectSigno > 0 then difAngulo[i] := d else difAngulo[i] := -d; // damos el signo del producto vectorial al ángulo.

       anguloTotal := anguloTotal + difAngulo[i]; // vamos sumando o restando los angulos de cada par de vectores consecutivos.
       Setlength(difAngulo, length(difAngulo) + 1); // ampliamos el array.
    end;
  end;
  if vertice = 1 then situac := true
  else
  begin
    if Abs(anguloTotal) < 3 then situac := false // si la suma total de ángulos tiende a 0, devuelve false.
      else situac := true; // si la suma total de ángulos tiende a Pi, devuelve true.
  end;
  result := situac;
end;

////////////////////////// Control Línea /////////////////////////
{                                                                           
  Amplia con dos puntos un array de puntos que define una línea para obte- 
  ner un array que define una zona.                                        
                                                                           
  Los dos puntos que nuevos serán perpendiculares a la linea que une el
  punto inicial y final de la línea.
           (b)                         (c)
           o--------------------------o
          /                           |
          |                           |
          |                           |
         /                            |
         |                            |
         --o--------------------------o
           (a)                          (d)

 Dada la línea a-b y en el caso de querer determinar los puntos que se encuen-
 tren a la izquierda de ella, se obtiene los puntos d y c perpendiculares a la
 recta que une a y b y se incluyen al incicio (punto p) y al final (punto c) del
 array de puntos que definen línea a-b, de tal forma que ahora tenermos un
 array de puntos que definen una zona que será tratada en la función:
  .- Posicion_relativa

 Fondo: distancia a-d
 Lado:
    .- true: derecha
    .- false: izquierda

}                                          
///////////////////////////////////////////////////////////////////////////////
function Convert_LineaToZona(Puntos_Linea: TMc_Lista_Puntos;
                              Fondo: Integer; Lado: Boolean): TMc_Lista_Puntos;

  //----------------------------------------------------------------------------
  ////////////////////// Función Desplazamiento //////////////////////////
  //                                                                    //
  //  Sea una recta r que pasa por los puntos O y P.                    //
  //                                                                    //
  //  Dado un punto origen O(X, Y), otro destino P(X1, Y1) y los        //
  //  desplazamientos L1 [paralelo a r] y L2 [perpendicular a r] con    //
  //  respecto a P, devuelve un array con las cordenadas (x, y) del     //
  //  punto desplazado.                                                 //
  //                                                                    //
  ////////////////////////////////////////////////////////////////////////
  function Desplazam(X, Y, X1, Y1, L1, L2: double): TMC_Punto;
  var
    Ang: double;
    sAng, cAng: double;
    coordDesp: TMC_Punto;
  begin
    Ang := arctan2(X1 - X, Y1 - Y);
    cAng := cos(Ang);
    sAng := sin(Ang);
    coordDesp.x := X1 + (sAng * (L1) + cAng * (L2));
    coordDesp.y := Y1 + (cAng * (L1) - sAng * (L2));
    result := coordDesp;

var
  //se emplea para guardar la línea de coordinación más los puntos a izquierda o derecha una distancia Fondo.
  FPuntos_Zona: TMc_Lista_Puntos;
  FPoint: TMC_Punto;
  dist: Double;
  i: Integer;
begin
   //Calcula la distandia de la recta que une el primer y último punto de la línea de coordinación.
   dist := Sqrt(Power(Puntos_Linea[Length(Puntos_Linea)-1].x - Puntos_Linea[0].x, 2)
            + Power(Puntos_Linea[Length(Puntos_Linea)-1].y - Puntos_Linea[0].y, 2));

   //amplia el array FPuntos_Zona a dos más que FPuntos.
   SetLength(FPuntos_Zona, Length(Puntos_Linea) + 2);
   if not Lado then
   begin
     FPoint := Desplazam(Puntos_Linea[0].x, Puntos_Linea[0].y,
                Puntos_Linea[Length(Puntos_Linea) - 1].x,
                Puntos_Linea[Length(Puntos_Linea) - 1].y, -dist, Fondo);
     FPuntos_Zona[0].x := Round(FPoint.x);
     FPuntos_Zona[0].y := Round(FPoint.y);
     for i := 1 to Length(Puntos_Linea) do FPuntos_Zona[i] := Puntos_Linea[i-1];
     FPoint := Desplazam(Puntos_Linea[0].x, Puntos_Linea[0].y,
                  Puntos_Linea[Length(Puntos_Linea) - 1].x,
                  Puntos_Linea[Length(Puntos_Linea) - 1].y, 0, Fondo);
     FPuntos_Zona[Length(FPuntos_Zona) - 1].x := Round(FPoint.x);
     FPuntos_Zona[Length(FPuntos_Zona) - 1].y := Round(FPoint.y);
   end
   else
   begin
     FPoint := Desplazam(Puntos_Linea[0].x, Puntos_Linea[0].y,
                Puntos_Linea[Length(Puntos_Linea) - 1].x,
                Puntos_Linea[Length(Puntos_Linea) - 1].y, -dist, -Fondo);
     FPuntos_Zona[0].x := Round(FPoint.x);
     FPuntos_Zona[0].y := Round(FPoint.y);
     for i := 1 to Length(Puntos_Linea) do FPuntos_Zona[i] := Puntos_Linea[i-1];
     FPoint := Desplazam(Puntos_Linea[0].x, Puntos_Linea[0].y,
                        Puntos_Linea[Length(Puntos_Linea) - 1].x,
                        Puntos_Linea[Length(Puntos_Linea) - 1].y, 0, -Fondo);
     FPuntos_Zona[Length(FPuntos_Zona) - 1].x := Round(FPoint.x);
     FPuntos_Zona[Length(FPuntos_Zona) - 1].y := Round(FPoint.y);
   end;
   Result:= FPuntos_Zona;
end;
//------------------------------------------------------------------------------
function Convert_LineaToZona(Puntos_Linea: TMc_Lista_Puntos;
                              Lado: Boolean): TMc_Lista_Puntos;
var
  dist: Double;
begin
  dist := Sqrt(Power(Puntos_Linea[Length(Puntos_Linea)-1].x - Puntos_Linea[0].x, 2)
            + Power(Puntos_Linea[Length(Puntos_Linea)-1].y - Puntos_Linea[0].y, 2));
  Result:= Convert_LineaToZona(Puntos_Linea, Round(dist*50), lado);
end;

Por último para usarlas:

Código Delphi [-]

Siendo:
.- FPuntos un array of TMC_Punto que contiene los puntos que definen la línea o bien una zona poliongal 
.- Punto el punto a evaluar
.- FValorCorrecto: el valor correcto esperado de la evaluación.


function TMc_Ctrl_ZonaPoligonal.Situacion(punto: TMC_Punto): Boolean;
begin
  Result:= Posicion_relativa(FPuntos, punto);
end;

function TMc_Ctrl_Lineal.Situacion(punto: TMC_Punto): Boolean;
var
  FPuntos_Zona: TMc_Lista_Puntos;
begin
    FPuntos_Zona:= Convert_LineaToZona(FPuntos, FValorCorrecto);
    if Posicion_relativa(FPuntos_Zona, punto) then
      Result:= FValorCorrecto
    else
      Result:= not FValorCorrecto;
end;