페이드 라이브러리 들로네 삼각 사이트 이웃들 들로네 삼각 분할에서

Question

는 : http://www.geom.at/example2-traversing/

나는 사이트 neighbor-을 통과하는 방법을 알아낼 수 없었다 사고 삼각형과 그 이웃을 이용하여 어떤 삼각형 이웃을 방문해야이 일을 완수 할 수 있습니까?

아래 예에서 기본 사이트는 파란색 원으로 표시되어 있으며 일부 이웃 사이트를 빨간색 원으로 저장하려고합니다. .

example

Answer 1

저는 Fade2D의 저자입니다. 당신이 TriangleAroundVertexIterator 또는 Fade_2D :: getIncidentTriangles() 메서드를 사용할 때 그것은 훨씬 더 쉽게, 아래의 데모 기능을 참조 : 그것은 임의의 삼각형을 만들어 특정 지점을 추출 주변의 정점을하고 그 결과립니다

을

vector<Point2> vRandomPoints; 
generateRandomPoints(50,0,1000,vRandomPoints,1); 

Fade_2D dt; 
vector<Point2*> vVertexHandles; 
dt.insert(vRandomPoints,vVertexHandles); 

// Your point index to be checked and the corresponding pointer 
size_t pointToCheck=5; 
Point2* pVertexToCheck(vVertexHandles[pointToCheck]); 

// Fetch the incident triangles 
std::vector<Triangle2*> vIncidentTriangles; 
dt.getIncidentTriangles(pVertexToCheck,vIncidentTriangles); 

// Extract the vertices 
set<Point2*> sResultVertices; 
for(std::vector<Triangle2*>::iterator it(vIncidentTriangles.begin()); 
    it!=vIncidentTriangles.end();++it) 
{ 
    Triangle2* pIncidentT(*it); 
    int intraTriangleIndex(pIncidentT->getIntraTriangleIndex(pVertexToCheck)); 
    sResultVertices.insert(pIncidentT->getCorner((intraTriangleIndex+1)%3)); 
    sResultVertices.insert(pIncidentT->getCorner((intraTriangleIndex+2)%3)); 
} 
cout<<"number of points: "<<sResultVertices.size()<<endl; 

// Verify: Postscript Visualization 
Visualizer2 vis("result.ps"); 
dt.show(&vis,false); 
vis.addObject(Label(*pVertexToCheck,"base"),Color(CGREEN)); 
for(set<Point2*>::iterator it(sResultVertices.begin());it!=sResultVertices.end();++it) 
{ 
    vis.addObject(Label(**it,"VTX"),Color(CRED)); 
} 
vis.writeFile(); 

Answer 2

이 코드는 this example에 대한 정확한 출력을 제공하지만 난이 그것을 할 수있는 효율적인 방법입니다 생각하지 않습니다. 나는 매우 많은 수의 사이트에서 매우 느릴 것이라고 생각합니다.

#include <stdio.h> 
#include <iostream> 
#include <Fade_2D.h> 


using namespace GEOM_FADE2D; 
using namespace std; 
const int NUM_EXAMPLES(7); 

// Defined in the exampleX files 



