CODEWITHSUNDEEP
algorithmvectorvector-graphics
Rahul
Rahul

Reputation: 870

How to find direction of a vector path

I have a vector path (made up from lineto, curveTo points) and I want to determine its direction (clockwise, anticlockwise).

Is there any algorithm which can be used for the same?

The reason I want to do this is that I am getting two paths from different functions; one is always clockwise but the other function returns anticlockwise paths sometimes; when I combine these two paths and fill the resultant path then the non-zero winding fill rule creates a hole in the regions where the path overlaps.

So I am trying to solve the problem by converting all paths to clockwise direction before combining them.

Upvotes: 1

Views: 2960

Answers (2)

Savvas Dalkitsis
Savvas Dalkitsis

Reputation: 11592

EDIT: see the comments below:

What is clockwise? Case in point. Do you consider this path clockwise?:

alt text

If you said yes, then what about this one?

alt text

Follows my original proposal which works fine for convex paths:

You can use the cross product of 3D vectors.

If a,b two vectors such that :

a = (a1, a2, a3)

b = (b1, b2, b3)

Then the cross product is

axb = (a2b3-a3b2, a3b1-a1b3, a1b2 - a2b1)

Now if you assume that the path you describe does not intersect itself (which nullifies the point of clockwise or counterclockwise) then all you need is the first three points of it in the order they are presented. And from them you create 2 vectors whose cross product you can calculate.

So assuming you have these points in order:

a = (a1, a2)

b = (b1, b2)

c = (c1, c2)

you create the following vectors:

A = (A1, A2) = ab = (b1-a1, b2-a2)

B = (B1, B2) = bc = (c1-b1, c2-b2)

and then all you need is the third coordinate of AxB which is:

A1B2 - A2B1

or

(b1-a1)(c2-b2) - (b2-a2)(c1-b1)

If this coordinate is positive then your path is counterclockwise, if it is negative then it is clockwise.

Upvotes: 3

Josh Lee
Josh Lee

Reputation: 177665

Pick any point in the interior of the path component, then use the fill rule to determine whether its winding number is +1 or −1:

  1. Draw a ray from the point out to infinity
  2. Start with a count of zero
  3. Add 1 every time a path segment crosses the ray from left to right
  4. Subtract 1 every time a path segment crosses the ray from right to left

(If the path component is simple there will only be one crossing. If the path is not simple, i.e. it crosses itself, then it does not mean anything to say if it is clockwise or not.)

Then, since you want clockwise components you should expect a count of +1. A count of −1 indicates that the component is inside out.

Upvotes: 2

Related Questions