Monotone Polygons

Order points on the y-axis. The points are separated into two groups, those on the left hand side and those on the right. I have colored them black and white balls.

If you project a color onto the y-axis it is in a linear fashion. ie a ball does not double back. Mathematicians call this monotone for one direction - lookup monotone sequence.

The start and end points can often be classified either way. Then classify them to best suit the situation. (eg when designing or implementing an algorithm)

Sorting on y-axis from the polygons boundary

Given the order of points around a monotone polygon you can sort in O(n) on the y-axis. Let pts[] be an array of ordered points around boundary.

i=0
k=pts.size()-1;
for ( ; i!=k; )
{
    if (pts[i].y>pts[k].y)
        v.push_back(i++)
    else
        v.push_back(k--)
}

Describing the Monotone Polygon

You can not just give a series of points that go around a polygon because the same set of points may describe different monotone polygons.

Hence in some way the polygon is described by two lists of points,those on the left hand side and the others on the right.

I have used the concept of colored balls for opposite sides when building and implementing the Triangulating a Monotone Polygon algorithm.