4
$\begingroup$

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:

Image showing polygon vertices

I do not understand the vertices of the second left bound $\{p_4,p_3,p_2\}$. How are these vertices derived?

$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Simon F May 27 '16 at 9:59
  • 1
    $\begingroup$ 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." $\endgroup$ – Ecir Hana May 28 '16 at 13:56
1
$\begingroup$

(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.

$\endgroup$
0
$\begingroup$

The left bounds are defined as edges where the interior of the polygon is on the right. Think of them as just being the left edge of the shape. You can see from the given polygon that one left edge (the one furthest on the left) starts at P0 and goes to P6. This is the leftmost edge of the polygon. The only other area of the polygon that has an edge on the left side is the part that looks like a devil horn on the right. Its left edge starts at P4 and goes up to P2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.