Dirección de un punto desde un segmento de línea

La dirección del punto P dado desde un segmento de línea simplemente significa dadas las coordenadas de un punto P y un segmento de línea (digamos AB), y tenemos que determinar la dirección del punto P desde el segmento de línea. Eso es si el punto se encuentra a la derecha del segmento de línea oa la izquierda del segmento de línea.
 

Line Segment

El punto puede estar detrás del segmento de línea, en ese caso asumimos una línea imaginaria al extender el segmento de línea y determinar la dirección del punto.
 

extending the line segment and determine the direction of point

* Solo hay tres casos, ya sea que el punto esté en el lado izquierdo, en el lado derecho o en el segmento de línea en sí.
Este es un problema muy fundamental y se encuentra comúnmente para las direcciones en el mapa en línea
Ejemplo : suponga que un usuario A tiene que ir al punto C en el siguiente mapa, el usuario llega primero al punto B, pero después de eso, ¿cómo sabe el usuario A que si él? tiene que girar a la derecha o a la izquierda. 
 

Example for Direction of a Point from a Line Segment

Conocer la dirección de un punto a partir de un segmento de línea también actúa como un bloque de construcción para resolver problemas más complicados como: 
 

  • Intersección de segmento de línea : encontrar si dos segmentos de línea se cruzan
  • Casco Convexo de un conjunto de Puntos.

El sistema de coordenadas que usaremos es un plano cartesiano, ya que la mayoría de los problemas bidimensionales usan un plano cartesiano y dado que este es un problema bidimensional.
Este problema se puede resolver usando el producto cruzado del álgebra vectorial 
. El producto cruzado de dos puntos A y B es: A x * B y – A y * B x 
donde A x y A y son las coordenadas x e y de A respectivamente . Análogamente, B x y B y son coordenadas x e y de B, respectivamente. 
El producto cruzadotiene una propiedad interesante que se usará para determinar la dirección de un punto a partir de un segmento de línea. Es decir, el producto vectorial de dos puntos es positivo si y solo si el ángulo de esos puntos en el origen (0, 0) está en el sentido contrario a las agujas del reloj. Y a la inversa, el producto vectorial es negativo si y solo si el ángulo de esos puntos en el origen está en el sentido de las agujas del reloj.
Un ejemplo sin duda lo aclararía
En la siguiente figura, el ángulo BOP es antihorario y el producto cruzado de BXP = 29*28 – 15*(-15) = 1037 que es positivo.
 

 Cross-Product

Esto nos ayuda a llegar a la conclusión de que un punto del lado derecho debe tener un producto cruzado positivo y un punto del lado izquierdo debe tener un producto cruzado negativo. También tenga en cuenta que asumimos que un punto del segmento de línea es el origen y, por lo tanto, necesitamos convertir cualquier sistema de tres puntos de modo que un punto del segmento de línea sea el origen.

El siguiente ejemplo explica el concepto
Los tres puntos A, B y P se convirtieron en A’, B’ y P’ para hacer que A sea el origen (esto se puede hacer simplemente restando las coordenadas de A del punto P y B ), y luego calcule el producto cruzado: 59*18 – (-25)*18 = 2187 
Dado que esto es positivo, el punto P está en el lado derecho del segmento de línea AB.
 

Example for Direction of a Point from a Line Segment 

C++

// C++ Program to Determine Direction of Point
// from line segment
#include <iostream>
using namespace std;
 
// structure for point in cartesian plane.
struct point {
    int x, y;
};
 
// constant integers for directions
const int RIGHT = 1, LEFT = -1, ZERO = 0;
 
int directionOfPoint(point A, point B, point P)
{
    // subtracting co-ordinates of point A from
    // B and P, to make A as origin
    B.x -= A.x;
    B.y -= A.y;
    P.x -= A.x;
    P.y -= A.y;
 
    // Determining cross Product
    int cross_product = B.x * P.y - B.y * P.x;
 
    // return RIGHT if cross product is positive
    if (cross_product > 0)
        return RIGHT;
 
    // return LEFT if cross product is negative
    if (cross_product < 0)
        return LEFT;
 
    // return ZERO if cross product is zero.
    return ZERO;
}
 
// Driver code
int main()
{
    point A, B, P;
    A.x = -30;
    A.y = 10; // A(-30, 10)
    B.x = 29;
    B.y = -15; // B(29, -15)
    P.x = 15;
    P.y = 28; // P(15, 28)
 
    int direction = directionOfPoint(A, B, P);
    if (direction == 1)
        cout << "Right Direction" << endl;
    else if (direction == -1)
        cout << "Left Direction" << endl;
    else
        cout << "Point is on the Line" << endl;
    return 0;
}

Java

