Рубрики

Ориентация 3 упорядоченных точек

Ориентация упорядоченного триплета точек на плоскости может быть

  • против часовой стрелки
  • по часовой стрелке
  • коллинеарны

Следующая диаграмма показывает различные возможные ориентации (a, b, c)

Если ориентация (p1, p2, p3) коллинеарна, то ориентация (p3, p2, p1) также коллинеарна.
Если ориентация (p1, p2, p3) направлена по часовой стрелке, то ориентация (p3, p2, p1) направлена против часовой стрелки, и наоборот также верно.

Учитывая три точки p1, p2 и p3, найдите ориентацию (p1, p2, p3).
Пример:

Input:   p1 = {0, 0}, p2 = {4, 4}, p3 = {1, 2}
Output:  CounterClockWise

Input:   p1 = {0, 0}, p2 = {4, 4}, p3 = {1, 1}
Output:  Colinear

Как рассчитать ориентацию?

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 σ 

Below is the implementation of above idea.

C++




// 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 colinear // 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;  // colinear        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";     return 0; }
Java




// 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 colinear     // 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// colinear                 // 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.
C#




// 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 colinear     // 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; // colinear                // 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 */


Output:

CounterClockwise

Понятие ориентации используется в следующих статьях:
Найти простой замкнутый путь для заданного набора точек
Как проверить, пересекаются ли два заданных отрезка?
Выпуклая оболочка | Набор 1 (алгоритм Джарвиса или упаковка)
Выпуклая оболочка | Комплект 2 (Грэм Скан)

Источник:
http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf

Эта статья предоставлена Радживом Агравалом . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Ориентация 3 упорядоченных точек

0.00 (0%) 0 votes