points (x,y), in which directio are they connected?

safra · 2011-02-10 08:39:25

Hi,

I have a number of consecutive points (x,y) in an array, they are all connected like p1 with p2, p2 with p3, p3 with p4 etc. with the last vector connected with p1.

I have to find out whether the points are connected in clockwise direction or counterclockwise direction. Can anyone think of some clever way to find this out?

Thanks!

bobbym · 2011-02-10 10:15:45

Hi safra;

Welcome to the forum! Clockwise implies circular. So the points will be in all directions. Points on top of the circle are pointing one way while the points on the bottom are pointing in the other. Same thing with the sides. Can you be a little clearer?

Bob · 2011-02-10 21:29:31

hi safra and bobbym

See diagram below. I think safra wants to know if a trip around the perimeter is clockwise ot anticlockwise.

I had an idea that finding X would help but the idea evaporated as I wrote it out. So I'm still working on it.

Bob

Bob · 2011-02-11 01:58:20

hi safra

Here's a more considered reply.

I had thought that just calculating the rotation from P1 to P2 and checking whether it was positive or negative would be enough.

But then I realised that the polygon may not be convex. (see diagram below)

So it seems you will have to calculate the angle of rotation for P1 to P2, then P2 to P3 ..... and add them up. This should reveal whether the overall rotation is positive or negative.

Method. Take O as the origin.

Repeat until last point is once more P1

Calculate gradient of OPn and OPn+1
Calculate angle PnOPn+1
Add to angle sum total

If total is 360 the rotation is one way and if -360, the rotation is the other way.

I haven't interpreted which is clockwise and which is anticlockwise because it depends how you calculate the gradients.

You need to be consistent about this or the sign of the angle won't reveal which way you are turning.

I have shown the angles for my illustration on the diagram.

Bob

Last edited by Bob (2011-02-11 02:13:11)

safra · 2011-02-13 01:25:49

Hi guys, thanks for the replies!

@Bobbym, indeed it involves a large number of points all connected, the shape isn't necessarily circular. They can go up down, left right, left and so fort, but lines between points never cross! The points represent the outer vertices of a mesh. Meanwhile I found some info about this. One guy had a clever remark saying that in this case the direction is always either clockwise or ccw because of the nature of how the triangles are setup. But on testing this I found that this is not necessarily true although it seems there is a pattern. Not sure if I can rely on that as it involves processing of many meshes simulataneously I am looking for another way, a way that is for sure bullet proof.

@Bob Bundy, Not sure where O comes from, the origin, is this (0,0)? Also find it it complicated to figure out how to automatically determine whether the angle is positive or negative. I can see you define it as positive when the order of the points pPrevious, O, pNext is clockwise. But how to figure that out? And why is p4, O, p1, -260 and not +100?

Last edited by safra (2011-02-13 01:26:43)

Bob · 2011-02-13 08:19:05

hi safra,

LATER EDIT. SORRY, I HAVE FOUND A FLAW WITH WHAT FOLLOWS, SO I AM HAVING A RE-THINK.

EVEN LATER EDIT. Ok. I think I'm sorted now. The suggestion below won't work. I'll explain why in a new post. I'll leave it here for the record and in case someone can spot how to improve it into a method. However, I've come up with a method which I think is sound although I haven't proved all the details. I'll put all into a fresh post which follows.

I was taking + as counter-clockwise.

And why is p4, O, p1, -260 and not +100?

+100 would be P1OP4 not P4OP1

How to work out an angle. (see diagram below)

To keep the arithmetic simple I've taken P1 as (3,4) and P2 as (-12,5)

I want to calculate P1OP2.

ARCTAN(4/3) = 53.1301
ARCTAN(5/-12)=-22.6199

So it would seem that P1OP2 = -75.75

But clearly, this is wrong. The problem arises because inverse trig calculations give 'principle values'. So this approach will only be reliable if we can sort out the true angles.

So I worked as follows.

(i) Make unit vectors from the two points.

and

(ii) Find the rotation matrix, R, that takes P1 onto P2

(iii) Write out the two equations from RP1 = P2

and

and solve for theta

