6
$\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?

Improve this question
$\endgroup$
3
  • 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, 2016 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, 2016 at 13:56
  • $\begingroup$ @EcirHana The example of the OP is actually based on that, which can be found at what-when-how.com/computer-graphics-and-geometric-modeling/… $\endgroup$
    – Rafael Eyng
    May 3, 2021 at 19:19

3 Answers 3

Reset to default
2
$\begingroup$

{𝑝0,𝑝8,𝑝7,𝑝6} and {𝑝4,𝑝3,𝑝2} are called "left bounds" because if you look at both these bounds, the polygon interior is to the right of them:

image1

Likewise, {𝑝0,𝑝1,𝑝2} and {𝑝4,𝑝5,𝑝6} are "right bounds" because the polygon interior is at their left:

image2

For reference, this example comes from: http://what-when-how.com/computer-graphics-and-geometric-modeling/clipping-basic-computer-graphics-part-5/

Improve this answer
$\endgroup$
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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