次の手順では、A と B の 2 つの点から開始し、三角形を形成するために使用する点 C を決定しようとしていると想定しています。
を。指定された点 C が 2 つの点 A と B によって形成される線の左または右にあるかどうかを判断するメンバー関数を作成します。ヒント: これを行うには、2 つの点 A と B の間のベクトルとベクトルの外積をとります。外積は 2 つのベクトル間の角度の正弦に比例するため、0 ～ 180 度の角度の正の値になります (つまり、点 C が A からの線の左側にある場合)。 B）に。
b. 特定の点が他の 3 つの点によって形成される円の内側にあるかどうかを判断するメンバー関数を作成します (この場合、3 つの点は三角形の点になり、結果の円は外接円になります)。ヒント: この関数の非常に洗練された実装は、ウィキペディアの Delaunay Triangulation のエントリにあります。この実装を借用する場合は、徹底的にテストして参照し、ラボ レポートでどのように機能するかを説明してください。
c. 2 つの点を指定して、次の Delaunay 三角形の点を見つけるメンバー関数を作成します。この関数はリスト全体を検索でき (最も効率的な実装ではありませんが、この演習では十分です)、上記の 4a および 4b で定義された関数を呼び出す可能性が高くなります。
d. 上記の 4c から関数を呼び出して次の点 C を見つける再帰メンバー関数 Delaunay(Point A, Point B) を作成します。点 C が見つかった場合、この関数は新しい三角形を三角形ベクトルに挿入し、ポイント リスト内のブール変数。次に、この関数は、ポイント A と C を使用して、さらにポイント C と B を使用して、再帰的に自身を呼び出す必要があります。関数にも 2 つの基本ケースがあることを確認してください。1 つは、C で見つかった点が既に使用されている場合です。この場合、三角形を追加する必要がありますが、再帰呼び出しは発生しません。ポイント C が見つからない別のケース (A と B がデータセットの外側のエッジを形成するため)
私はコードを完成させましたが、デバッグプロセスでエラーが発生し続けているようで、読み取り関数に絞り込んだと思うので、ここに私のコードがあります:
PointList::PointList()
{
totPt = 0;
totTri = 0;
}
void PointList::read(const char* filename)
{
FILE* file;
file = fopen ( filename, "r" );
fscanf ( file, "%d \n", &totPt);
datapoint.resize( totPt );
for ( unsigned int i=0; i < datapoint.size(); i++ )
{
fscanf ( file, " %d %lf %lf \n", &datapoint.at(i).ptnum, &datapoint.at(i).xCoord, &datapoint.at(i).yCoord );
}
}
void PointList::TriPrint()
{
cout << "# of triangles created: " << triPoint.size() << endl;
cout << "Triangle # : Vertice1 Vertice2 Vertice3" << endl;
for ( unsigned int i = 0; i < triPoint.size() ; i++)
{
cout << triPoint.at(i).triNum << " : " << triPoint.at(i).vert1.ptnum << " " << triPoint.at(i).vert2.ptnum << " " << triPoint.at(i).vert3.ptnum << endl;
}
return;
}
//TASK 4a: 与えられた点 C が 2 つの点 a と b による直線の左側か右側かを判断します
bool PointList::isRight( double a, double b, double c )
{
Point A = datapoint.at(a-1);
Point B = datapoint.at(b-1);
Point C = datapoint.at(c-1);
//Cross product of AB and AC
Point AB;
Point AC;
AB.xCoord = B.xCoord - A.xCoord;
AB.yCoord = B.yCoord - A.yCoord;
AC.xCoord = C.xCoord - A.xCoord;
AC.yCoord = C.yCoord - A.yCoord;
double det = (AB.xCoord*AC.yCoord) - (AC.xCoord*AB.yCoord);
if ( det >= 0 )
{
return true;
}
else
{
return false;
}
}
//タスク 4b: 与えられた点が他の 3 つの点によって形成される円の内側にあるかどうかを判断する
bool PointList::inCircle ( double a, double b, double c, double d )
{
bool inCirc = false;
Point A = datapoint.at(a-1);
Point B = datapoint.at(b-1);
Point C = datapoint.at(c-1);
Point D = datapoint.at(d-1);
vector <vector<double>> Matrix;
Matrix.resize(3);
for ( int i = 0; i < 3 ; i++)
{
Matrix.at(i).resize(3);
}
Matrix.at(0).at(0) = A.xCoord - D.xCoord;
Matrix.at(1).at(0) = B.xCoord - D.xCoord;
Matrix.at(2).at(0) = C.xCoord - D.xCoord;
Matrix.at(0).at(1) = A.yCoord - D.yCoord;
Matrix.at(1).at(1) = B.yCoord - D.yCoord;
Matrix.at(2).at(1) = C.yCoord - D.yCoord;
Matrix.at(0).at(2) = ((A.xCoord*A.xCoord) - (D.xCoord*D.xCoord)) + ((A.yCoord*A.yCoord) - (D.yCoord*D.yCoord));
Matrix.at(1).at(2) = ((B.xCoord*B.xCoord) - (D.xCoord*D.xCoord)) + ((B.yCoord*B.yCoord) - (D.yCoord*D.yCoord));
Matrix.at(2).at(2) = ((C.xCoord*C.xCoord) - (D.xCoord*D.xCoord)) + ((C.yCoord*C.yCoord) - (D.yCoord*D.yCoord));
double det = 0;
det = (Matrix.at(0).at(0) * Matrix.at(1).at(1) * Matrix.at(2).at(2)) + (Matrix.at(0).at(1) * Matrix.at(1).at(2) * Matrix.at(2).at(0)) + (Matrix.at(0).at(2) * Matrix.at(1).at(0) * Matrix.at(2).at(1));
det = det - (Matrix.at(2).at(0) * Matrix.at(1).at(1) * Matrix.at(0).at(2)) - (Matrix.at(2).at(1) * Matrix.at(1).at(2) * Matrix.at(0).at(0)) - (Matrix.at(2).at(2) * Matrix.at(1).at(0) * Matrix.at(0).at(1));
if ( det >= 0 ) // determinant is positive if and only if D lies inside the circumcircle
{
inCirc = false;
}
else
{
inCirc = true;
}
return inCirc;
}
//タスク 4c: 与えられた 2 つの点から、次のドローネ三角形の点を見つけます
double PointList::nextDelaunay ( double a, double b )
{
bool incircle = false;
bool isright = false;
bool noRight = false;
int f = -1;
//check all points in file
for ( int i = 0; i < datapoint.size() ; i++)
{
if ( i == a || i == b)
{
continue;
}
else
{
isright = isRight( a, b, i); //checks to see if its to the right
if(isright)
{
noRight = false;
for ( int j = 1; j < datapoint.size(); j++ )
{
if ( j == a || j == b || j == i )
{
continue;
}
else
{
incircle = inCircle ( a, b, i, j );
//checks to see if point in circle
if(incircle)
{
break;
}
}
}
if ( !incircle)
{
return i;
}
}
else
{
continue;
}
}
}
if (noRight)
{
return f;
}
}
//タスク 4d: 再帰メンバー関数 Delaunay、次のポイント C を見つけるための上記の 4c からの呼び出し
void PointList::Delaunay( int a, int b )
{
Triangle x;
Point A = datapoint.at(a - 1);
Point B = datapoint.at(b - 1);
int c = nextDelaunay(a,b);
if ( c == -1)
{
return;
}
else
{
Point C = datapoint.at(c-1);
if ( C.usedPt == false)
{
x.vert1.ptnum = a;
x.vert1.xCoord = A.xCoord;
x.vert1.yCoord = A.yCoord;
x.vert2.ptnum = b;
x.vert2.xCoord = B.xCoord;
x.vert2.yCoord = B.yCoord;
x.vert3.ptnum = c;
x.vert3.xCoord = C.xCoord;
x.vert3.yCoord = C.yCoord;
x.triNum = triPoint.size()+1;
triPoint.push_back(x);
datapoint.at(c-1).usedPt = true;
Delaunay( a, c );
Delaunay( c, b );
return;
}
if ( C.usedPt == true )
{
x.vert1.ptnum = a;
x.vert1.xCoord = A.xCoord;
x.vert1.yCoord = A.yCoord;
x.vert2.ptnum = b;
x.vert2.xCoord = B.xCoord;
x.vert2.yCoord = B.yCoord;
x.vert3.ptnum = c;
x.vert3.xCoord = C.xCoord;
x.vert3.yCoord = C.yCoord;
x.triNum = triPoint.size()+1;
triPoint.push_back(x);
return;
}
}
}