# How to detect path progression direction

hi guys,

let’s say I have different paths from a vector file, and I want them to be all the vertices evolving in clockwise direction

how there are now

how I want them to be what I have done so far is:
I have already calculated the centroid of each path, and I want to calculate the signed angle between segments (centroid, path) and (centroid, path)). when using anglebetween() I get an absolute value, but I want the sign to know if it is counter clockwise or clockwise.
the idea is to reverse the order of the path[vertices] array when I detect the “wrong” direction.

is there an easiest way or a simple command/library for that
thanx !

1 Like

If the angle goes over 180, then to find wether the angle is clockwise of counterclockwise is easy. If it‘s over 180, then it‘s the other way around. (Though i don‘t know in which direction it goes with smaller angle).

But that could give a wrong result, if the shape starts out counterclockwise, but then goes clockwise, like the star one would do.

Therefore you‘ll probably want to calculate the total of all paths minus the last one, just to see wether the total is over 0 or under it. (Since the total of all should equal 0).

well I have a working solution but I am not sure it is the most elegant way to do it

``````void setDir(PVector[] Liste){ // Liste is an arraye of the vertices of the path
PVector bary,v0,v1,v2;
PVector[] listy;

int leng=Liste.length;

listy= new PVector[leng]; // lesty is a temporary Array to store new values
bary = Centroid(Liste); // calculating the centroid of the path (barycentre)
v0=PVector.sub(bary,Liste); // not used here
v1=PVector.sub(bary,Liste);
v2=PVector.sub(Liste,Liste);
v2.rotate(PI/2);

float dot=PVector.dot(v1,v2);
for(int kk=0;kk<leng;kk++){
listy[leng-kk-1]=Liste[kk];
}

if(dot<0){
for(int kk=0;kk<leng;kk++){
Liste[kk]=listy[kk];
}
}

}
``````

since I already have the centroid of each path, I calculated the vector between the centroid and one vertex, then a I calculated the perpenducal vector the first segment, and used the dot product to detect direction, and reversed the array of vertices!
by the way is there a command to find a normal to 2d vector and an other to reverse a PVector array ?

before after 1 Like

To reverse it, there isn‘t one, as far as i know. But you could always build one yourself.

As for the normal, you can use normal(), but i‘m not sure wether it also works in 2D. I just calculate them directly, when i need them…

Hi @jeykech,

I had the same question some time ago and found this thread on stackoverflow:

I wrote this small function and it should work quite well to determine if the polygon is clockwise (it returns true) or not.

``````PVector[] points = new PVector;

void setup() {
size(100, 100);

points = new PVector(5, 0);
points = new PVector(6, 4);
points = new PVector(4, 5);
points = new PVector(1, 5);
points = new PVector(1, 0);

println(isClockwise(points));
}

boolean isClockwise(PVector[] vertices) {
float area = 0;
for (int i = 0; i < vertices.length; i++) {
int j = (i + 1) % vertices.length;
area += vertices[i].x * vertices[j].y;
area -= vertices[j].x * vertices[i].y;
}
return area > 0;
}
``````

To reverse the array if it is not clockwise you’ll need something like that:

``````for (int i = 0; i < points.length / 2; i++)
{
PVector temp = points[i];
points[i] = points[points.length - i - 1];
points[points.length - i - 1] = temp;
}
``````
1 Like

@bohnacker , can you provide any explanation for your algorithm? I don’t really understand the logic behind it ?!

Hi @jeykech, I’ve put in some comments to explain. Note, that the script below is a bit different from the originally posted, because I found that it matches better to the stackoverflow discussion that way.

``````PVector[] points = new PVector;

void setup() {
size(100, 100);

// just for testing: some points
points = new PVector(5, 0);
points = new PVector(6, 4);
points = new PVector(4, 5);
points = new PVector(1, 5);
points = new PVector(1, 0);

// the function isClockwise() returns true, if the polygon is clockwise, so reverse if not
if (!isClockwise(points)) {
// reversing an array could be done by swapping the first with the last entry, the second with the second last, ....
// so just go throught the entries until the middle of the array
for (int i = 0; i < points.length / 2; i++) {
// these lines are swapping two entries
PVector temp = points[i];
points[i] = points[points.length - i - 1];
points[points.length - i - 1] = temp;
}
}

println(points);
}

// the function isClockwise calculates the signed area of a polygon
boolean isClockwise(PVector[] vertices) {
// the algorithm uses this formula to sum up the area:
// https://en.wikipedia.org/wiki/Shoelace_formula

float area = 0;
// go through all the points of the polygon
for (int i = 0; i < vertices.length; i++) {
// index i is the actual point. index j is the next point.
int j = (i + 1) % vertices.length;

// this is the main part of the shoelace formula:
area -= vertices[i].x * vertices[j].y;
area += vertices[j].x * vertices[i].y;

// another way to calculate the signed area:
// area += (vertices[j].x - vertices[i].x) * (vertices[j].y + vertices[i].y);
}

// if area is smaller than 0 it returns true, otherwise false.
return area < 0;
}

``````
2 Likes

@bohnacker thanks and thank you all guys !

One general purpose method is to write a Java Comparator, which compares any two point headings and returns a greater or less measure. Then any PVector[] can be sorted by heading with Arrays.sort().

``````// Sort PVector Array
// 2019-11-12 Processing 3.4
// based on PointsVecArray from Toolboxing

import java.util.Arrays;
import java.util.Comparator;

PVector[] pts;
PVector ctr;

void setup(){

// make some random points on a circle in shuffled order
pts = new PVector;
PVector spinner = new PVector(width/3, 0);
for(int i=0; i<pts.length; i++){
pts[i] = spinner.rotate(random(TWO_PI)).copy();
}

// sort the points clockwise
}

void draw() {
background(128);
translate(width/2,height/2);
ellipse(0,0,5,5);

// draw lines
for(int i=0; i<pts.length; i++){
int i2 = (i+1)%pts.length;
line(pts[i].x, pts[i].y, pts[i2].x, pts[i2].y);
}

// draw labeled points
for(int i=0; i<pts.length; i++){
ellipse(pts[i].x, pts[i].y, 3, 3);
text(i, pts[i].x, pts[i].y);
}
}

// Sort a list of PVectors by heading.
// You may want to first center the points around 0,0.
/**
* h comparator: sort vectors by heading (angle of rotation from origin)
*/
Comparator<PVector> VEC_CMP_HEAD = new Comparator<PVector>() {
@ Override public final int compare(final PVector a, final PVector b) { 