2D polygon triangulation
Posted
by logank9
on Stack Overflow
See other posts from Stack Overflow
or by logank9
Published on 2010-05-30T15:23:39Z
Indexed on
2010/05/30
15:32 UTC
Read the original article
Hit count: 371
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 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;
}
© Stack Overflow or respective owner