Orientación de 3 puntos ordenados

Dados tres puntos p1, p2 y p3, la tarea es determinar la orientación de estos tres puntos.

La orientación de un triplete ordenado de puntos en el plano puede ser

• en sentido anti-horario
• agujas del reloj
• colineal

El siguiente diagrama muestra diferentes orientaciones posibles de (a,b,c)
 

Si la orientación de (p1, p2, p3) es colineal, entonces la orientación de (p3, p2, p1) también lo es. 
Si la orientación de (p1, p2, p3) es en el sentido de las agujas del reloj, entonces la orientación de (p3, p2, p1) es en el sentido contrario a las agujas del reloj y viceversa.

Ejemplo: 
 

Entrada:   p1 = {0, 0}, p2 = {4, 4}, p3 = {1, 2}
Salida:  en sentido antihorario

Entrada:   p1 = {0, 0}, p2 = {4, 4}, p3 = {1, 1}
Salida:  Colineal

¿Cómo calcular la orientación? 

The idea is to use slope.  

Slope of line segment (p1, p2): σ = (y2 - y1)/(x2 - x1)
Slope of line segment (p2, p3): τ = (y3 - y2)/(x3 - x2)

If  σ > τ, the orientation is clockwise (right turn)

Using above values of σ and τ, we can conclude that, 
the orientation depends on sign of  below expression: 

(y2 - y1)*(x3 - x2) - (y3 - y2)*(x2 - x1)

Above expression is negative when σ < τ, i.e.,  counterclockwise

A continuación se muestra la implementación de la idea anterior. 
 

// A C++ program to find orientation of three points
#include <iostream>
using namespace std;
 
struct Point {
    int x, y;
};
 
// To find orientation of ordered triplet (p1, p2, p3).
// The function returns following values
// 0 --> p, q and r are collinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p1, Point p2, Point p3)
{
    // See 10th slides from following link for derivation
    // of the formula
    int val = (p2.y - p1.y) * (p3.x - p2.x)
              - (p2.x - p1.x) * (p3.y - p2.y);
 
    if (val == 0)
        return 0; // collinear
 
    return (val > 0) ? 1 : 2; // clock or counterclock wise
}
 
// Driver program to test above functions
int main()
{
    Point p1 = { 0, 0 }, p2 = { 4, 4 }, p3 = { 1, 2 };
    int o = orientation(p1, p2, p3);
    if (o == 0)
        cout << "Linear";
    else if (o == 1)
        cout << "Clockwise";
    else
        cout << "CounterClockwise";
    cout << endl;
 
    p1 = { 0, 0 }, p2 = { 4, 4 }, p3 = { 1, 1 };
    o = orientation(p1, p2, p3);
    if (o == 0)
        cout << "Linear";
    else if (o == 1)
        cout << "Clockwise";
    else
        cout << "CounterClockwise";
    cout << endl;
 
    p1 = { 1, 2 }, p2 = { 4, 4 }, p3 = { 0, 0 };
    o = orientation(p1, p2, p3);
    if (o == 0)
        cout << "Linear";
    else if (o == 1)
        cout << "Clockwise";
    else
        cout << "CounterClockwise";
    return 0;
}

// JAVA Code to find Orientation of 3
// ordered points
class Point
{
    int x, y;
    Point(int x,int y){
        this.x=x;
        this.y=y;
    }
}
 
class GFG {
     
    // To find orientation of ordered triplet
    // (p1, p2, p3). The function returns
    // following values
    // 0 --> p, q and r are collinear
    // 1 --> Clockwise
    // 2 --> Counterclockwise
    public static int orientation(Point p1, Point p2,
                                         Point p3)
    {
        // See 10th slides from following link
        // for derivation of the formula
        int val = (p2.y - p1.y) * (p3.x - p2.x) -
                  (p2.x - p1.x) * (p3.y - p2.y);
      
        if (val == 0) return 0;  // collinear
      
        // clock or counterclock wise
        return (val > 0)? 1: 2;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
            Point p1 = new Point(0, 0);
            Point p2 = new Point(4, 4);
            Point p3 = new Point(1, 2);
             
            int o = orientation(p1, p2, p3);
             
            if (o==0)    
            System.out.print("Linear");
            else if (o == 1) 
            System.out.print("Clockwise");
            else             
            System.out.print("CounterClockwise");
         
    }
}
 
