# 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?

• It looks to me that it's just finding runs of monotonic edges. Given a defined winding order (in this case anticlockwise), then you can identify P6 through P0 as a decreasing run, as is P2 through P4. Since the left most vertex, P8, is on a decreasing run, the decreasing runs define left boundaries (and therefore increasing runs, right boundaries) – Simon F May 27 '16 at 9:59
• Not sure if it will help you but Clipper uses Vatti's algorithm. The docs mention: "A section in 'Computer graphics and geometric modeling: implementation and algorithms' by By Max K. Agoston (Springer, 2005) discussing Vatti Polygon Clipping was also helpful in creating the initial Clipper implementation." – Ecir Hana May 28 '16 at 13:56