CODEWITHSUNDEEP
algorithmmatlabmathgeometry
Ahmed Abobakr
Ahmed Abobakr

Reputation: 1666

Determine whether the direction of a line segment is clockwise or anti clockwise

I have a list of 2D points (x1,y1),(x2,y2)......(Xn,Yn) representing a curved segment, is there any formula to determine whether the direction of drawing that segment is clockwise or anti clockwise ?

any help is appreciated

Upvotes: 8

Views: 4375

Answers (3)

Yvon
Yvon

Reputation: 2983

Now this is my approach, as mentioned in a comment to the question -

Another approach: draw a line from starting point to ending point. This line is indeed a vector. A CW curve has most of its part on RHS of this line. For CCW, left.

I wrote a sample code to elaborate this idea. Most of the explanation can be found in comments in the code. 

clear;clc;close all

%% draw a spiral curve
N = 30;
theta = linspace(0,pi/2,N); % a CCW curve
rho = linspace(1,.5,N);
[x,y] = pol2cart(theta,rho);
clearvars theta rho N

plot(x,y);
hold on

%% find "the vector"
vec(:,:,1) = [x(1), y(1); x(end), y(end)]; % "the vector"

scatter(x(1),y(1), 200,'s','r','fill') % square is the starting point
scatter(x(end),y(end), 200,'^','r','fill') % triangle is the ending point
line(vec(:,1,1), vec(:,2,1), 'LineStyle', '-', 'Color', 'r')

%% find center of mass
com = [mean(x), mean(y)]; % center of mass

vec(:,:,2) = [x(1), y(1); com]; % secondary vector (start -> com)

scatter(com(1), com(2), 200,'d','k','fill') % diamond is the com
line(vec(:,1,2), vec(:,2,2), 'LineStyle', '-', 'Color', 'k')

%% find rotation angle
dif = diff(vec,1,1);
[ang, ~] = cart2pol(reshape(dif(1,1,:),1,[]), reshape(dif(1,2,:),1,[]));
clearvars dif

% now you can tell the answer by the rotation angle
if ( diff(ang)>0 )
    disp('CW!')
else
    disp('CCW!')
end

One can always tell on which side of the directed line (the vector) a point is, by comparing two vectors, namely, rotating vector [starting point -> center of mass] to the vector [starting point -> ending point], and then comparing the rotation angle to 0. A few seconds of mind-animating can help understand.

Upvotes: 3

Luis Mendo
Luis Mendo

Reputation: 112689

One possible approach. It should work reasonably well if the sampling of the line represented by your list of points is uniform and smooth enough, and if the line is sufficiently simple.

  1. Subtract the mean to "center" the line.
  2. Convert to polar coordinates to get the angle.
  3. Unwrap the angle, to make sure its increments are meaningful.
  4. Check if total increment is possitive or negative.

I'm assuming you have the data in x and y vectors.

theta = cart2pol(x-mean(x), y-mean(y)); %// steps 1 and 2
theta = unwrap(theta); %// step 3
clockwise = theta(end)<theta(1); %// step 4. Gives 1 if CW, 0 if ACW

This only considers the integrated effect of all points. It doesn't tell you if there are "kinks" or sections with different directions of turn along the way.

A possible improvement would be to replace the average of x and y by some kind of integral. The reason is: if sampling is denser in a region the average will be biased towards that, whereas the integral wouldn't.

Upvotes: 5

Penguino
Penguino

Reputation: 2176

Alternately, you can use a bit of linear algebra. If you have three points a, b, and c, in that order, then do the following:

 1)  create the vectors u = (b-a) = (b.x-a.x,b.y-a.y) and v = (c-b) ...
 2) calculate the cross product uxv = u.x*v.y-u.y*v.x
 3) if uxv is -ve then a-b-c is curving in clockwise direction (and vice-versa).

by following a longer curve along in the same manner, you can even detect when as 's'-shaped curve changes from clockwise to anticlockwise, if that is useful.

Upvotes: 9

Related Questions