TopologyKernel.hh 26.7 KB
Newer Older
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
/*===========================================================================*\
 *                                                                           *
 *                            OpenVolumeMesh                                 *
 *        Copyright (C) 2011 by Computer Graphics Group, RWTH Aachen         *
 *                        www.openvolumemesh.org                             *
 *                                                                           *
 *---------------------------------------------------------------------------*
 *  This file is part of OpenVolumeMesh.                                     *
 *                                                                           *
 *  OpenVolumeMesh is free software: you can redistribute it and/or modify   *
 *  it under the terms of the GNU Lesser General Public License as           *
 *  published by the Free Software Foundation, either version 3 of           *
 *  the License, or (at your option) any later version with the              *
 *  following exceptions:                                                    *
 *                                                                           *
 *  If other files instantiate templates or use macros                       *
 *  or inline functions from this file, or you compile this file and         *
 *  link it with other files to produce an executable, this file does        *
 *  not by itself cause the resulting executable to be covered by the        *
 *  GNU Lesser General Public License. This exception does not however       *
 *  invalidate any other reasons why the executable file might be            *
 *  covered by the GNU Lesser General Public License.                        *
 *                                                                           *
 *  OpenVolumeMesh is distributed in the hope that it will be useful,        *
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
 *  GNU Lesser General Public License for more details.                      *
 *                                                                           *
 *  You should have received a copy of the GNU LesserGeneral Public          *
 *  License along with OpenVolumeMesh.  If not,                              *
 *  see <http://www.gnu.org/licenses/>.                                      *
 *                                                                           *
\*===========================================================================*/

/*===========================================================================*\
 *                                                                           *
 *   $Revision$                                                         *
 *   $Date$                    *
 *   $LastChangedBy$                                                *
 *                                                                           *
\*===========================================================================*/

#ifndef TOPOLOGYKERNEL_HH_
#define TOPOLOGYKERNEL_HH_

46
#include <cassert>
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
73
74
75
76
77
#include <set>
#include <vector>

#include "BaseEntities.hh"
#include "OpenVolumeMeshHandle.hh"
#include "ResourceManager.hh"
#include "Iterators.hh"

namespace OpenVolumeMesh {

class TopologyKernel : public ResourceManager {
public:

    TopologyKernel();
    virtual ~TopologyKernel();

    /*
     * Defines and constants
     */

    static const VertexHandle   InvalidVertexHandle;
    static const EdgeHandle     InvalidEdgeHandle;
    static const FaceHandle     InvalidFaceHandle;
    static const CellHandle     InvalidCellHandle;
    static const HalfEdgeHandle InvalidHalfEdgeHandle;
    static const HalfFaceHandle InvalidHalfFaceHandle;

    typedef OpenVolumeMeshEdge Edge;
    typedef OpenVolumeMeshFace Face;
    typedef OpenVolumeMeshCell Cell;

78
79
80
81
82
    // Add StatusAttrib to list of friend classes
    // since it provides a garbage collection
    // that needs access to some protected methods
    friend class StatusAttrib;

83
84
85
86
87
88
89
90
91
92
    //=====================================================================
    // Iterators
    //=====================================================================

    friend class VertexOHalfEdgeIter;
    friend class HalfEdgeHalfFaceIter;
    friend class VertexCellIter;
    friend class HalfEdgeCellIter;
    friend class CellVertexIter;
    friend class CellCellIter;
Mike Kremer's avatar
Mike Kremer committed
93
    friend class HalfFaceVertexIter;
94
    friend class BoundaryHalfFaceHalfFaceIter;
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
    friend class BoundaryFaceIter;
    friend class VertexIter;
    friend class EdgeIter;
    friend class HalfEdgeIter;
    friend class FaceIter;
    friend class HalfFaceIter;
    friend class CellIter;

    VertexOHalfEdgeIter voh_iter(const VertexHandle& _h) const {
        return VertexOHalfEdgeIter(_h, this);
    }

    HalfEdgeHalfFaceIter hehf_iter(const HalfEdgeHandle& _h) const {
        return HalfEdgeHalfFaceIter(_h, this);
    }

    VertexCellIter vc_iter(const VertexHandle& _h) const {
        return VertexCellIter(_h, this);
    }

    HalfEdgeCellIter hec_iter(const HalfEdgeHandle& _h) const {
        return HalfEdgeCellIter(_h, this);
    }

    CellVertexIter cv_iter(const CellHandle& _h) const {
        return CellVertexIter(_h, this);
    }

    CellCellIter cc_iter(const CellHandle& _h) const {
        return CellCellIter(_h, this);
    }

Mike Kremer's avatar
Mike Kremer committed
127
128
129
130
    HalfFaceVertexIter hfv_iter(const HalfFaceHandle& _h) const {
        return HalfFaceVertexIter(_h, this);
    }

131
132
133
134
    BoundaryHalfFaceHalfFaceIter bhfhf_iter(const HalfFaceHandle& _ref_h) const {
        return BoundaryHalfFaceHalfFaceIter(_ref_h, this);
    }

135
136
137
138
139
140
141
142
143
144
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
    BoundaryFaceIter bf_iter() const {
        return BoundaryFaceIter(this);
    }

    VertexIter v_iter() const {
        return VertexIter(this);
    }

    VertexIter vertices_begin() const {
        return VertexIter(this, VertexHandle(0));
    }

    VertexIter vertices_end() const {
        return VertexIter(this, VertexHandle(n_vertices()));
    }

    EdgeIter e_iter() const {
        return EdgeIter(this);
    }

    EdgeIter edges_begin() const {
        return EdgeIter(this, EdgeHandle(0));
    }

    EdgeIter edges_end() const {
        return EdgeIter(this, EdgeHandle(edges_.size()));
    }

    HalfEdgeIter he_iter() const {
        return HalfEdgeIter(this);
    }

    HalfEdgeIter halfedges_begin() const {
        return HalfEdgeIter(this, HalfEdgeHandle(0));
    }

    HalfEdgeIter halfedges_end() const {
        return HalfEdgeIter(this, HalfEdgeHandle(edges_.size() * 2));
    }

    FaceIter f_iter() const {
        return FaceIter(this);
    }

    FaceIter faces_begin() const {
        return FaceIter(this, FaceHandle(0));
    }

    FaceIter faces_end() const {
        return FaceIter(this, FaceHandle(faces_.size()));
    }

    HalfFaceIter hf_iter() const {
        return HalfFaceIter(this);
    }

    HalfFaceIter halffaces_begin() const {
        return HalfFaceIter(this, HalfFaceHandle(0));
    }

    HalfFaceIter halffaces_end() const {
        return HalfFaceIter(this, HalfFaceHandle(faces_.size() * 2));
    }

    CellIter c_iter() const {
        return CellIter(this);
    }

    CellIter cells_begin() const {
        return CellIter(this, CellHandle(0));
    }

    CellIter cells_end() const {
        return CellIter(this, CellHandle(cells_.size()));
    }

    /*
     * Virtual functions with implementation
     */

    /// Get number of vertices in mesh
216
    virtual size_t n_vertices()   const { return n_vertices_; }
217
    /// Get number of edges in mesh
218
    virtual size_t n_edges()      const { return edges_.size(); }
219
    /// Get number of halfedges in mesh
220
    virtual size_t n_halfedges()  const { return edges_.size() * 2u; }
221
    /// Get number of faces in mesh
222
    virtual size_t n_faces()      const { return faces_.size(); }
223
    /// Get number of halffaces in mesh
224
    virtual size_t n_halffaces()  const { return faces_.size() * 2u; }
225
    /// Get number of cells in mesh
226
    virtual size_t n_cells()      const { return cells_.size(); }
227

228
229
230
    int genus() const {

        int g = (1 - (n_vertices() -
231
232
                      n_edges() +
                      n_faces() -
233
234
235
236
237
238
239
                      n_cells()));

        if(g % 2 == 0) return (g / 2);

        // An error occured
        // The mesh might not be manifold
        return  -1;
240
241
    }

242
243
private:

244
    // Cache total vertex number
245
    size_t n_vertices_;
246
247

public:
248
249

    /// Add abstract vertex
250
    virtual VertexHandle add_vertex();
251
252
253
254

    //=======================================================================

    /// Add edge
255
    virtual EdgeHandle add_edge(const VertexHandle& _fromVertex, const VertexHandle& _toHandle, bool _allowDuplicates = false);
256
257

    /// Add face via incident edges
258
259
260
261
262
263
    ///
    /// \return Handle of the new face, InvalidFaceHandle if \a _halfedges
    ///         are not connected and \a _topologyCheck is \a true.
    ///
    /// \warning If _halfedges are not connected and \a _topologyCheck is \a false,
    ///          the behavior is undefined.
264
    virtual FaceHandle add_face(const std::vector<HalfEdgeHandle>& _halfedges, bool _topologyCheck = false);
265
266
267
268
269

    /// Add face via incident vertices
    virtual FaceHandle add_face(const std::vector<VertexHandle>& _vertices);

    /// Add cell via incident halffaces
270
271
272
273
274
275
    ///
    /// \return Handle of the new cell, InvalidCellHandle if \a _topologyCheck is \a true and
    ///         \a _halffaces are not connected.
    ///
    /// \warning If _halffaces are not connected and \a _topologyCheck is \a false,
    ///          the behavior is undefined.
276
    virtual CellHandle add_cell(const std::vector<HalfFaceHandle>& _halffaces, bool _topologyCheck = false);
277

278
279
280
281
282
283
284
285
286
    /// Set the vertices of an edge
    void set_edge(const EdgeHandle& _eh, const VertexHandle& _fromVertex, const VertexHandle& _toVertex);

    /// Set the half-edges of a face
    void set_face(const FaceHandle& _fh, const std::vector<HalfEdgeHandle>& _hes);

    /// Set the half-faces of a cell
    void set_cell(const CellHandle& _ch, const std::vector<HalfFaceHandle>& _hfs);

287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
    /*
     * Non-virtual functions
     */

    /// Get edge with handle _edgeHandle
    const Edge& edge(const EdgeHandle& _edgeHandle) const;

    /// Get face with handle _faceHandle
    const Face& face(const FaceHandle& _faceHandle) const;

    /// Get cell with handle _cellHandle
    const Cell& cell(const CellHandle& _cellHandle) const;

    /// Get edge with handle _edgeHandle
    Edge& edge(const EdgeHandle& _edgeHandle);

    /// Get face with handle _faceHandle
    Face& face(const FaceHandle& _faceHandle);

    /// Get cell with handle _cellHandle
    Cell& cell(const CellHandle& _cellHandle);

    /// Get edge that corresponds to halfedge with handle _halfEdgeHandle
310
    Edge halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
311
312

    /// Get face that corresponds to halfface with handle _halfFaceHandle
313
    Face halfface(const HalfFaceHandle& _halfFaceHandle) const;
314
315

    /// Get opposite halfedge that corresponds to halfedge with handle _halfEdgeHandle
316
    Edge opposite_halfedge(const HalfEdgeHandle& _halfEdgeHandle) const;
317
318

    /// Get opposite halfface that corresponds to halfface with handle _halfFaceHandle
319
    Face opposite_halfface(const HalfFaceHandle& _halfFaceHandle) const;
320

321
    /// Get halfedge from vertex _vh1 to _vh2
322
    HalfEdgeHandle halfedge(const VertexHandle& _vh1, const VertexHandle& _vh2) const;
323

324
325
326
    /// Get half-face from list of incident vertices (in connected order)
    ///
    /// \note Only the first three vertices are checked
327
    HalfFaceHandle halfface(const std::vector<VertexHandle>& _vs) const;
328

329
330
331
    /// Get half-face from list of incident half-edges
    ///
    /// \note Only the first two half-edges are checked
332
    HalfFaceHandle halfface(const std::vector<HalfEdgeHandle>& _hes) const;
333

334
    /// Get next halfedge within a halfface
335
    HalfEdgeHandle next_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
336
337

    /// Get previous halfedge within a halfface
338
    HalfEdgeHandle prev_halfedge_in_halfface(const HalfEdgeHandle& _heh, const HalfFaceHandle& _hfh) const;
339
340

    /// Get valence of vertex (number of incident edges)
341
    inline size_t valence(const VertexHandle& _vh) const {
342
343
344
        assert(has_vertex_bottom_up_incidences());
        assert(_vh.is_valid() && (size_t)_vh.idx() < outgoing_hes_per_vertex_.size());

345
346
347
348
        return outgoing_hes_per_vertex_[_vh.idx()].size();
    }

    /// Get valence of edge (number of incident faces)
349
    inline size_t valence(const EdgeHandle& _eh) const {
350
351
        assert(has_edge_bottom_up_incidences());
        assert(_eh.is_valid() && (size_t)_eh.idx() < edges_.size());
352
        assert((size_t)halfedge_handle(_eh, 0).idx() < incident_hfs_per_he_.size());
353

354
        return incident_hfs_per_he_[halfedge_handle(_eh, 0).idx()].size();
355
356
357
    }

    /// Get valence of face (number of incident edges)
358
    inline size_t valence(const FaceHandle& _fh) const {
359
        assert(_fh.is_valid() && (size_t)_fh.idx() < faces_.size());
360
361
362
363
364

        return face(_fh).halfedges().size();
    }

    /// Get valence of cell (number of incident faces)
365
    inline size_t valence(const CellHandle& _ch) const {
366
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
367
368
369
370

        return cell(_ch).halffaces().size();
    }

371
372
373
    //=====================================================================
    // Delete entities
    //=====================================================================
374

375
public:
376

377
    virtual VertexIter delete_vertex(const VertexHandle& _h);
378

379
    virtual EdgeIter delete_edge(const EdgeHandle& _h);
380

381
    virtual FaceIter delete_face(const FaceHandle& _h);
382

383
    virtual CellIter delete_cell(const CellHandle& _h);
384

385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
private:

    template <class ContainerT>
    void get_incident_edges(const ContainerT& _vs, std::set<EdgeHandle>& _es) const;

    template <class ContainerT>
    void get_incident_faces(const ContainerT& _es, std::set<FaceHandle>& _fs) const;

    template <class ContainerT>
    void get_incident_cells(const ContainerT& _fs, std::set<CellHandle>& _cs) const;

    VertexIter delete_vertex_core(const VertexHandle& _h);

    EdgeIter delete_edge_core(const EdgeHandle& _h);

    FaceIter delete_face_core(const FaceHandle& _h);

    CellIter delete_cell_core(const CellHandle& _h);

404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
protected:

    virtual void delete_multiple_vertices(const std::vector<bool>& _tag);

    virtual void delete_multiple_edges(const std::vector<bool>& _tag);

    virtual void delete_multiple_faces(const std::vector<bool>& _tag);

    virtual void delete_multiple_cells(const std::vector<bool>& _tag);

    class EdgeCorrector {
    public:
        EdgeCorrector(const std::vector<int>& _newIndices) :
            newIndices_(_newIndices) {}

        void operator()(Edge& _edge) {
            _edge.set_from_vertex(VertexHandle(newIndices_[_edge.from_vertex().idx()]));
            _edge.set_to_vertex(VertexHandle(newIndices_[_edge.to_vertex().idx()]));
        }
    private:
        const std::vector<int>& newIndices_;
    };

    class FaceCorrector {
    public:
        FaceCorrector(const std::vector<int>& _newIndices) :
            newIndices_(_newIndices) {}

        void operator()(Face& _face) {
            std::vector<HalfEdgeHandle> hes = _face.halfedges();
            for(std::vector<HalfEdgeHandle>::iterator he_it = hes.begin(),
                    he_end = hes.end(); he_it != he_end; ++he_it) {

                EdgeHandle eh = edge_handle(*he_it);
                unsigned char opp = (he_it->idx() - halfedge_handle(eh, 0).idx());
                *he_it = halfedge_handle(newIndices_[eh.idx()], opp);
            }
            _face.set_halfedges(hes);
        }
    private:
        const std::vector<int>& newIndices_;
    };

    class CellCorrector {
    public:
        CellCorrector(const std::vector<int>& _newIndices) :
            newIndices_(_newIndices) {}

        void operator()(Cell& _cell) {
            std::vector<HalfFaceHandle> hfs = _cell.halffaces();
            for(std::vector<HalfFaceHandle>::iterator hf_it = hfs.begin(),
                    hf_end = hfs.end(); hf_it != hf_end; ++hf_it) {

                FaceHandle fh = face_handle(*hf_it);
                unsigned char opp = (hf_it->idx() - halfface_handle(fh, 0).idx());
                *hf_it = halfface_handle(newIndices_[fh.idx()], opp);
            }
            _cell.set_halffaces(hfs);
        }
    private:
        const std::vector<int>& newIndices_;
    };

public:

469
470
471
472
    /** \brief Delete range of cells
     *
     * Deletes all cells in range [_first, _last].
     *
473
474
475
     * @param _first Iterator to first cell that is to be deleted
     * @param _last Iterator to last cell that is to be deleted
     * @return An iterator to the first cell after the deleted range
476
477
478
     */
    CellIter delete_cell_range(const CellIter& _first, const CellIter& _last);

479
public:
480
481

    /// Clear whole mesh
482
    virtual void clear(bool _clearProps = true) {
483
484
485
486
487
488
489

        edges_.clear();
        faces_.clear();
        cells_.clear();
        outgoing_hes_per_vertex_.clear();
        incident_hfs_per_he_.clear();
        incident_cell_per_hf_.clear();
Mike Kremer's avatar
Mike Kremer committed
490
        n_vertices_ = 0;
491

492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
        if(_clearProps) {

            // Delete all property data
            clear_vertex_props();
            clear_edge_props();
            clear_halfedge_props();
            clear_face_props();
            clear_halfface_props();
            clear_cell_props();
            clear_mesh_props();

        } else {
            // Resize props
            resize_vprops(0u);
            resize_eprops(0u);
            resize_fprops(0u);
            resize_cprops(0u);
        }
510
511
512
    }

    //=====================================================================
513
    // Bottom-up Incidences
514
515
    //=====================================================================

516
517
public:

518
    void enable_bottom_up_incidences(bool _enable = true) {
519

520
521
522
        enable_vertex_bottom_up_incidences(_enable);
        enable_edge_bottom_up_incidences(_enable);
        enable_face_bottom_up_incidences(_enable);
523
524
    }

525
    void enable_vertex_bottom_up_incidences(bool _enable = true) {
526
527

        if(_enable && !v_bottom_up_) {
528
            // Vertex bottom-up incidences have to be
529
            // recomputed for the whole mesh
530
            compute_vertex_bottom_up_incidences();
531
        }
532

533
534
535
536
        if(!_enable) {
            outgoing_hes_per_vertex_.clear();
        }

537
538
        v_bottom_up_ = _enable;
    }
539

540
    void enable_edge_bottom_up_incidences(bool _enable = true) {
541

542
        if(_enable && !e_bottom_up_) {
543
            // Edge bottom-up incidences have to be
544
            // recomputed for the whole mesh
545
            compute_edge_bottom_up_incidences();
546
547
548

            if(f_bottom_up_) {
                std::for_each(edges_begin(), edges_end(),
549
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
550
551
552
            }
        }

553
554
555
556
        if(!_enable) {
            incident_hfs_per_he_.clear();
        }

557
558
559
        e_bottom_up_ = _enable;
    }

560
    void enable_face_bottom_up_incidences(bool _enable = true) {
561

562
        bool updateOrder = false;
563
        if(_enable && !f_bottom_up_) {
564
            // Face bottom-up incidences have to be
565
            // recomputed for the whole mesh
566
            compute_face_bottom_up_incidences();
567

568
            updateOrder = true;
569
570
        }

571
572
573
574
        if(!_enable) {
            incident_cell_per_hf_.clear();
        }

575
        f_bottom_up_ = _enable;
576
577
578
579

        if(updateOrder) {
            if(e_bottom_up_) {
                std::for_each(edges_begin(), edges_end(),
580
                              fun::bind(&TopologyKernel::reorder_incident_halffaces, this, fun::placeholders::_1));
581
582
            }
        }
583
584
    }

585
586
587
588
    bool has_full_bottom_up_incidences() const {
        return (has_vertex_bottom_up_incidences() &&
                has_edge_bottom_up_incidences() &&
                has_face_bottom_up_incidences());
589
590
    }

591
    bool has_vertex_bottom_up_incidences() const { return v_bottom_up_; }
592

593
    bool has_edge_bottom_up_incidences() const { return e_bottom_up_; }
594

595
    bool has_face_bottom_up_incidences() const { return f_bottom_up_; }
596
597
598

private:

599
    void compute_vertex_bottom_up_incidences();
600

601
    void compute_edge_bottom_up_incidences();
602

603
    void compute_face_bottom_up_incidences();
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620

    void reorder_incident_halffaces(const EdgeHandle& _eh);

    // Outgoing halfedges per vertex
    std::vector<std::vector<HalfEdgeHandle> > outgoing_hes_per_vertex_;

    // Incident halffaces per (directed) halfedge
    std::vector<std::vector<HalfFaceHandle> > incident_hfs_per_he_;

    // Incident cell (at most one) per halfface
    std::vector<CellHandle> incident_cell_per_hf_;

    bool v_bottom_up_;

    bool e_bottom_up_;

    bool f_bottom_up_;
621
622
623
624
625

    //=====================================================================
    // Connectivity
    //=====================================================================

626
627
public:

628
629
630
631
632
633
    /// \brief Get halfface that is adjacent (w.r.t. a common halfedge) within the same cell
    ///
    /// \return Handle of the adjacent half-face if \a _halfFaceHandle is not
    ///         at a boundary, \a InvalidHalfFaceHandle otherwise.
    ///
    /// \warning The mesh must have face bottom-up incidences.
634
635
636
637
638
639
    HalfFaceHandle adjacent_halfface_in_cell(const HalfFaceHandle& _halfFaceHandle, const HalfEdgeHandle& _halfEdgeHandle) const;

    /// Get cell that is incident to the given halfface
    CellHandle incident_cell(const HalfFaceHandle& _halfFaceHandle) const;

    bool is_boundary(const HalfFaceHandle& _halfFaceHandle) const {
640
641
642
643
644

        assert(_halfFaceHandle.is_valid() && (size_t)_halfFaceHandle.idx() < faces_.size() * 2u);
        assert(has_face_bottom_up_incidences());
        assert((size_t)_halfFaceHandle.idx() < incident_cell_per_hf_.size());
        return incident_cell_per_hf_[_halfFaceHandle.idx()] == InvalidCellHandle;
645
646
647
    }

    bool is_boundary(const FaceHandle& _faceHandle) const {
648
649
        assert(_faceHandle.is_valid() && (size_t)_faceHandle.idx() < faces_.size());
        assert(has_face_bottom_up_incidences());
650
651
652
653
654
        return  is_boundary(halfface_handle(_faceHandle, 0)) ||
                is_boundary(halfface_handle(_faceHandle, 1));
    }

    bool is_boundary(const EdgeHandle& _edgeHandle) const {
655
656
657
        assert(has_edge_bottom_up_incidences());
        assert(_edgeHandle.is_valid() && (size_t)_edgeHandle.idx() < edges_.size());

658
659
660
661
662
663
664
665
666
667
        for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(halfedge_handle(_edgeHandle, 0));
                hehf_it.valid(); ++hehf_it) {
            if(is_boundary(face_handle(*hehf_it))) {
                return true;
            }
        }
        return false;
    }

    bool is_boundary(const HalfEdgeHandle& _halfedgeHandle) const {
668
669
670
        assert(has_edge_bottom_up_incidences());
        assert(_halfedgeHandle.is_valid() && (size_t)_halfedgeHandle.idx() < edges_.size() * 2u);

671
672
673
674
675
676
677
678
679
680
        for(HalfEdgeHalfFaceIter hehf_it = hehf_iter(_halfedgeHandle);
                hehf_it.valid(); ++hehf_it) {
            if(is_boundary(face_handle(*hehf_it))) {
                return true;
            }
        }
        return false;
    }

    bool is_boundary(const VertexHandle& _vertexHandle) const {
681
682
683
        assert(has_vertex_bottom_up_incidences());
        assert(_vertexHandle.is_valid() && (size_t)_vertexHandle.idx() < n_vertices());

684
685
686
687
688
689
        for(VertexOHalfEdgeIter voh_it = voh_iter(_vertexHandle); voh_it.valid(); ++voh_it) {
            if(is_boundary(*voh_it)) return true;
        }
        return false;
    }

690
    size_t n_vertices_in_cell(const CellHandle& _ch) const {
691
        assert(_ch.is_valid() && (size_t)_ch.idx() < cells_.size());
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711

        std::set<VertexHandle> vertices;
        std::vector<HalfFaceHandle> hfs = cell(_ch).halffaces();
        for(std::vector<HalfFaceHandle>::const_iterator hf_it = hfs.begin();
                hf_it != hfs.end(); ++hf_it) {
            std::vector<HalfEdgeHandle> hes = halfface(*hf_it).halfedges();
            for(std::vector<HalfEdgeHandle>::const_iterator he_it = hes.begin();
                he_it != hes.end(); ++he_it) {
                vertices.insert(halfedge(*he_it).to_vertex());
            }
        }
        return vertices.size();
    }

    //=========================================================================

    /*
     * Non-virtual functions
     */

712
    Edge opposite_halfedge(const Edge& _edge) const {
713
714
715
        return Edge(_edge.to_vertex(), _edge.from_vertex());
    }

716
    Face opposite_halfface(const Face& _face) const {
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
        std::vector<HalfEdgeHandle> opp_halfedges;
        for(std::vector<HalfEdgeHandle>::const_iterator it = _face.halfedges().begin(); it
                != _face.halfedges().end(); ++it) {
            opp_halfedges.insert(opp_halfedges.begin(), opposite_halfedge_handle(*it));
        }

        return Face(opp_halfedges);
    }

    /*
     * Static functions
     */

    /// Conversion function
    static inline HalfEdgeHandle halfedge_handle(const EdgeHandle& _h, const unsigned char _subIdx) {
        // Is handle in range?
733
734
735
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfEdgeHandle;
736
737
738
739
740
741
        return HalfEdgeHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
    }

    /// Conversion function
    static inline HalfFaceHandle halfface_handle(const FaceHandle& _h, const unsigned char _subIdx) {
        // Is handle in range?
742
743
744
        assert(_h.is_valid());
        assert(_subIdx < 2);
        // if(_h.idx() < 0 || _subIdx > 1) return InvalidHalfFaceHandle;
745
        return HalfFaceHandle((2 * _h.idx()) + (_subIdx ? 1 : 0));
746
747
748
749
750
    }

    /// Handle conversion
    static inline EdgeHandle edge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
751
752
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidEdgeHandle;
753
754
755
756
757
        return EdgeHandle((int)(_h.idx() / 2));
    }

    static inline FaceHandle face_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
758
759
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidFaceHandle;
760
761
762
763
764
        return FaceHandle((int)(_h.idx() / 2));
    }

    static inline HalfEdgeHandle opposite_halfedge_handle(const HalfEdgeHandle& _h) {
        // Is handle in range?
765
766
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfEdgeHandle;
767
768
769
770
771
772
773
774
775
776

        // Is handle even?
        if(_h.idx() % 2 == 0) {
            return HalfEdgeHandle(_h.idx() + 1);
        }
        return HalfEdgeHandle(_h.idx() - 1);
    }

    static inline HalfFaceHandle opposite_halfface_handle(const HalfFaceHandle& _h) {
        // Is handle in range?
777
778
        assert(_h.is_valid());
        // if(_h.idx() < 0) return InvalidHalfFaceHandle;
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801

        // Is handle even?
        if(_h.idx() % 2 == 0) {
            return HalfFaceHandle(_h.idx() + 1);
        }
        return HalfFaceHandle(_h.idx() - 1);
    }

protected:

    // List of edges
    std::vector<Edge> edges_;

    // List of faces
    std::vector<Face> faces_;

    // List of cells
    std::vector<Cell> cells_;
};

}

#endif /* TOPOLOGYKERNEL_HH_ */