Talk:Polygon Triangulation

I believe that the code in its current form is broken.

The line...

float angle = (float)Math.Acos(Vector2.Dot(Vector2.Normalize(vip1 - vi), Vector2.Normalize(vim1 - vi)));

...is wrong. From my understanding (and testing), the arc-cos of the dot-product will only ever return the smallest angle between the two vectors. This gives you no clue as to wether the point is an 'inny' or and 'outy' point. Increasing the angle from 179 degrees, to 180 degrees, to 181 degrees - in fact returns angles of 179, 180 and 179 degrees. Simply, the dot product doesn't work here.

My partial fix, is to use the following check for reflex points. It uses the cross product of the vectors, instead of the dot product. The cross product returns a vector pointing 'in' or 'out' of the 2D screen, depending on the orientation of the two vectors.

// find whether it's an inward or outward pointing vertex
 
    float x1 = vim1.X, y1 = vim1.Y;
    float x2 = vi.X,   y2 = vi.Y;
    float x3 = vip1.X, y3 = vip1.Y;
 
    float crossProductZ = (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1);
 
    // if the Z component of the cross product is negative, it's a reflex angle (i.e. the vertex points
    //   inwards.  If it equals zero, the point lies directly between the other two points.  If it's
    //   positive, the vertex points outwards.
 
    if (crossProductZ < 0) reflexPoints.Add(i);  // replaces "if (angle > MathHelper.PiOver2)"

This successfully identifies points as being reflex of otherwise, where the other method does not. My solution does however require further fixing to prevent the routine getting caught in the 'do' loop. My temporary fix is as follows:

// Place this code before the 'do' line in the Triangulate sub...
 
    int oldOLDNumOfTris = -1, oldNumOfTris = -1, currentNumOfTris = -1;

...and...

// Place this code before the 'while' line in the Triangulate sub...
 
    currentNumOfTris = points.Count;
 
    if (currentNumOfTris == oldOLDNumOfTris)
    {
        // we have a problem: invalid, self-intersecting shape.
        Console.WriteLine(" ## INVALID SHAPE ##");
        return null;
    }
    oldOLDNumOfTris = oldNumOfTris;
    oldNumOfTris = currentNumOfTris;

... but there is undoubtedly a better solution to this. I just haven't had a chance to look yet!

So does anyone agree, or disagree, or has anyone noticed the same problem?

- Tommy_g003

---

OLDER COMMENTS

---

for the reflex point checking, angle should more than Pi instand of Pi/2, is that right?

//if angle is more than PiOverTwo, it's a reflex point
if (angle > MathHelper.PiOver2)
        reflexPoints.Add(i);

SunDiver: Yes, just came to the same result after trying to fix this odd infinity loop.