int main() 
{ 
    int pointToCheck; 
    bool incidentResetted; 


    cout << endl; 

    std::vector<Point2> vInputPoints; 
    // Create a triangulation 
    Fade_2D dt; 

    // Create and insert 4 points 

    Point2 p1(8.3, 1); 
    Point2 p2(7.6, 8); 
    Point2 p3(7.4, 7); 
    Point2 p4(3.9, 3); 
    Point2 p5(6.5, 9.5); 
    Point2 p6(1.7, 0.4); 
    Point2 p7(7, 4.2); 
    Point2 p8(0.3, 3.9); 
    Point2 p9(2.8, 7.7); 
    Point2 p10(0.4, 8); 



    p1.setCustomIndex(1); 
    p2.setCustomIndex(2); 
    p3.setCustomIndex(3); 
    p4.setCustomIndex(4); 
    p5.setCustomIndex(5); 
    p6.setCustomIndex(6); 
    p7.setCustomIndex(7); 
    p8.setCustomIndex(8); 
    p9.setCustomIndex(9); 
    p10.setCustomIndex(10); 


    vInputPoints.push_back(p1); 
    vInputPoints.push_back(p2); 
    vInputPoints.push_back(p3); 
    vInputPoints.push_back(p4); 
    vInputPoints.push_back(p5); 
    vInputPoints.push_back(p6); 
    vInputPoints.push_back(p7); 
    vInputPoints.push_back(p8); 
    vInputPoints.push_back(p9); 
    vInputPoints.push_back(p10); 

    std::vector<Point2*> vDelaunayVertexPointers; 

    dt.insert(vInputPoints, vDelaunayVertexPointers); 



    //Draw 
    dt.show("example.ps"); 

    std::vector<Point2*> vAllPoints; 

    vAllPoints.clear(); 
    dt.getVertexPointers(vAllPoints); 




    while (true) 
    { 
     cout << "Please enter point to check: "; 
     cin >> pointToCheck; 


     for (std::vector<Point2*>::iterator it(vAllPoints.begin()); 
      it != vAllPoints.end(); ++it) 
     { 
      Point2* currentPoint(*it); 

      incidentResetted = false; 

      vector<Point2*> neighbours; 

      if (currentPoint->getCustomIndex() == pointToCheck) 
      { 
       //Print neighbours 
       Triangle2* pT(currentPoint->getIncidentTriangle()); 
       Triangle2* firstTr(currentPoint->getIncidentTriangle()); 
       Triangle2* lastcheckedTriangle; 

       lastcheckedTriangle = pT; 


       timer("INSERT"); // Start timer 

       if (pT->getCorner(0)->getCustomIndex() == currentPoint->getCustomIndex()) 
       { 
        neighbours.push_back(pT->getCorner(1)); 
        neighbours.push_back(pT->getCorner(2)); 


        if (pT->getOppositeTriangle(1) != NULL) 
         pT = pT->getOppositeTriangle(1); 
        else 
         pT = pT->getOppositeTriangle(2); 
       } 
       else if (pT->getCorner(1)->getCustomIndex() == currentPoint->getCustomIndex()) 
       { 
        neighbours.push_back(pT->getCorner(0)); 
        neighbours.push_back(pT->getCorner(2)); 


        if (pT->getOppositeTriangle(0) != NULL) 
         pT = pT->getOppositeTriangle(0); 
        else 
         pT = pT->getOppositeTriangle(2); 
       } 
       else if (pT->getCorner(2)->getCustomIndex() == currentPoint->getCustomIndex()) 
       { 
        neighbours.push_back(pT->getCorner(0)); 
        neighbours.push_back(pT->getCorner(1)); 


        if (pT->getOppositeTriangle(0) != NULL) 
         pT = pT->getOppositeTriangle(0); 
        else 
         pT = pT->getOppositeTriangle(1); 
       } 


       if (pT == NULL) 
        break; 


       while (pT != firstTr) 
       { 

        if (pT->getCorner(0)->getCustomIndex() == currentPoint->getCustomIndex()) 
        { 
         if (pT->getCorner(1)->getCustomIndex() != neighbours.back()->getCustomIndex()) 
         { 
          neighbours.push_back(pT->getCorner(1)); 
         } 
         else 
         { 
          neighbours.push_back(pT->getCorner(2)); 
         } 


         if (pT->getOppositeTriangle(1) != lastcheckedTriangle) 
         { 
          lastcheckedTriangle = pT; 
          pT = pT->getOppositeTriangle(1); 
         } 
         else 
         { 
          lastcheckedTriangle = pT; 
          pT = pT->getOppositeTriangle(2); 
         } 

        } 
        else if (pT->getCorner(1)->getCustomIndex() == currentPoint->getCustomIndex()) 
        { 
         if (pT->getCorner(0)->getCustomIndex() != neighbours.back()->getCustomIndex()) 
         { 
          neighbours.push_back(pT->getCorner(0)); 
         } 
         else 
         { 
          neighbours.push_back(pT->getCorner(2)); 
         } 


         if (pT->getOppositeTriangle(0) != lastcheckedTriangle) 
         { 
          lastcheckedTriangle = pT; 
          pT = pT->getOppositeTriangle(0); 
         } 
         else 
         { 
          lastcheckedTriangle = pT; 
          pT = pT->getOppositeTriangle(2); 
         } 
        } 
        else if (pT->getCorner(2)->getCustomIndex() == currentPoint->getCustomIndex()) 
        { 
         if (pT->getCorner(1)->getCustomIndex() != neighbours.back()->getCustomIndex()) 
         { 
          neighbours.push_back(pT->getCorner(1)); 
         } 
         else 
         { 
          neighbours.push_back(pT->getCorner(0)); 
         } 

         if (pT->getOppositeTriangle(1) != lastcheckedTriangle) 
         { 
          lastcheckedTriangle = pT; 
          pT = pT->getOppositeTriangle(1); 
         } 
         else 
         { 
          lastcheckedTriangle = pT; 
          pT = pT->getOppositeTriangle(0); 
         } 
        } 
        else 
        { 
         break; 
        } 



        //checking a case in which the currectPoint is on the boundary and the incident triangle is some in between triangle 
        if (pT == NULL) 
        { 
         if (incidentResetted) 
          break; 
         else 
         { 

          incidentResetted = true; 

          //Need to reset everything and start again from this triangle 
          neighbours.clear(); 

          currentPoint->setIncidentTriangle(lastcheckedTriangle); 

          pT = lastcheckedTriangle; 
          firstTr = pT; 


          if (pT->getCorner(0)->getCustomIndex() == currentPoint->getCustomIndex()) 
          { 
           neighbours.push_back(pT->getCorner(1)); 
           neighbours.push_back(pT->getCorner(2)); 


           if (pT->getOppositeTriangle(1) != NULL) 
            pT = pT->getOppositeTriangle(1); 
           else 
            pT = pT->getOppositeTriangle(2); 
          } 
          else if (pT->getCorner(1)->getCustomIndex() == currentPoint->getCustomIndex()) 
          { 
           neighbours.push_back(pT->getCorner(0)); 
           neighbours.push_back(pT->getCorner(2)); 


           if (pT->getOppositeTriangle(0) != NULL) 
            pT = pT->getOppositeTriangle(0); 
           else 
            pT = pT->getOppositeTriangle(2); 
          } 
          else if (pT->getCorner(2)->getCustomIndex() == currentPoint->getCustomIndex()) 
          { 
           neighbours.push_back(pT->getCorner(0)); 
           neighbours.push_back(pT->getCorner(1)); 


           if (pT->getOppositeTriangle(0) != NULL) 
            pT = pT->getOppositeTriangle(0); 
           else 
            pT = pT->getOppositeTriangle(1); 
          } 

         } 
        } 

       } 
       timer("INSERT"); // End timer 

       if (neighbours.front()->getCustomIndex() == neighbours.back()->getCustomIndex()) 
        neighbours.pop_back(); 
       cout << "Neighbour sites:\n"; 

       for (int l = 0; l < neighbours.size(); l++) 
       { 
        cout << neighbours[l]->getCustomIndex() << " | " << neighbours[l]->x() << " , " << neighbours[l]->y() << endl; 
       } 
       cout << "\n\n\n"; 

      } 

      //dt.remove(currentPoint); 
     } 
    } 
    return 0; 
}