以下のプログラムは、x座標の小さい順に整列された点（このプログラムは文字数の関係で省略）を結び、三角形で分割するプログラムです。
質問なんですが、プログラム冒頭の構造体Inを定義し、辺を表す構造体のメンバとして保持しています。そして辺構造体の配列でキューを構成して、辺から端点を参照し、正しく凸方の三角形分割に分割できるようにしようとしたのですが、それでは不十分らしく、その下に書いてあるように、「辺から隣の辺」「辺から三角形」「点から辺」も参照できなければいけません。（一応この定義だけはしました）
この後どうすればよいでしょうか。文字数の関係でうまく説明できなくすみません。回答よろしくお願いします。
-------------------------------------
#include <stdio.h>
#include <stdlib.h>
typedef struct In{
int vs; /*始点のｘｙインデクス*/
int ve; /*終点のｘｙインデクス*/
} LINE_V;
typedef struct In2{
int lscw; /*始点のclockwise line*/
int lecw; /*終点のclockwise line*/
int lscc; /*始点のcounter clockwise line*/
int lecc; /*終点のcounter clockwise line*/
} LINE_L;
typedef struct In3{
int lt; /* left triangle */
int rt; /* right triangle */
} LINE_T;
typedef struct In4{
int lt; /* any line from the vertex */
} VTX_L;
double x[100],y[100];
int nxy; //頂点の数
LINE_V *sgln;//辺のキュー
int msg=100; //キューの寸法
int nsg=0; //辺の数
void makepoints(int *nxy,double *x,double *y);
LINE_V *enqueseg(int vs,int ve);
int tdet(int a1, int b1, int c1, int a2, int b2, int c2, int a3, int b3, int c3){
int retvalp, retvaln;
retvalp = a1*b2*c3+a2*b3*c1+a3*b1*c2;
retvaln = a1*b3*c2+a2*b1*c3+a3*b2*c1;
return retvalp-retvaln;
}
int leftside(int vertex1, int vertex2, int vertex3){
int a1, b1, c1, a2, b2, c2, a3, b3, c3;
a1 = 1.0 ; b1 = x[vertex1]; c1 = y[vertex1];
a2 = 1.0 ; b2 = x[vertex2]; c2 = y[vertex2];
a3 = 1.0 ; b3 = x[vertex3]; c3 = y[vertex3];
return tdet(a1, b1, c1, a2, b2, c2, a3, b3, c3);
}
int main()
{int v0=0,v1=1,v2=2;
int vnxt;
makepoints(&nxy, x, y);
//辺のキューを初期確保
sgln=(LINE_V*)malloc(sizeof(LINE_V)*msg);
/* 三角形の頂点の組を表示 */
printf("Triangle 1 : %d %d %d\n,v0,v1,v2 ");
//辺をキューに登録
sgln[0].vs = v0; sgln[0].ve = v1;
sgln[1].vs = v1; sgln[1].ve = v2;
sgln[2].vs = v2; sgln[2].ve = v0;
nsg = 3;
/* 各頂点の処理 */
for(vnxt=3;vnxt<nxy;vnxt++){
double m,k;
int side1,side2;
/* 傾きが極端に大きくなったときに計算誤差が発生。これが起こらないよう、傾きが1を境に処理をxとyで入れ替える*/
side1=leftside(v1, v2, v0);
side2=leftside(v1, v2, vnxt);
/* 判別結果によって次の三角形の頂点を
選択 */
if(side1^side2)
{v0=v1; /* 排他的論理和を使って判別。side1/side2のいずれか一方のみが非0のとき条件成立 */
}
/* else節はなくても一緒なので略す
else{
triangle[0]=triangle[0];
}
*/
v1=v2; v2=vnxt;
/* 三角形の頂点の組を表示 */
printf("Triangle_%d_:_%d_%d_%d\n",vnxt-1,v0,v1,v2);
//３辺を追加登録
sgln = enqueseg(v0,v1);
sgln = enqueseg(v1,v2);
sgln = enqueseg(v2,v0);
}
LINE_V *enqueseg(int vs,int ve){
int k;
int hit;
int va,vb;
//キューの拡張：倍々サイズ
if(nsg==msg){
msg *= 2;
sgln=(LINE_V*)realloc(sgln,sizeof(LINE_V)*msg);
if(sgln==NULL){
//エラーメッセージと、exit(0);
}
}
//重複登録チェック
for(k=0;k<nsg;k++){
va = sgln[k].vs;
vb = sgln[k].ve;
hit = (va==vs&&vb==ve)||(va==ve&&vb==vs);
if(hit) break;
}
//重複なし：新規登録
if(k==nsg){
sgln[nsg].vs = vs;
sgln[nsg].ve = ve;
nsg++;
}
return sgln;
}
お礼
情報不足でしたね。すみませんでした。