Библиотека Fade Соседи участка триангуляции Делоне

В триангуляции Делоне с использованием библиотеки Fade можно посетить треугольник инцидента сайту и посетить его соседей, как описано здесь: http://www.geom.at/example2-traversing/

Я не мог понять, как обойти сайты-соседи, используя инцидентный треугольник и его соседей. Какого соседа по треугольнику я должен посетить на каждой итерации, чтобы выполнить это?

В приведенном ниже примере основной сайт находится в синем кружке, и я хочу сохранить все соседние сайты в красных кружках в некотором массиве. .

пример


c++ voronoi delaunay
person Jack    schedule 01.05.2017    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я автор 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();
person Geom    schedule 29.07.2017
comment
Большое спасибо за ответ. Я получил эту ошибку: идентификатор incIndexBy1 не найден. Не могли бы вы помочь мне решить эту проблему. - person Jack; 29.07.2017
comment
Извините: incIndexBy1(idx) — небольшой помощник из моей среды. При вызове с idx он возвращает (idx+1)%3, поэтому incIndexBy1(0)=1, incIndexBy1(1)=2 и incIndexBy1(2)=0. - person Geom; 29.07.2017
comment
Спасибо! Я только что заметил, что если точка является граничной, первый сосед пропускается: ibb.co/ih5n0Q - person Jack; 30.07.2017
comment
Да, демонстрационный код предполагал внутреннюю вершину. Я отредактировал код прямо сейчас, и теперь он работает и для граничных вершин. - person Geom; 30.07.2017

arrow_upward
0
arrow_downward

Этот код дает правильный вывод для этого примера, но я не думаю, что это эффективный способ сделать это. Я считаю, что это было бы очень медленно для очень большого количества сайтов.

#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;
}
person Jack    schedule 02.05.2017
comment
Это поздний ответ, извините: вам не нужно перебирать vAllPoints, чтобы найти $currentPoint, потому что указатели вершин в vDelaunayVertexPointers и входные точки в vInputPoints имеют одинаковый порядок. Пусть пользовательские индексы начинаются с 0. Затем вы можете использовать vDelaunayVertexPointers[pointToCheck], чтобы быстро найти $currentPoint за время O(1). Кроме того, использование TriangleAroundVertexIterator намного проще и позволяет избежать большинства строк кода. - person Geom; 07.07.2021