Clockwise Check of Three Points

Geeks


Description:

Given three points p1, p2 and p3, find orientation of (p1, p2, p3).

If orientation of (p1, p2, p3) is collinear, then orientation of (p3, p2, p1) is also collinear. If orientation of (p1, p2, p3) is clockwise, then orientation of (p3, p2, p1) is counterclockwise and vice versa is also true.

Example:

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

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

Idea:

根据两个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 counterclockwise (left turn)
If  σ = τ, the orientation is collinear
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
Above expression is 0 when σ = τ, i.e., collinear
Above expression is positive when σ > τ, i.e., clockwise

Code:

#include <iostream>
#include <vector>
using namespace std;

struct Point{
    int x;
    int y;
};

enum OrientationType{
    Colinear, Clockwise, ConterClockwise
};

OrientationType checkOrientation(Point p1, Point p2, Point p3){
    int flag = (p3.y - p2.y)*(p2.x-p1.x) - (p2.y-p1.y)*(p3.x-p2.x);
    if(flag==0){
        return Colinear;
    }
    else if(flag>0){
        return ConterClockwise;
    }
    else{
        return Clockwise;
    }
}

int main(){
    Point p1={0, 0};
    Point p2={4, 4};
    Point p3={1, 2};

    cout<<checkOrientation(p1, p2, p3);
}

results matching ""

    No results matching ""