<p>(Promoting "comment" to an answer)</p>

<p>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.</p>

<p>**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.</p>

CC BY-SA 3.0
2016-05-31T09:12:46.230Z
2016-06-01T09:34:21.397Z
2016-06-01T09:34:21.397Z
Simon F
<p>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.</p>

CC BY-SA 3.0
2018-04-18T00:37:45.463Z
2018-04-18T00:37:45.463Z
Guest
<p>{0,8,7,6} and {4,3,2} are called &quot;left bounds&quot; because if you look at both these bounds, the polygon interior is to the right of them:</p>
<p><a href="https://i.sstatic.net/GhMNp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GhMNp.png" alt="image1" /></a></p>
<p>Likewise, {0,1,2} and {4,5,6} are &quot;right bounds&quot; because the polygon interior is at their left:</p>
<p><a href="https://i.sstatic.net/idwor.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/idwor.png" alt="image2" /></a></p>
<p>For reference, this example comes from: <a href="http://what-when-how.com/computer-graphics-and-geometric-modeling/clipping-basic-computer-graphics-part-5/" rel="nofollow noreferrer">http://what-when-how.com/computer-graphics-and-geometric-modeling/clipping-basic-computer-graphics-part-5/</a></p>

CC BY-SA 4.0
2021-05-03T15:51:06.563Z
2021-05-03T15:51:06.563Z
Rafael Eyng
<p>I am going through the Vatti Arbitrary Polygon Clipping Algorithm, but got stuck at their very initial explanation. It says the following:</p>

<blockquote>
  <p>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\}$.</p>
</blockquote>

<p>The image it refers to is:</p>

<p><a href="https://i.sstatic.net/fFx6m.jpg" rel="noreferrer"><img src="https://i.sstatic.net/fFx6m.jpg" alt="Image showing polygon vertices"></a></p>

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

CC BY-SA 3.0
2016-05-27T09:59:49.447Z
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
CC BY-SA 3.0
2016-05-28T13:56:46.263Z
Not sure if it will help you but [Clipper](http://www.angusj.com/delphi/clipper.php) uses Vatti's algorithm. The [docs](http://www.angusj.com/delphi/clipper/documentation/Docs/Overview/_Body.htm) 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
CC BY-SA 4.0
2021-05-03T19:19:59.937Z
@EcirHana The example of the OP is actually based on that, which can be found at http://what-when-how.com/computer-graphics-and-geometric-modeling/clipping-basic-computer-graphics-part-5/
Rafael Eyng
<algorithm><polygon>
Explanation of the Vatti clipping algorithm
sajis997
# Explanation of the Vatti clipping algorithm

(Asked by: username_0 on 2016-05-26)

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](https://i.sstatic.net/fFx6m.jpg)](https://i.sstatic.net/fFx6m.jpg)

I do not understand the vertices of the second left bound $\{p\_4,p\_3,p\_2\}$. How are these vertices derived?

**Tags:** algorithm, polygon

> **Comments:**
> **username_1**: 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)  
> **username_2**: Not sure if it will help you but [Clipper](http://www.angusj.com/delphi/clipper.php) uses Vatti's algorithm. The [docs](http://www.angusj.com/delphi/clipper/documentation/Docs/Overview/_Body.htm) 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."  
> **username_3**: @username_2 The example of the OP is actually based on that, which can be found at http://what-when-how.com/computer-graphics-and-geometric-modeling/clipping-basic-computer-graphics-part-5/  

---

## 3 answers

### Answer by username_3 on 2021-05-03. Score: 2

{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](https://i.sstatic.net/GhMNp.png)](https://i.sstatic.net/GhMNp.png)

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

[![image2](https://i.sstatic.net/idwor.png)](https://i.sstatic.net/idwor.png)

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


---

### Answer by username_1 on 2016-05-31. Score: 1

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


---

### Answer by username_4 on 2018-04-18. Score: 0

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.


---

