| 167 | |
| 168 | template <class TPopOrder> |
| 169 | void TrianglesInfo::ListInfo::MakeTrianglesChainImpl(PointsInfo const & points, TIterator start, |
| 170 | std::vector<Edge> & chain) const |
| 171 | { |
| 172 | chain.clear(); |
| 173 | |
| 174 | Triangle const fictive(start->first.second, start->first.first, -1); |
| 175 | |
| 176 | std::priority_queue<Edge, std::vector<Edge>, TPopOrder> q; |
| 177 | q.push(Edge(-1, start->second, 0, -1)); |
| 178 | |
| 179 | while (!q.empty()) |
| 180 | { |
| 181 | // pop current element |
| 182 | Edge e = q.top(); |
| 183 | q.pop(); |
| 184 | |
| 185 | // check if already processed |
| 186 | if (m_visited[e.m_p[1]]) |
| 187 | continue; |
| 188 | m_visited[e.m_p[1]] = true; |
| 189 | |
| 190 | // push to chain |
| 191 | chain.push_back(e); |
| 192 | |
| 193 | Triangle const & trg = m_triangles[e.m_p[1]]; |
| 194 | |
| 195 | // get neighbors |
| 196 | int nb[2]; |
| 197 | GetNeighbors(trg, (e.m_p[0] == -1) ? fictive : m_triangles[e.m_p[0]], nb); |
| 198 | |
| 199 | // push neighbors to queue |
| 200 | for (int i = 0; i < 2; ++i) |
| 201 | if (nb[i] != empty_key && !m_visited[nb[i]]) |
| 202 | q.push(Edge(e.m_p[1], nb[i], CalcDelta(points, trg, m_triangles[nb[i]]), i)); |
| 203 | } |
| 204 | } |
| 205 | |
| 206 | // Element with less m_delta is better than another one. |
| 207 | struct edge_greater_delta |