Исчезать библиотека Делоне Триангуляция сайта соседей
В триангуляции Делоне с использованием библиотеки Fade можно посетить инцидентный треугольник и посетить его соседей, как описано здесь: http://www.geom.at/example2-traversing/
Я не мог понять, как пройти сайт соседних сайтов, используя инцидентный треугольник и его соседей. Какой сосед треугольника я должен посетить на каждой итерации, чтобы выполнить это?
В приведенном ниже примере основной сайт находится в синем круге, и я хочу сохранить все соседние сайты в красных кружках в некотором массиве. ,
Решение
Я автор 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();
Другие решения
Этот код дает правильный вывод для этот пример но я не думаю, что это эффективный способ сделать это. Я считаю, что это будет очень медленно для очень большого количества сайтов.
#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 filesint 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;
}
detector