淡化库 Delaunay Triangulation 站点邻居

Question

在使用 Fade 库的 Delaunay 三角剖分中，可以访问站点的事件三角形并访问其邻居，如下所述：http://www.geom.at/example2-traversing/

我不知道如何利用事件三角形及其邻居来遍历站点邻居站点。我应该在每次迭代中访问哪个三角形邻居来完成这个？

在下面的例子中，主要站点在蓝色圆圈中，我想将所有红圈中的邻居站点保存在某个数组中。 .

example

Answer 1

此代码为 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;
}

Answer 2

我是 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();

淡化库 Delaunay Triangulation 站点邻居

Fade library Delaunay Triangulation site neighbors

c++

voronoi

delaunay