voronoiDiagrams.hpp 4.08 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 `````` regions[d] = i; vertexInfo[d].pathOrigin = d; `````` Basile Sauvage committed Aug 08, 2012 75 76 77 78 79 80 81 82 `````` } } template void VoronoiDiagram::setCost (const EdgeAttribute& c){ edgeCost = c; } `````` Basile Sauvage committed Sep 05, 2012 83 84 85 ``````template void VoronoiDiagram::collectVertexFromFront(Dart e){ regions[e] = regions[vertexInfo[e].pathOrigin]; `````` Basile Sauvage committed Sep 05, 2012 86 87 `````` front.erase(vertexInfo[e].it); vertexInfo[e].valid=false; `````` Basile Sauvage committed Sep 05, 2012 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::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); } } `````` 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 `````` } } } } `````` Basile Sauvage committed Sep 05, 2012 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 ``````/*********************************************************** * 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){ `````` Basile Sauvage committed Sep 05, 2012 165 `````` distances[e] = this->vertexInfo[e].it->first; `````` Basile Sauvage committed Sep 05, 2012 166 167 168 169 170 171 `````` pathOrigins[e] = this->vertexInfo[e].pathOrigin; VoronoiDiagram::collectVertexFromFront(e); } `````` Basile Sauvage committed Aug 08, 2012 172 173 174 ``````}// end namespace Geometry }// end namespace Algo }// end namespace CGoGN``````