I'm trying to write a program that will take a polygon, and convert it into triangles. I have the algorithm worked out, and i have it coded, but im having some problems compiling it to start debugging, and it's because of a dynamic struct array.
Basically, its an array called triangles, which holds x1,x2,x3,y1,y2, and y3. The problem seems to be when i put in triangles[], to delete the array or find the size. I have no clue what im doing wrong here, because im a newbie to c++. Im gonna post up the entire program because it needs a looking over from someone who knows what they're doing anyways.
#include <cmath>
#include <string>
#include <string.h>
#include "DarkGDK.h"
using namespace std;
struct vec
{
float x;
float y;
bool resolved;
};
struct tri
{
float x1;
float x2;
float x3;
float y1;
float y2;
float y3;
};
struct poly
{
float x;
float y;
float x2;
float y2;
};
bool same_side (vec p1, vec p2, vec l1, vec l2);
bool inside(vec p, vec a,vec b,vec c);
int wrapvalue(int min, int max, int val);
tri* addmem(int addmem);
int wrapvalue2(int min,int max, int val);
void update_tris(void);
int leftmostvertice();
bool same_side (vec p1, vec p2, vec l1, vec l2);
bool inside(vec p, vec a,vec b,vec c) ;
void display(void);
int a;
float area(void);
int triangle_num;
int size;
int trinum;
poly polygon;
vec verts[15];
tri* triangles=new tri[1];
bool exclude[15];
void DarkGDK (void)
{
for(int a=1; a<=15; a++)
{
// 1/15th of 360 degrees in radians
float temp=(44*a)/(7*15);
verts[a].x=cos(temp)*40;
verts[a].y=sin(temp)*40;
}
while(LoopGDK())
{
update_tris();
display();
dbSync();
}
}
void update_tris(void)
{
for(a=0;a<=14;a++)
{exclude[a]=0;}
trinum=0;
bool triangles_left=1;
while(triangles_left)
{
trinum++;
delete triangles[];
tri* triangles=new tri[1];
int verta=leftmostvertice();//the leftmost vert
//find the two adjacent non excluded verts to verta
int vertb=wrapvalue(0,14,verta+1);
while (exclude[vertb])
{vertb=wrapvalue(0,14,vertb+1);};
int vertc=wrapvalue(0,15,verta-1);
while (exclude[vertc])
{vertb=wrapvalue(0,14,vertc-1);}
//if any of the verts are the same, then there are only 2 points left, which means all triangles are made
if ((vertb==vertc)||(vertc==verta)||(verta==vertc))
{
triangles_left=0;
break;
}
bool tru=0;//if tru=1 then there is a vert inside the given triangle
while (1)
{
//check if there are other verts in triangle verta,vertb,vertc
for(int a=1;a<=12;a++)
{
int b=wrapvalue(0,14,a+vertb);
tru=inside(verts[b],verts[verta],verts[vertb],verts[vertc]);
if (tru) break;
}
if(!tru) break;
vertb++;
while(exclude[vertb])
{vertb++;}
}
triangles=addmem(sizeof(tri));
int index=sizeof(triangles[])/sizeof(tri);
triangles[index].x1=verts[verta].x;
triangles[index].x2=verts[vertb].x;
triangles[index].x3=verts[vertc].x;
triangles[index].y1=verts[verta].y;
triangles[index].y2=verts[vertb].y;
triangles[index].y3=verts[vertc].y;
}
}
/*
float area(void)
{
float temp;
for (a=0;a<=trianglenum-1;a++)
{
float a=triangles[a].x1;
float b=triangles[a].x2;
float c=triangles[a].x3;
float x=triangles[a].y1;
float y=triangles[a].y2;
float z=triangles[a].y3;
temp = temp+1/2(-b*x+c*x+a*y-c*y-a*z+b*z);
}
return temp;
}
*/
int wrapvalue(int min,int max, int val)
{
int temp=val;
//wrapvalue where max+1=min and min-1=max
if(val<min)
{
temp=max+(val+1-min)%(max-min);
}
if(val>max)
{
temp=min+(val-1-min)%(max-min);
}
return temp;
}
int wrapvalue2(int min,int max, int val)
{
int temp=val;
//wrapvalue where max=min
if(val<min)
{
temp=(val-min)%(max-min)+max;
}
if(val>max)
{
temp=(val-min)%(max-min)+min;
}
return temp;
}
int leftmostvertice()
{
//this function will return the leftmost vertice that hasn't already been returned
bool* exclude=new bool[15];
float temp1;
int temp2;
temp2=0;
temp1=verts[0].x;
temp2=0;
for(int a=0;a<=14;a++)
{
if((temp1>verts[a].x) && (exclude[a]==0))
{
temp1=verts[a].x;
temp2=a;
}
}
exclude[temp2]=1;
return temp2;
}
tri* addmem(int addmem)
{
tri* temp = new tri[sizeof(triangles[])+addmem];
memcpy(temp,triangles[],sizeof(triangles[]));
delete triangles[];
return temp;
}
bool same_side (vec p1, vec p2, vec l1, vec l2)
{
bool same_side=((p1.x-l1.x)*(l2.y-l1.y)-(l2.x-l1.x)*(p1.y-l1.y))*((p2.x-l1.x)*(l2.y-l1.y)-(l2.x-l1.x)*(p2.y-l1.y))>0;
return same_side;
}
bool inside(vec p, vec a,vec b,vec c)
{
bool inside = same_side(p, a, b, c) & same_side(p, b, a,c) & same_side(p, c, a, b);
}
void display(void)
{
//draw each triangle in green
dbInk(dbRGB(0,255,0),dbRGB(0,255,0));
for (a=0;a<=trinum-1;a++)
{
dbLine(triangles[a].x1,triangles[a].y1,triangles[a].x2,triangles[a].y2);
dbLine(triangles[a].x1,triangles[a].y1,triangles[a].x3,triangles[a].y3);
dbLine(triangles[a].x2,triangles[a].y2,triangles[a].x3,triangles[a].y3);
}
//draw the outline of the polygon in white, and circles in blue
for(a=0;a<=14;a++)
{
dbInk(dbRGB(255,255,255),dbRGB(255,255,255));
dbLine(verts[a].x,verts[a].y,verts[wrapvalue(0,14,a+1)].x,verts[wrapvalue(0,14,a+1)].y);
dbInk(dbRGB(0,0,255),dbRGB(0,0,255));
dbCircle(verts[a].x,verts[a].y,5);
}
}
In case you wanna know how the algorithm works (for clarity or interest), here it is:
Excluded vertices are red, the current vertices are green, the tris are green, and the polygon is black. Heres how it works:
1. find the leftmost vertex
2. find the two adjacent, non excluded vertices
3. create a triangle
4. find the next leftmost vertex
5. find the two adjacent, non excluded vertices
6. create a triangle
7. repeat
Also, this is only the second usable program i've written in c++, so if theres anything stupid im doing, any bad habits im forming, or anything else, please tell me!
