Explanation of the Vatti clipping algorithm I am going through the Vatti Arbitrary Polygon Clipping Algorithm, but got stuck at their very initial explanation. It says the following:


  Call an edge of a polygon a left or right edge if the interior of the polygon is to the right or left, respectively. Horizontal edges are considered to be both left and right edges. A key fact that is used by the Vatti algorithm is that polygons can be represented via a set of left and right bounds which are connected lists of left and right edges, respectively, that come in pairs. Each of these bounds starts at a local minimum of the polygon and ends at a local maximum. Consider the "polygon" with vertices $\{p_0, p_1, ..., p_8\}$ shown in Figure 1(a). The two left bounds have vertices $\{p_0, p_8, p_7, p_6\}$ and $\{p_4, p_3, p_2\}$, respectively. The two right bounds have vertices $\{p_0, p_1, p_2\}$ and $\{p_4, p_5, p_6\}$.


The image it refers to is:



I do not understand the vertices of the second left bound $\{p_4,p_3,p_2\}$. How are these vertices derived?
(Promoting "comment" to an answer)

It looks to me that it's just finding monotonic runs of edges. Given a defined winding order (in this case anticlockwise), then you can identify {P6, P7, P8, P0} as a decreasing run, as is {P2, P3, P4}. Since the left most vertex, P8, is in (**the middle of) a decreasing run, the decreasing runs define left boundaries and, therefore, increasing runs are right boundaries.

**it just occurred to me that if the left most point is at the beginning/end of a monotonic run then a slightly more involved rule will need to be applied involving the edges entering/leaving that point.