How to sort all polygon points by clockwise/ anticlockwise direction?

Question

I've been reading about Jarvis's algorithm and while it has the ability to sort all "outer points" in clockwise direction, the inner points are ignored as shown below:

Does anyone know if there are any other algorithms or any additional methods i have to implement that will sort every single points in a clock-wise direction?

Thank you.

Answer 1

Here is an application to order a polygon vertices in clockwise order, using a reference point and its polar angle to every other vertex.

To change the reference point from centroid to the left bottom vertex, change the code in the snippet.

You may use sortedPolygon.reverse() for anti-clockwise order.

const getAngle = (vertex, other) => Math.atan2(other[1] - vertex[1], other[0] - vertex[0]) * 180 / Math.PI;

const getCentroid = polygon => polygon.reduce((acc, vertex, _, {length}) => [acc[0] + vertex[0] / length, acc[1] + vertex[1] / length], [0, 0]);
const getLeftBottom = polygon => polygon.sort((a, b) => a[0] - b[0] !== 0 ? a[0] - b[0] : b[1] - a[1])[0];
/* Set reference vertex here */
const getRef = getCentroid; // getLeftBottom;
/* Set whether you want to display vertices ordered or not */
const orderVertices = true;

/* Sort the polygon vertices in clockwise order */
function sort(polygon) {
    const centroid = getRef(polygon);
    return [...polygon].sort((u, v) => getAngle(centroid, u) - getAngle(centroid, v));
}

function drawPolygon(context, polygon, strokeStyle, fillStyle) {
  context.strokeStyle = strokeStyle;
  context.fillStyle = fillStyle;
  context.beginPath();
  context.moveTo(polygon[0][0], polygon[0][1]); //first vertex
  for (var i = 1; i < polygon.length; i++)
    context.lineTo(polygon[i][0], polygon[i][1]);
  context.lineTo(polygon[0][0], polygon[0][1]); //back to start
  context.fill();
  context.stroke();
  context.closePath();
}

function drawRef(context, polygon) {
    const centroid = getRef(polygon);
    context.beginPath();
    context.arc(centroid[0], centroid[1], 10, 0, 2 * Math.PI);
    context.fillStyle = 'red';
    context.fill();
    context.lineWidth = 2;
    context.strokeStyle = '#003300';
    context.stroke();
    context.closePath();
}


function avg(a, b) {
  return ~~((a + b)/2);
}
function drawLines(context, polygon) {
    const centroid = getRef(polygon);
    context.beginPath();
    for (const vertex of polygon) {
        context.moveTo(centroid[0], centroid[1]);
        context.lineTo(vertex[0], vertex[1]);
        context.font = "30px Arial";
        context.fillStyle = "green";
        context.fillText(`${Math.round(getAngle(centroid, vertex))}°`, avg(centroid[0], vertex[0]), avg(centroid[1], vertex[1]));
    }
    context.lineWidth = 2;
    context.strokeStyle = '#5de337';
    context.stroke();
    context.closePath();
}

const select = function(n) {
  var context = document.getElementById("canvas").getContext("2d");
  context.clearRect(0, 0, 500, 500);
  document.querySelector('.initial').textContent = polygons[n];
  const sortedPolygon = orderVertices ? sort(polygons[n]) : polygons[n];
  drawPolygon(context, sortedPolygon, "#888", "#88f");
  drawRef(context, polygons[n]);
  drawLines(context, polygons[n]);
  document.querySelector('.sorted').textContent = sortedPolygon;
};

const polygons = [
    [[400, 250], [100, 300], [100, 100], [300, 400], [300, 0]],
    [[300, 300], [300, 100], [-100, 400], [0, 0]],
    [[50, 150], [150, 350], [350, 150], [200, 50], [250, 320], [100, 250], [350, 250], [200, 250]],
    [[400, 300], [100, 100], [100, 300], [300, 100]]
];

const buttons = document.querySelectorAll("button");
for (let counter = 0; counter < buttons.length; counter++) {
    buttons[counter].addEventListener("click", function(){
      window.onload = select(counter);
   });
}
window.onload = select(0);

