voronoiDiagrams.hpp 4.22 KB
 Basile Sauvage committed Aug 08, 2012 1 2 3 4 5 6 7 8 9 ``````namespace CGoGN { namespace Algo { namespace Geometry { `````` Basile Sauvage committed Sep 05, 2012 10 11 12 13 ``````/*********************************************************** * class VoronoiDiagram ***********************************************************/ `````` Basile Sauvage committed Aug 08, 2012 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 69 70 71 72 ``````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 73 74 75 ``````// vertexInfo[d].region = i; regions[d] = i; vertexInfo[d].pathOrigin = d; `````` Basile Sauvage committed Aug 08, 2012 76 77 78 79 80 81 82 83 `````` } } template void VoronoiDiagram::setCost (const EdgeAttribute& c){ edgeCost = c; } `````` Basile Sauvage committed Sep 05, 2012 84 85 86 87 ``````template void VoronoiDiagram::collectVertexFromFront(Dart e){ // regions[e] = vertexInfo[e].region; regions[e] = regions[vertexInfo[e].pathOrigin]; `````` Basile Sauvage committed Sep 05, 2012 88 89 `````` front.erase(vertexInfo[e].it); vertexInfo[e].valid=false; `````` Basile Sauvage committed Sep 05, 2012 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 ``````} 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 114 115 116 117 118 119 120 121 122 123 `````` template void VoronoiDiagram::computeDiagram () { initFrontWithSeeds(); while ( !front.empty() ) { Dart e = front.begin()->second; float d = front.begin()->first; `````` Basile Sauvage committed Sep 05, 2012 124 125 `````` collectVertexFromFront(e); `````` Basile Sauvage committed Aug 08, 2012 126 127 128 129 130 `````` 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 131 132 133 134 135 `````` { // 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 136 137 `````` } else `````` Basile Sauvage committed Sep 05, 2012 138 139 `````` { // f has not been reached : add it to the front addVertexToFront(f,d); `````` Basile Sauvage committed Aug 08, 2012 140 141 142 143 144 `````` } } } } `````` Basile Sauvage committed Sep 05, 2012 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 ``````/*********************************************************** * 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); } `````` Basile Sauvage committed Aug 08, 2012 176 177 178 ``````}// end namespace Geometry }// end namespace Algo }// end namespace CGoGN``````