//This code is contributed by Arnav Kr. Mandal.

# A Python3 program to find orientation of 3 points
class Point:
     
    # to store the x and y coordinates of a point
    def __init__(self, x, y):
        self.x = x
        self.y = y
 
def orientation(p1, p2, p3):
     
    # to find the orientation of
    # an ordered triplet (p1,p2,p3)
    # function returns the following values:
    # 0 : Collinear points
    # 1 : Clockwise points
    # 2 : Counterclockwise
    val = (float(p2.y - p1.y) * (p3.x - p2.x)) - \
           (float(p2.x - p1.x) * (p3.y - p2.y))
    if (val > 0):
         
        # Clockwise orientation
        return 1
    elif (val < 0):
         
        # Counterclockwise orientation
        return 2
    else:
         
        # Collinear orientation
        return 0
 
# Driver code
p1 = Point(0, 0)
p2 = Point(4, 4)
p3 = Point(1, 2)
 
o = orientation(p1, p2, p3)
 
if (o == 0):
    print("Linear")
elif (o == 1):
    print("Clockwise")
else:
    print("CounterClockwise")
     
# This code is contributed by Ansh Riyal

// C# Code to find Orientation of 3
// ordered points
using System;
public class Point
{
    public int x, y;
    public Point(int x,int y)
    {
        this.x = x;
        this.y = y;
    }
}
 
class GFG
{
     
    // To find orientation of ordered triplet
    // (p1, p2, p3). The function returns
    // following values
    // 0 --> p, q and r are collinear
    // 1 --> Clockwise
    // 2 --> Counterclockwise
    public static int orientation(Point p1, Point p2,
                                        Point p3)
    {
        // See 10th slides from following link
        // for derivation of the formula
        int val = (p2.y - p1.y) * (p3.x - p2.x) -
                (p2.x - p1.x) * (p3.y - p2.y);
     
        if (val == 0) return 0; // collinear
     
        // clock or counterclock wise
        return (val > 0)? 1: 2;
    }
     
    /* Driver program to test above function */<strong>
    public static void Main(String[] args)
    {
            Point p1 = new Point(0, 0);
            Point p2 = new Point(4, 4);
            Point p3 = new Point(1, 2);
             
            int o = orientation(p1, p2, p3);
             
            if (o == 0)    
                Console.WriteLine("Linear");
            else if (o == 1)
                Console.WriteLine("Clockwise");
            else           
                Console.WriteLine("CounterClockwise");
         
    }
}
 
/* This code contributed by PrinciRaj1992 */

<script>
// javascript Code to find Orientation of 3
// ordered points
 
class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}
 
 
// To find orientation of ordered triplet
// (p1, p2, p3). The function returns
// following values
// 0 --> p, q and r are collinear
// 1 --> Clockwise
// 2 --> Counterclockwise
function orientation(p1, p2, p3) {
  // See 10th slides from following link
  // for derivation of the formula
  let val = (p2.y - p1.y) * (p3.x - p2.x) -
    (p2.x - p1.x) * (p3.y - p2.y);
 
  if (val == 0) return 0; // collinear
 
  // clock or counterclock wise
  return (val > 0) ? 1 : 2;
}
 
/* Driver program to test above function */
let p1 = new Point(0, 0);
let p2 = new Point(4, 4);
let p3 = new Point(1, 2);
 
let o = orientation(p1, p2, p3);
 
if (o == 0)
  document.write("Linear");
else if (o == 1)
  document.write("Clockwise");
else
  document.write("CounterClockwise");
 
// This code is contributed by Saurabh Jaiswal
</script>

CounterClockwise
Linear
Clockwise

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)

El concepto de orientación se utiliza en los siguientes artículos: 

• Encuentre la ruta cerrada simple para un conjunto dado de puntos
• ¿Cómo verificar si dos segmentos de línea dados se cruzan?
• Casco convexo | Conjunto 1 (Algoritmo de Jarvis o Wrapping)
• Casco convexo | Juego 2 (escaneo de Graham)

Este artículo es una contribución de Rajeev Agrawal . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.