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; } } template void VoronoiDiagram::setCost (const EdgeAttribute& c){ edgeCost = c; } template void VoronoiDiagram::computeDiagram () { initFrontWithSeeds(); while ( !front.empty() ) { Dart e = front.begin()->second; float d = front.begin()->first; front.erase(vertexInfo[e].it); vertexInfo[e].valid=false; regions[e] = vertexInfo[e].region; Traversor2VVaE tv (map, e); for (Dart f = tv.begin(); f != tv.end(); f=tv.next()) { VertexInfo& vi (vertexInfo[f]); if (vmReached.isMarked(f)) { if (vi.valid) // probably useless (because of distance test) but faster { // float dist = d + Algo::Geometry::edgeLength(map,f,position); 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[e]; } } else { if ( regions[f] != regions[e] ) border.push_back(f); } } else { // vi.it = front.insert(std::pair(d + Algo::Geometry::edgeLength(map,f,position), f)); vi.it = front.insert(std::pair(d + edgeCost[f], f)); vi.valid=true; vi.region = regions[e]; vmReached.mark(f); } } } } }// end namespace Geometry }// end namespace Algo }// end namespace CGoGN