2D polygon triangulation

Question

The code below is my attempt at triangulation. It outputs the wrong angles (it read a square's angles as 90, 90. 90, 176) and draws the wrong shapes. What am I doing wrong?

//use earclipping to generate a list of triangles to draw
std::vector<vec> calcTriDraw(std::vector<vec> poly)
{
    std::vector<double> polyAngles;
    //get angles
    for(unsigned int i = 0;i < poly.size();i++)
    {

        int p1 = i - 1;
        int p2 = i;
        int p3 = i + 1;

        if(p3 > int(poly.size()))
            p3 -= poly.size();
        if(p1 < 0)
            p1 += poly.size();

        //get the angle of from 3 points
        double dx, dy;
        dx = poly[p2].x - poly[p1].x;
        dy = poly[p2].y - poly[p1].y;
        double a = atan2(dy,dx);

        dx = poly[p3].x - poly[p2].x;
        dy = poly[p3].y - poly[p2].y;
        double b = atan2(dy,dx);
        polyAngles.push_back((a-b)*180/PI);
    }
    std::vector<vec> triList;
    for(unsigned int i = 0;i < poly.size() && poly.size() > 2;i++)
    {
        int p1 = i - 1;
        int p2 = i;
        int p3 = i + 1;

        if(p3 > int(poly.size()))
            p3 -= poly.size();
        if(p1 < 0)
            p1 += poly.size();

        if(polyAngles[p2] >= 180)
        {
            continue;
        }
        else
        {
            triList.push_back(poly[p1]);
            triList.push_back(poly[p2]);
            triList.push_back(poly[p3]);
            poly.erase(poly.begin()+p2);
            std::vector<vec> add = calcTriDraw(poly);
            triList.insert(triList.end(), add.begin(), add.end());
            break;
        }
    }

    return triList;
}

Sorry, I don't know why the first few lines aren't getting counted as code.

Answer 1

You need to reduce p3 if it is >= poly.size(), not just >.

Edit: python code to test

#!/usr/bin/python
import math
p = ((0,0),(0,1),(1,1),(1,0))
for i in xrange(4):
   p1 = (i + 3) % 4
   p2 = i
   p3 = (i + 1) % 4
   a = math.atan2(p[p2][1] - p[p1][1], p[p2][0] - p[p1][0])
   b = math.atan2(p[p3][1] - p[p2][1], p[p3][0] - p[p2][0])
   print (a-b)*180/math.pi

And to run it:

$ ./tmp.py 
90.0
90.0
90.0
-270.0

Answer 2

You don't evaluate angles correctly.

Look at the snippet from your code, and to this picture.

In the picture there are two different situations. The first one, when the polygon is above the points P1, P2, P3 (then angle = 135 degrees), and the second situation when it is under these points (then angle = 225 degrees), but your code will evaluate the same angle in both situations.

    //get the angle of from 3 points
    double dx, dy;
    dx = poly[p2].x - poly[p1].x;
    dy = poly[p2].y - poly[p1].y;
    double a = atan2(dy,dx);

    dx = poly[p3].x - poly[p2].x;
    dy = poly[p3].y - poly[p2].y;
    double b = atan2(dy,dx);
    polyAngles.push_back((a-b)*180/PI);