# How to detect path progression direction

**URL:** <https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404>\
**Category:** Coding Questions\
**Created:** [November 11, 2019, 3:04pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404 "2019-11-11T15:04:21Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![jeykech](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@jeykech](https://discourse.processing.org/u/jeykech)\
**Post date:** [November 11, 2019, 3:04pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/1 "2019-11-11T15:04:21Z")

</div>

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

 ![dire1](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/6453aadaf4aea5520482a0a58581d53aeedfd97f.jpeg)

how I want them to be  
 ![dire2](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/6/6e06cd289a83109d2dddd649fe9575681d8c0780.jpeg)

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[0]) and (centroid, path[1])). 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 !

---

<div class="post-metadata">

**Author:** ![Lexyth](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/lexyth/32/7403_2.png) [@Lexyth](https://discourse.processing.org/u/Lexyth)\
**Post date:** [November 11, 2019, 3:21pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/2 "2019-11-11T15:21:56Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![jeykech](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@jeykech](https://discourse.processing.org/u/jeykech)\
**Post date:** [November 11, 2019, 3:39pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/3 "2019-11-11T15:39:03Z")

</div>

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

```auto
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[0]); // not used here 
   v1=PVector.sub(bary,Liste[1]);
   v2=PVector.sub(Liste[1],Liste[0]);
   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  
 ![jpg1](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/a/a482579eff0d07399cd777979689fc10af7c822e.jpeg)  
after  
 ![jpg2](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/d/d72777162aad64c83a9cb1a9107d7952d0f5ae69.jpeg)

---

<div class="post-metadata">

**Author:** ![Lexyth](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/lexyth/32/7403_2.png) [@Lexyth](https://discourse.processing.org/u/Lexyth)\
**Post date:** [November 11, 2019, 4:22pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/4 "2019-11-11T16:22:29Z")

</div>

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…

---

<div class="post-metadata">

**Author:** ![bohnacker](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/bohnacker/32/5868_2.png) [@bohnacker](https://discourse.processing.org/u/bohnacker)\
**Post date:** [November 11, 2019, 4:22pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/5 "2019-11-11T16:22:46Z")

</div>

Hi @jeykech,

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

> <https://stackoverflow.com/questions/1165647/how-to-determine-if-a-list-of-polygon-points-are-in-clockwise-order>

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

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

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

  points[0] = new PVector(5, 0); 
  points[1] = new PVector(6, 4);
  points[2] = new PVector(4, 5);
  points[3] = new PVector(1, 5);
  points[4] = 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:

```auto
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;
}

```

---

<div class="post-metadata">

**Author:** ![jeykech](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@jeykech](https://discourse.processing.org/u/jeykech)\
**Post date:** [November 11, 2019, 4:42pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/6 "2019-11-11T16:42:43Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![bohnacker](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/bohnacker/32/5868_2.png) [@bohnacker](https://discourse.processing.org/u/bohnacker)\
**Post date:** [November 12, 2019, 12:13pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/8 "2019-11-12T12:13:38Z")

</div>

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.

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

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

  // just for testing: some points
  points[0] = new PVector(5, 0); 
  points[1] = new PVector(6, 4);
  points[2] = new PVector(4, 5);
  points[3] = new PVector(1, 5);
  points[4] = 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

  // start with 0
  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;
}

```

---

<div class="post-metadata">

**Author:** ![jeykech](https://avatars.discourse-cdn.com/v4/letter/j/e47774/32.png) [@jeykech](https://discourse.processing.org/u/jeykech)\
**Post date:** [November 12, 2019, 12:31pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/9 "2019-11-12T12:31:30Z")

</div>

@bohnacker thanks and thank you all guys !

---

<div class="post-metadata">

**Author:** ![jeremydouglass](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/jeremydouglass/32/20_2.png) [@jeremydouglass](https://discourse.processing.org/u/jeremydouglass)\
**Post date:** [November 12, 2019, 7:36pm UTC](https://discourse.processing.org/t/how-to-detect-path-progression-direction/15404/10 "2019-11-12T19:36:43Z")

</div>

See also two previous related discussions of sorting points by heading / angle:

- [https://forum.processing.org/two/discussion/19469/sort-a-pvector-array](https://forum.processing.org/two/discussion/19469/sort-a-pvector-array)
- [https://forum.processing.org/two/discussion/15046/sorting-points-in-an-arraylist-clockwise](https://forum.processing.org/two/discussion/15046/sorting-points-in-an-arraylist-clockwise)

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().

```auto
// 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[6];
  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
  pts = pheadsort(pts);
}

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.
PVector[] pheadsort(PVector[] pts) {
  /**
   * 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) {
      return Float.compare(a.heading(), b.heading());
    }
  };

  // do the sort
  Arrays.sort(pts, VEC_CMP_HEAD);
  return pts;
}

```

![SortPVectorArray--screenshot](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/2X/0/0d4d47b9c7708bb4bb3460c1e8dbc38f394107f3.png)