namespace CGoGN { namespace Algo { namespace Geometry { /*********************************************************** * class VoronoiDiagram ***********************************************************/ 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; regions[d] = i; vertexInfo[d].pathOrigin = d; } } template void VoronoiDiagram::setCost (const EdgeAttribute& c){ edgeCost = c; } template void VoronoiDiagram::collectVertexFromFront(Dart e){ regions[e] = regions[vertexInfo[e].pathOrigin]; front.erase(vertexInfo[e].it); vertexInfo[e].valid=false; } 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.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.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); } } } } /*********************************************************** * class CentroidalVoronoiDiagram ***********************************************************/ template CentroidalVoronoiDiagram::CentroidalVoronoiDiagram (typename PFP::MAP& m, const EdgeAttribute& c, VertexAttribute& r, VertexAttribute& d, VertexAttribute& o) : VoronoiDiagram(m,c,r), distances(d), pathOrigins(o) { } template CentroidalVoronoiDiagram::~CentroidalVoronoiDiagram () { } template void CentroidalVoronoiDiagram::clear () { VoronoiDiagram::clear(); distances.setAllValues(0.0); } template void CentroidalVoronoiDiagram::collectVertexFromFront(Dart e){ distances[e] = this->vertexInfo[e].it->first; pathOrigins[e] = this->vertexInfo[e].pathOrigin; VoronoiDiagram::collectVertexFromFront(e); } }// end namespace Geometry }// end namespace Algo }// end namespace CGoGN