ARCSIN(theta) gives 75.7499673021964 and ARCCOS(theta) = 104.250032697804

From these two apparently different values it is possible to be certain that theta = 104.250032697804
since SIN is still positive in the second quadrant and COS is negative.

This is a long process but does yield correct results in all four quadrants. If you are trying to write a procedure for theta you'll have to compute theta using both SIN and COS and then uniquely deduce the true angle, free of principle value problems.

For a one off though, I'd just plot the points and look!

Bob

Last edited by Bob (2011-02-14 00:40:12)

Bob · 2011-02-14 01:06:49

hi again,

This problem doesn't seem to be at all easy. The trouble is that both co-ordinate geometry and vector space theory lack a definition of clockwise, and, with one exception which I make use of, don't include the concept in any theorems.

At first I thought you could get the angle (+ or -) between the origin and two points (OP1 and OP2, say) by getting gradients and using ARCTAN.

But, as I showed in the post above, this fails when at least one of the points is not in the first quadrant.

So then, I thought to use both sin and cos, using the fact that the pair of answers could be taken together to reveal the true angle between the lines.

Trouble is that fails too as these functions are periodic. There would be no way to determine whether an angle, once found, should be, say, +225 or - 135 degrees. That flaw is fatal in terms of using the sum of the angles to reveal clockwise or counter clockwise.

But here's an outline of a method that should work.

I'll call the clockwise or not nature of the polygon its 'sense'.

You find a circle with at least three of the points on its circumference that encloses all the remaining points. It is a property of that circle that it will have the same sense as the polygon.

step (i) Pick any three points out of P1, P2 etc. (There must be at least three for the problem to be meaningful.) Let's call them P, Q and R.

Find the circumcircle of these points; in particular its centre and radius.

Check if the remaining points lie inside the circle. If they do, that's the circle we want. If a point S lies outside then try again with P, Q and S. If R isn't inside this circle, try P, R, S and if that fails Q, R, S will work.

So now repeat the check on this circle. Are any points remaining outside it? If yes, repeat the step above to get a bigger circle.

Keep going until you have a circle with three ( or more ) points on its circumference, lets call them X, Y and Z, and all the other points inside.

step 2. Use the parametric form of the equation of the circle.

Start with theta = 0 and increase stepwise until the co-ordinates of one of the points is calculated. Rename this point, X.

Continue to increase theta stepwise until a second point is found; renaming it Y

Continue to find the theta for Z.

Look at the P1, P2 ... points and find which is X, which is Y and which is Z.

If Py comes before Pz then the sense is clockwise; otherwise it is counter clockwise.

Bob

Last edited by Bob (2011-02-14 01:15:09)

safra · 2011-02-15 00:41:43

Many thanks Bob for all your efforts!

All points are in the first quadrant, but I belief there is still a issue with the first approach regarding detrmining whether and angle is for example +225 or - 135, correct?

Yor second solution contains a lot of Math specific terminology and syntax. I must admit, all that is a bit rusty over here : ). I have to go away for a couple of weeks, when I am back I will see if I can get this to work!

Thanks again!

Bob · 2011-02-15 01:07:33

hi safra,

You are very welcome. It is an interesting problem to tackle.

First quadrant only should make it easier. I'll await you next post. If you want any further explanation do post again.

Bob

Math Is Fun Forum

#1 2011-02-10 08:39:25

points (x,y), in which directio are they connected?

#2 2011-02-10 10:15:45

Re: points (x,y), in which directio are they connected?

#3 2011-02-10 21:29:31

Re: points (x,y), in which directio are they connected?

#4 2011-02-11 01:58:20

Re: points (x,y), in which directio are they connected?

#5 2011-02-13 01:25:49

Re: points (x,y), in which directio are they connected?

#6 2011-02-13 08:19:05

Re: points (x,y), in which directio are they connected?

#7 2011-02-14 01:06:49

Re: points (x,y), in which directio are they connected?

#8 2011-02-15 00:41:43

Re: points (x,y), in which directio are they connected?

#9 2011-02-15 01:07:33

Re: points (x,y), in which directio are they connected?

Board footer