Вопрос:
Следующие шаги предполагают, что вы начинаете с двух точек – A & B – и пытаетесь определить точку C, которая будет использоваться для формирования треугольника:
а. Создайте функцию-член, которая определит, находится ли данная точка C слева или справа от линии, образованной двумя точками A и B. Подсказка: для этого возьмите поперечное произведение вектора между двумя точками A и B и вектором между A и C. Поскольку поперечное произведение пропорционально синусу угла между двумя векторами, оно будет положительным значением для угла между 0 и 180 градусами (т.е. если точка C находится слева от линии из A к B).
б. Создайте функцию-член, которая определит, находится ли данная точка внутри круга, образованного тремя другими точками (в этом случае три точки будут точками треугольника, а результирующий круг будет окружностью). Подсказка: очень элегантная реализация этой функции можно найти в записи Википедии для триангуляции Делоне. Если вы заимствуете эту реализацию, обязательно тщательно протестируйте ее, обратитесь к ней и объясните, как она работает в вашем лабораторном отчете.
с. Создайте функцию-член, которая, учитывая две точки, найдет точку для следующего треугольника Делоне. Эта функция может искать весь список (не самая эффективная реализация, но достаточная для этой лаборатории) и, скорее всего, вызовет функции, определенные в 4a и 4b выше.
д. Создайте рекурсивную функцию-член, Delaunay (точка A, точка B), которая вызывает функцию из 4c над поиском следующей точки C. Когда точка C найдена, эта функция должна вставить новый треугольник в вектор треугольника, а также обновить Булева переменная в списке точек. Затем эта функция должна рекурсивно называть себя с использованием точек A и C и снова использовать точки C и B. Убедитесь, что функция также имеет два базовых варианта; один, когда найденная точка 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 слева или справа от формы линии двумя точками 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: определить, находится ли данная точка внутри круга, образованная тремя другими точками
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: учитывая две точки, находит точку для следующего треугольника Делоне
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, вызовы из 4c выше, чтобы найти следующую точку C
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; } } } Ответ №1
Поскольку я выполняю это же задание для ENGO 333, я могу сказать, что ваша ошибка лежит в вашей nextDelaunay функции nextDelaunay. Проверяйте каждую функцию отдельно, реализуя каждую из них, по одному за раз.
Ответ №2
Существует отличная библиотека, которая просто делает то, что вам нужно: http://www.vtk.org/.
