2D полигональная триангуляция

Question

Код ниже - моя попытка триангуляции. Он выводит неправильные углы (он читает углы квадрата как 90, 90. 90, 176) и рисует неправильные формы. Что я делаю не так?

//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;
}

Извините, я не знаю, почему первые несколько строк не считаются кодом.

Answer 1

Вы неправильно оцениваете углы.

Посмотрите на фрагмент из своего кода и на эту картинку.

На картинке две разные ситуации. Первая, когда многоугольник находится над точками P1, P2, P3 (тогда угол = 135 градусов), и вторая ситуация, когда он находится под этими точками (тогда угол = 225 градусов), но ваш код оценит тот же угол в обеих ситуациях.

    //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);

альтернативный текст http://www.freeimagehosting.net/uploads/28a3a66573.png

Answer 2

Вам нужно уменьшить p3, если это> = poly.size (), а не просто>.

Редактировать: код Python для проверки

#!/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

И запустить его:

$ ./tmp.py 
90.0
90.0
90.0
-270.0