Dec 23, 2011

Night #4: Sorting the Vertices of a Polygon

The following problem came up in my ICM course this year. A student was working on a sketch that involved tiling polygons arbitrarily drawn by a user. Allowing a user to set the vertices of a polygon should be easy enough, right? But what if the user does not happen to draw them in a nice clock-wise (or counter clock-wise) order?

Imagine for a moment, you have an ArrayList of PVectors called “vertices.” When the user clicks, the mouse you could add that mouse location to that ArrayList.

void mousePressed() {
  vertices.add(new PVector(mouseX,mouseY));
}

You could then draw that list as a polygon using beginShape() and endShape().

void draw() {
  beginShape();
  for (PVector v : vertices) {
    vertex(v.x, v.y);
  } 
  endShape(CLOSE);
}

But depending on how the user set the vertices, you might end up with:

when what you really want is the following:

One solution for solving this problem is to always sort all of the vertices according to their relative angle from the center. Let’s say you calculate the center of the polygon as the average location of all vertices.

  PVector centroid = new PVector();
  for (PVector v : vertices) {
    centroid.add(v);
  } 
  centroid.div(vertices.size());

You can then make a vector that points from the center to each vertex and get its direction (using PVector’s heading2D() method).

  for (PVector v : vertices) {
    PVector dir = PVector.sub(v, centroid);
    float a = dir.heading2D() + PI;
  }

Note how we add PI to the angle. The heading2D() function will return an angle between -PI and PI and it’ll be easier to sort if we just have an angle between 0 and TWO_PI. One way to sort an ArrayList is called a Selection Sort. In the example below, you’ll find a variation of the selection sort. The code iterates through the ArrayList, finds the element with the highest angle, removes that element and sticks it at the end of a new ArrayList. It does this again and again until the original ArrayList is empty. The result is a new ArrayList in sorted order.

Following is that example which implements all of the above into a class. If you are looking for an exercise, try allowing the user to move or delete existing vertices. Also, how you would make a system of these polygons so that the user can draw more than one?

Source: PolygonVertexSorting.zip