How can I efficiently determine which side of a line segment is internal to the polygon?

Pick the vertex with the highest x value. You can label the edges touching it. Now just walk along your polygon and label the edges consistently.