<button onclick="select(0)">Polygon 0</button>
<button onclick="select(1)">Polygon 1</button>
<button onclick="select(2)">Polygon 2</button>
<button onclick="select(3)">Polygon 3</button>
<p>Initial vertices: <span class="initial"></span><p/>
<p>Clockwise sorted vertices: <span class="sorted"></span><p/>
Polygon area : <span id='area'></span>
<canvas id='canvas' width='400' height='400'></canvas>

Answer 2

The first step in a Graham scan is to sort each coordinate by polar angle. By choosing an arbitrary (x, y) pair as your "center", you can compute the polar angle of each point relative to your center, and then sort them based on this angle. The end result sorts the polygon's point in clockwise/counterclockwise direction.

// Example program
#include <iostream>
#include <string>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>

class point {
  public:
    //default consructor sets point to 0,0
    point() { x=0; y=0; angle = 0; }

    //manually assign point
    point(int xin, int yin) { x=xin; y=yin; angle = 0; }

    //other constructors
    point(const point &p) { x = p.x; y = p.y; angle = p.angle; }
    point &operator=(const point &p) { x = p.x; y = p.y; angle = p.angle; return *this; }


    //get angle between this point and another
    double get_angle(point &p) {
        //check to make sure the angle won't be "0"
        if(p.x == this->x) { return 0; }

        //cast to double, or risk losing precision
        return( atan( double(p.y - this->y) / double(p.x - this->x) ) );
    }

    //for sorting based on angles
    //If you'd like, you can also modify the operator to behave differently,
    //such as checking the radii of the points if the lengths are the same - 
    //this would require some modification of the point class. 
    bool operator<(const point &p) const {
        return(angle < p.angle);
    }


    //and then there's these things
    void set_x(int xin) { x = xin; }
    void set_y(int yin) { y = yin; }
    void set_angle(double d) { angle = d; }

    int get_x() const { return x; }
    int get_y() const { return y; }
    double get_angle() const { return angle; }

  private:
    int x;
    int y;
    double angle;
};

//-----------------------------------------------------------------------------

//makes printing points easier
std::ostream &operator<<(std::ostream &os, const point &p) {
    os << "x: " << p.get_x() << "\ty: " << p.get_y() << "\tangle: " << p.get_angle();
    return os;
}

//=============================================================================

int main()
{
    //create a vector for points - vectors can use std::sort
    std::vector<point> points;

    point new_p(0, 0);
    for(int i=0; i<10; i++) {
        //fill the array with some random points
        //your actual data goes here - if you are using random points, don't
        //forget to seed the rng

        points.push_back(point(rand() % 100, rand() % 100));
    }


    //pick a random point to be the center
    //your data also goes here - the center doesn't have to be in the list
    point center = points[rand() % 10];

    std::cout << "center\n" << center << std::endl << std::endl;

    //sort all points by polar angle
    //be sure to use &references, otherwise your changes won't go through
    for(point &p : points) {
        double angle = center.get_angle(p);
        p.set_angle(angle);
    }

    //sort the points using overloaded < operator
    //this program sorts them counterclockwise; you can flip the vector or
    //overload a different operator to get your desired effect
    std::sort(points.begin(), points.end());


    //tadaa!
    for(point &p : points) {
        std::cout << p << std::endl;
    }
}

tl;dr By using atan((y-y0) / (x-x0)), you can calculate the polar angle of a point, based on some reference point (x0, y0). Sorting based on these angles lets you sort all the points in a clockwise or counterclockwise direction.

Good luck!

Answer 3

You can think of the points as complex numbers and sort by argument.

import numpy as np
from scipy.spatial import ConvexHull

# set up example
np.random.seed(0)
pts = np.random.multivariate_normal(np.zeros(2), np.identity(2), size=100)
hull = ConvexHull(pts)

# vertices of a randomly generated
# convex polygon in R2
verts = hull.points[hull.vertices]
# shuffle vertices
np.random.shuffle(verts)

# get complex numbers
zs = verts[:,0] + 1j * verts[:,1]
verts_sorted = verts[np.angle(zs).argsort()]

# plot
from matplotlib import pyplot as plt

fig, ax = plt.subplots()
ax.scatter(verts_sorted[:,0], verts_sorted[:,1])

for i, p in enumerate(verts_sorted):
    ax.annotate(str(i), (p[0], p[1]))

plt.savefig("verts_sorted.png")

Sample plot: