namespace CGoGN { namespace Algo { namespace Geometry { template VoronoiDiagram::VoronoiDiagram (typename PFP::MAP& m, const EdgeAttribute& p, VertexAttribute& r) : map(m), edgeCost (p), regions (r), vmReached(m) { vertexInfo = map.template addAttribute("vertexInfo"); } template VoronoiDiagram::~VoronoiDiagram () { map.removeAttribute(vertexInfo); } template void VoronoiDiagram::clear () { border.clear(); regions.setAllValues(0); border.clear(); seeds.clear(); front.clear(); vmReached.unmarkAll(); } template void VoronoiDiagram::setSeeds (const std::vector& s) { clear(); seeds = s; } template void VoronoiDiagram::setRandomSeeds (unsigned int nseeds) { clear(); srand ( time(NULL) ); unsigned int n = nseeds; while (n > 0) { // TODO : correct this random init which assumes contiguous Dart table Dart d = rand() % map.getNbDarts() ; if (! vmReached.isMarked(d)) { vmReached.mark(d); seeds.push_back(d); n--; } } } template void VoronoiDiagram::initFrontWithSeeds () { vmReached.unmarkAll(); for (unsigned int i = 0; i < seeds.size(); i++) { Dart d = seeds[i]; vmReached.mark(d); vertexInfo[d].it = front.insert(std::pair(0.0, d)); vertexInfo[d].valid = true; // vertexInfo[d].region = i; regions[d] = i; vertexInfo[d].pathOrigin = d; } } template void VoronoiDiagram::setCost (const EdgeAttribute& c){ edgeCost = c; } template void VoronoiDiagram::collectVertexFromFront(Dart e){ front.erase(vertexInfo[e].it); vertexInfo[e].valid=false; // regions[e] = vertexInfo[e].region; regions[e] = regions[vertexInfo[e].pathOrigin]; } template void VoronoiDiagram::addVertexToFront(Dart f, float d){ VertexInfo& vi (vertexInfo[f]); vi.it = front.insert(std::pair(d + edgeCost[f], f)); vi.valid=true; // vi.region = regions[map.phi2(f)]; vi.pathOrigin = map.phi2(f); vmReached.mark(f); } template void VoronoiDiagram::updateVertexInFront(Dart f, float d){ VertexInfo& vi (vertexInfo[f]); float dist = d + edgeCost[f]; if (dist < vi.it->first) { front.erase(vi.it); vi.it = front.insert(std::pair(dist, f)); // vi.region = regions[map.phi2(f)]; vi.pathOrigin = map.phi2(f); } } template void VoronoiDiagram::computeDiagram () { initFrontWithSeeds(); while ( !front.empty() ) { Dart e = front.begin()->second; float d = front.begin()->first; collectVertexFromFront(e); Traversor2VVaE tv (map, e); for (Dart f = tv.begin(); f != tv.end(); f=tv.next()) { if (vmReached.isMarked(f)) { // f has been reached if (vertexInfo[f].valid) // f is in the front : update updateVertexInFront(f,d); else // f is not in the front any more (already collected) : detect a border edge if ( regions[f] != regions[e] ) border.push_back(f); } else { // f has not been reached : add it to the front addVertexToFront(f,d); } } } } }// end namespace Geometry }// end namespace Algo }// end namespace CGoGN