<p>I was looking into the ear-clipping algorithm for triangulating simple polygons. I have successfully implemented it on planar polygons. However if polygon is non-planar the algorithm breaks down. Specifically one step of the algorithm is to test if there're any polygon vertices inside each ear. However point triangle test only makes sense if the point lies in the same plane as the triangle.</p>
<p>So does ear-clipping algorithm not work for non-planar polygons? If so what algorithm could I use instead? I need it to support simple polygons with potentially holes inside them.</p>

CC BY-SA 4.0
2020-09-22T18:22:47.090Z
Have you tried calculating an average normal for the polygon, and projecting the whole thing onto that?
Nathan Reed
CC BY-SA 4.0
2020-09-23T08:35:06.080Z
How can you clip off a triangle, with a straight edge, when such an edge is extremely unlikely to lie in the "surface" (however you decide to define it) of the non-planar polygon?  For example, if you take the simple case of a non-planar quad, the 'obvious' surface to define is a bilinear one and the diagonals are not straight lines - they are quadratics (e.g. https://blog.demofox.org/2018/04/23/taking-a-stroll-between-the-pixels/ ) .   Furthermore, you could bend the surface so much that it self-intersects!
Simon F
CC BY-SA 4.0
2020-09-24T04:52:13.563Z
@NathanReed Is it mathematically rigorous approach?
Lenny White
CC BY-SA 4.0
2020-09-24T16:49:01.223Z
@LennyWhite no, but then an arbitrary non-planar polygon isn't even mathematically rigorously defined as to what the actual surface is.
Nathan Reed
<computational-geometry><triangulation>
Ear-clipping algorithm for non-planar polygons
Lenny White
# Ear-clipping algorithm for non-planar polygons

(Asked by: username_0 on 2020-09-22)

I was looking into the ear-clipping algorithm for triangulating simple polygons. I have successfully implemented it on planar polygons. However if polygon is non-planar the algorithm breaks down. Specifically one step of the algorithm is to test if there're any polygon vertices inside each ear. However point triangle test only makes sense if the point lies in the same plane as the triangle.

So does ear-clipping algorithm not work for non-planar polygons? If so what algorithm could I use instead? I need it to support simple polygons with potentially holes inside them.

**Tags:** computational-geometry, triangulation

> **Comments:**
> **username_1**: Have you tried calculating an average normal for the polygon, and projecting the whole thing onto that?  
> **username_2**: How can you clip off a triangle, with a straight edge, when such an edge is extremely unlikely to lie in the "surface" (however you decide to define it) of the non-planar polygon?  For example, if you take the simple case of a non-planar quad, the 'obvious' surface to define is a bilinear one and the diagonals are not straight lines - they are quadratics (e.g. https://blog.demofox.org/2018/04/23/taking-a-stroll-between-the-pixels/ ) .   Furthermore, you could bend the surface so much that it self-intersects!  
> **username_0**: @username_1 Is it mathematically rigorous approach?  
> **username_1**: @username_0 no, but then an arbitrary non-planar polygon isn't even mathematically rigorously defined as to what the actual surface is.  

---

## 0 answers

