voronoiDiagrams.hpp 3.19 KB
 Basile Sauvage committed Aug 08, 2012 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 ``````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; `````` Basile Sauvage committed Sep 05, 2012 69 70 71 ``````// vertexInfo[d].region = i; regions[d] = i; vertexInfo[d].pathOrigin = d; `````` Basile Sauvage committed Aug 08, 2012 72 73 74 75 76 77 78 79 `````` } } template void VoronoiDiagram::setCost (const EdgeAttribute& c){ edgeCost = c; } `````` Basile Sauvage committed Sep 05, 2012 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 ``````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); } } `````` Basile Sauvage committed Aug 08, 2012 110 111 112 113 114 115 116 117 118 119 `````` template void VoronoiDiagram::computeDiagram () { initFrontWithSeeds(); while ( !front.empty() ) { Dart e = front.begin()->second; float d = front.begin()->first; `````` Basile Sauvage committed Sep 05, 2012 120 121 `````` collectVertexFromFront(e); `````` Basile Sauvage committed Aug 08, 2012 122 123 124 125 126 `````` Traversor2VVaE tv (map, e); for (Dart f = tv.begin(); f != tv.end(); f=tv.next()) { if (vmReached.isMarked(f)) `````` Basile Sauvage committed Sep 05, 2012 127 128 129 130 131 `````` { // 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); `````` Basile Sauvage committed Aug 08, 2012 132 133 `````` } else `````` Basile Sauvage committed Sep 05, 2012 134 135 `````` { // f has not been reached : add it to the front addVertexToFront(f,d); `````` Basile Sauvage committed Aug 08, 2012 136 137 138 139 140 141 142 143 `````` } } } } }// end namespace Geometry }// end namespace Algo }// end namespace CGoGN``````