триангуляции Делоне в C++

Question

Следующие шаги предполагают, что вы начинаете с двумя точками - A & B - и пытаются определить точку С, чтобы быть использованы для формирования треугольника:

а. Создайте функцию-член, которая определит, находится ли данная точка C слева или справа от линии, образованной двумя точками A и B. Подсказка: для этого возьмите поперечное произведение вектора между двумя точками A и B и вектор между A и C. Поскольку поперечное произведение пропорционально синусу угла между двумя векторами, оно будет положительным значением для угла между 0 и 180 градусами (т. е. если точка C находится слева от линии От а до б).

b. Создайте функцию-член, которая определит, находится ли данная точка внутри круга, образованного тремя другими точками (в этом случае три точки будут точками треугольника, а результирующий круг будет окружностью). Подсказка: очень элегантная реализация этой функции можно найти в записи Википедии для триангуляции Делане. Если вы займете этой реализации, обязательно тщательно протестируйте ее, обратитесь к ней и объясните, как она работает в вашем лабораторном отчете.

c. Создайте функцию-член, которая, учитывая две точки, найдет точку для следующего треугольника Delaunay . Эта функция может искать весь список (не самая эффективная реализация, , но достаточная для этой лаборатории) и, скорее всего, вызовет функции, определенные в 4a и 4b выше.

d. Создайте рекурсивную функцию-член, Delaunay (Point A, Point 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; 
} 

// ЗАДАЧА 4а определит, будет ли данная точка с слева или справа от линии формного в двух точках а и б

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: определить, находится ли данная точка внутри cir CLE образована тремя другими точками

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: рекурсивная функция, Делоне, то звонки с 4с выше, чтобы найти следующую точку с

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; 
    } 
} 
} 

Answer 1

Существует отличная библиотека просто делать то, что вы хотите: http://www.vtk.org/.

Answer 2

Поскольку я выполняю это же задание для ENGO 333, могу вам сказать, что ваша ошибка лежит в вашей функции nextDelaunay. Проверяйте каждую функцию отдельно, реализуя каждую из них, по одному за раз.