Having trouble with ear clipping

Question

The problem I have is coming up because I can't identify a a caved in triangle vs an ear that should actually be chopped off.

How can I tell the difference between a convex and a concave triangle?

Answer 1

Triangles can't be concave. Do you mean that your mesh is concave?

---

I hadn't realized that you were talking about a particular technique. After doing a little research, I think I understand your problem enough to attempt an answer.

Suppose you are traversing your polygon's vertices in a counterclockwise order. If we traverse them in this order, the polygon's body will always be on the left. We are considering three vertices: A, B, and C. Imagine that we shoot a ray out from A through B. If C is to the left of that ray, then this is a well-formed triangle that is part of the polygon. If C is to the right of that ray, then it represents negative space.

OK, so let's create vectors v (which is A → B) and w (which is B → C). Also, let's construct v', which is v but rotated 90 degrees CCW. v' = < -v[y], v[x] >

In order to find out whether C is to the left or right of v, we simply need to measure the angle between v' and w. If it's within (0, 90) or (270, 360), then it's to the left. If it's within (90, 270), then it's to the right. This is handy because this corresponds exactly to where cos(Θ) > 0 and where cos(Θ) < 0, respectively. So, if cos(Θ) > 0, then C is to the left, and if cos(Θ) < 0, then C is to the right.

We can use dot products to help us determine cos(Θ). Remember that cos(Θ) = (v' • w) / (mag(v') ⋅ mag(w)). However, we don't actually need cos(Θ), we only need sign(cos(Θ)). Since mag(v') and mag(w) must both be positive, we can ignore them. Therefore, if v' • w > 0, then C is to the left and the three points correspond to a triangle that is part of the polygon. On the other hand, if v' • w < 0, then C is to the right and the three points correspond to negative space outside the polygon.

I haven't actually tried this beyond simple tests, but I believe that it (or something close to it) will work.

Oh, and for others who (like me) had never heard of this technique, you can read about it here.