11
$\begingroup$

How to sort vertices of a polygon in counter clockwise order?

I want to create a function (algorithm) which compares two vectors $\vec v$ and $\vec u$ which are vertices in a polygon. It should choose the vertex which counter clockwise index inside the polygon is higher. The first index should be the bottom left vertex.

pentagon example

I this example it should choose $\vec u$.

For the first quadrant I can say that $\vec u > \vec v$ if $|\vec u| > |\vec v|$ and $\forall\vec u > \forall\vec v$. The length should be weighted more than the angle in order that vertex 1 gets a lower index than vertex 2. But this rule only works for the first quadrant. I could first move the whole polygon into the first quadrant but I want to find a better solution. Any ideas?

$\endgroup$
  • $\begingroup$ Are you looking for an analytical function or an algorithm? For the second case you could just loop over the vertices numbers. $\endgroup$ – anderstood Oct 17 '14 at 19:15
  • $\begingroup$ Counter clockwise index from where? Are you assuming that your polygons are convex? $\endgroup$ – Steven Stadnicki Oct 17 '14 at 19:15
  • $\begingroup$ Otherwise you can check the sign of the angles (u,v) but it depends on the center and could be complicated if the polygon is complex. $\endgroup$ – anderstood Oct 17 '14 at 19:17
15
$\begingroup$

If your polygon is convex, take any point in the interior of the polygon, e.g. the average of all the vertices. Then you can compute the angle of each vertex to the center point, and sort according to the computed angles. This will work for any point inside the polygon. Note you will get a circular ordering.

$\endgroup$
  • $\begingroup$ Thanks for your contribution. $\endgroup$ – VoidCatz Oct 17 '14 at 19:37
  • $\begingroup$ Some background from Wikipedia. $\endgroup$ – Vorac May 11 '16 at 13:37
  • $\begingroup$ This algorithm breaks when the polygon is a quadrilateral since all angles are equal. My solution was to take the midpoint and then move it very slightly by a value that will not move it outside of the polygon. After that, not all angles are perfectly equal, and the algorithm functions as normal $\endgroup$ – Russell Strauss Oct 26 at 21:02
4
$\begingroup$

Here is my Java code based on the correct answer: 1) get centroid coordinates 2) calculate degree between two point, sort the point based on the degree

 private static class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "x=" + x + " y=" + y;
    }
}

public Point findCentroid(List<Point> points) {
    int x = 0;
    int y = 0;
    for (Point p : points) {
        x += p.x;
        y += p.y;
    }
    Point center = new Point(0, 0);
    center.x = x / points.size();
    center.y = y / points.size();
    return center;
}

public List<Point> sortVerticies(List<Point> points) {
    // get centroid
    Point center = findCentroid(points);
    Collections.sort(points, (a, b) -> {
        double a1 = (Math.toDegrees(Math.atan2(a.x - center.x, a.y - center.y)) + 360) % 360;
        double a2 = (Math.toDegrees(Math.atan2(b.x - center.x, b.y - center.y)) + 360) % 360;
        return (int) (a1 - a2);
    });
    return points;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.