// Java Program to Determine Direction of Point
// from line segment
class GFG
{
 
// structure for point in cartesian plane.
static class point
{
    int x, y;
};
 
// constant integers for directions
static int RIGHT = 1, LEFT = -1, ZERO = 0;
 
static int directionOfPoint(point A,
                            point B, point P)
{
    // subtracting co-ordinates of point A
    // from B and P, to make A as origin
    B.x -= A.x;
    B.y -= A.y;
    P.x -= A.x;
    P.y -= A.y;
 
    // Determining cross Product
    int cross_product = B.x * P.y - B.y * P.x;
 
    // return RIGHT if cross product is positive
    if (cross_product > 0)
        return RIGHT;
 
    // return LEFT if cross product is negative
    if (cross_product < 0)
        return LEFT;
 
    // return ZERO if cross product is zero.
    return ZERO;
}
 
// Driver code
public static void main(String[] args)
{
    point A = new point(),
          B = new point(), P = new point();
    A.x = -30;
    A.y = 10; // A(-30, 10)
    B.x = 29;
    B.y = -15; // B(29, -15)
    P.x = 15;
    P.y = 28; // P(15, 28)
 
    int direction = directionOfPoint(A, B, P);
    if (direction == 1)
        System.out.println("Right Direction");
    else if (direction == -1)
        System.out.println("Left Direction");
    else
        System.out.println("Point is on the Line");
    }
}
 
// This code is contributed
// by Princi Singh

Python3

# Python3 program to determine direction
# of point from line segment
  
# Structure for point in cartesian plane.
class point:
     
    def __init__(self):
         
        self.x = 0
        self.y = 0
  
# Constant integers for directions
RIGHT = 1
LEFT = -1
ZERO = 0
  
def directionOfPoint(A, B, P):
     
    global RIGHT, LEFT, ZERO
     
    # Subtracting co-ordinates of
    # point A from B and P, to
    # make A as origin
    B.x -= A.x
    B.y -= A.y
    P.x -= A.x
    P.y -= A.y
  
    # Determining cross Product
    cross_product = B.x * P.y - B.y * P.x
  
    # Return RIGHT if cross product is positive
    if (cross_product > 0):
        return RIGHT
         
    # Return LEFT if cross product is negative
    if (cross_product < 0):
        return LEFT
  
    # Return ZERO if cross product is zero
    return ZERO
 
# Driver code
if __name__=="__main__":
     
    A = point()
    B = point()
    P = point()
     
    A.x = -30
    A.y = 10 # A(-30, 10)
    B.x = 29
    B.y = -15 # B(29, -15)
    P.x = 15
    P.y = 28 # P(15, 28)
  
    direction = directionOfPoint(A, B, P)
     
    if (direction == 1):
        print("Right Direction")
    elif (direction == -1):
        print("Left Direction")
    else:
        print("Point is on the Line")
 
# This code is contributed by rutvik_56

C#

// C# Program to Determine Direction of Point
// from line segment
using System;
using System.Collections.Generic;
 
class GFG
{
 
// structure for point in cartesian plane.
public class point
{
    public int x, y;
};
 
// constant integers for directions
static int RIGHT = 1, LEFT = -1, ZERO = 0;
 
static int directionOfPoint(point A,
                            point B, point P)
{
    // subtracting co-ordinates of point A
    // from B and P, to make A as origin
    B.x -= A.x;
    B.y -= A.y;
    P.x -= A.x;
    P.y -= A.y;
 
    // Determining cross Product
    int cross_product = B.x * P.y - B.y * P.x;
 
    // return RIGHT if cross product is positive
    if (cross_product > 0)
        return RIGHT;
 
    // return LEFT if cross product is negative
    if (cross_product < 0)
        return LEFT;
 
    // return ZERO if cross product is zero.
    return ZERO;
}
 
// Driver code
public static void Main(String[] args)
{
    point A = new point(),
          B = new point(),
          P = new point();
    A.x = -30;
    A.y = 10; // A(-30, 10)
    B.x = 29;
    B.y = -15; // B(29, -15)
    P.x = 15;
    P.y = 28; // P(15, 28)
 
    int direction = directionOfPoint(A, B, P);
    if (direction == 1)
        Console.WriteLine("Right Direction");
    else if (direction == -1)
        Console.WriteLine("Left Direction");
    else
        Console.WriteLine("Point is on the Line");
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript Program to Determine Direction of Point
// from line segment
 
// structure for point in cartesian plane.
class point
{
    constructor()
    {
        this.x=0;
        this.y=0;
    }
}
 
// constant integers for directions
let RIGHT = 1, LEFT = -1, ZERO = 0;
 
function directionOfPoint(A,B,P)
{
    // subtracting co-ordinates of point A
    // from B and P, to make A as origin
    B.x -= A.x;
    B.y -= A.y;
    P.x -= A.x;
    P.y -= A.y;
  
    // Determining cross Product
    let cross_product = B.x * P.y - B.y * P.x;
  
    // return RIGHT if cross product is positive
    if (cross_product > 0)
        return RIGHT;
  
    // return LEFT if cross product is negative
    if (cross_product < 0)
        return LEFT;
  
    // return ZERO if cross product is zero.
    return ZERO;
}
 
// Driver code
let A = new point(),
          B = new point(), P = new point();
    A.x = -30;
    A.y = 10; // A(-30, 10)
    B.x = 29;
    B.y = -15; // B(29, -15)
    P.x = 15;
    P.y = 28; // P(15, 28)
  
    let direction = directionOfPoint(A, B, P);
    if (direction == 1)
        document.write("Right Direction<br>");
    else if (direction == -1)
        document.write("Left Direction");
    else
        document.write("Point is on the Line");
 
 
// This code is contributed by rag2127
 
</script>

Producción: 

Right Direction

Complejidad de tiempo: O(1)

Espacio Auxiliar: O(1)

Este artículo es una contribución de Shubham Rana . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *