I'm interested in how this algorithm would work. Can you provide links to definitions of "orient" and "to be consistent with" in this context?

At first I thought that I'd have to go through the list of possibly millions of vertexes looking for the highest x value. Then return through the list again to do the actual labeling. A more efficient way would be to just go through the list of vertexes once labeling along the way, making an assumption as to which side was the initial "inside". Traversing the list we can also keep track of the highest x value. When we find it, if we find that our assumption was incorrect and that all the "inside" labels are actually "outside" labels, then we just flip the label for all of the labels.