-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathindex.html
755 lines (752 loc) · 86.5 KB
/
index.html
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
69
70
71
72
73
74
75
76
77
78
79
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
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
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
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
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<link rel="canonical" href="https://doc.cgal.org/latest/Polyhedron/index.html"/>
<link rel="icon" type="image/png" href="../Manual/g-196x196-doc.png">
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=11">
<meta name="generator" content="Doxygen 1.9.6">
<meta name="viewport" content="width=device-width, initial-scale=1">
<title>CGAL 6.1 - 3D Polyhedral Surface: User Manual</title>
<!-- <link href="../Manual/tabs.css" rel="stylesheet" type="text/css"/> -->
<script type="text/javascript" src="../Manual/jquery.js"></script>
<script type="text/javascript" src="../Manual/dynsections.js"></script>
<script src="../Manual/hacks.js" type="text/javascript"></script>
<!-- Manually include treeview and search to avoid bloat and to fix
paths to the directory Manual . -->
<!-- $.treeview -->
<!-- $.search -->
<link href="navtree.css" rel="stylesheet" type="text/css">
<script type="text/javascript" src="../Manual/resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
</script>
<link href="../Manual/search/search.css" rel="stylesheet" type="text/css">
<script type="text/javascript" src="../Manual/search/searchdata.js"></script>
<script type="text/javascript" src="../Manual/search/search.js"></script>
<script type="text/javascript">
$(document).ready(function() { init_search(); });
</script>
<link href="../Manual/search/search.css" rel="stylesheet" type="text/css">
<script type="text/javascript" src="../Manual/search/search.js"></script>
<!-- Manually done below. -->
<link href="../Manual/doxygen.css" rel="stylesheet" type="text/css">
<link href="../Manual/cgal_stylesheet.css" rel="stylesheet" type="text/css">
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
extensions: ["tex2jax.js", "TeX/AMSmath.js", "TeX/AMSsymbols.js"],
jax: ["input/TeX","output/HTML-CSS"],
});
//<![CDATA[
MathJax.Hub.Config(
{
TeX: {
Macros: {
qprel: [ "{\\gtreqless}", 0],
qpx: [ "{\\mathbf{x}}", 0],
qpl: [ "{\\mathbf{l}}", 0],
qpu: [ "{\\mathbf{u}}", 0],
qpc: [ "{\\mathbf{c}}", 0],
qpb: [ "{\\mathbf{b}}", 0],
qpy: [ "{\\mathbf{y}}", 0],
qpw: [ "{\\mathbf{w}}", 0],
qplambda: [ "{\\mathbf{\\lambda}}", 0],
ssWpoint: [ "{\\bf #1}", 1],
ssWeight: [ "{w_{#1}}", 1],
dabs: [ "{\\parallel\\! #1 \\!\\parallel}", 1],
E: [ "{\\mathrm{E}}", 0],
A: [ "{\\mathrm{A}}", 0],
R: [ "{\\mathrm{R}}", 0],
N: [ "{\\mathrm{N}}", 0],
Q: [ "{\\mathrm{Q}}", 0],
Z: [ "{\\mathrm{Z}}", 0],
ccSum: [ "{\\sum_{#1}^{#2}{#3}}", 3],
ccProd: [ "{\\prod_{#1}^{#2}{#3}}", 3],
pyr: [ "{\\operatorname{Pyr}}", 0],
aff: [ "{\\operatorname{aff}}", 0],
Ac: [ "{\\cal A}", 0],
Sc: [ "{\\cal S}", 0],
},
equationNumbers: { autoNumber: "AMS" }
}
}
);
MathJax.Hub.Register.StartupHook("TeX Jax Ready",function () {
var PARSE = MathJax.InputJax.TeX.Parse,
TEXT = PARSE.prototype.InternalText;
PARSE.Augment({
InternalText: function (text,def) {
text = text.replace(/\\/g,"");
return TEXT.call(this,text,def);
}
});
});
//]]>
</script>
<script type="text/javascript" async="async" src="https://cdn.jsdelivr.net/npm/mathjax@2/MathJax.js"></script>
<script src="modules.js" type="text/javascript"></script>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="back-nav">
<ul>
<li><a href="https://www.cgal.org/">cgal.org</a></li>
<li><a href="../Manual/index.html">Top</a></li>
<li><a href="../Manual/general_intro.html">Getting Started</a></li>
<li><a href="../Manual/tutorials.html">Tutorials</a></li>
<li><a href="../Manual/packages.html">Package Overview</a></li>
<li><a href="../Manual/how_to_cite_cgal.html">Acknowledging CGAL</a></li>
</ul>
<!-- In a package SEARCHENGINE = false, so we cannot use
insertion. That's why we have to do it manually here. Notice
that we also take pngs from the Manual. -->
<div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<span id="MSearchSelect" onmouseover="return searchBox.OnSearchSelectShow()" onmouseout="return searchBox.OnSearchSelectHide()">
</span>
<input type="text" id="MSearchField" value="" placeholder="Search" accesskey="S" onfocus="searchBox.OnSearchFieldFocus(true)" onblur="searchBox.OnSearchFieldFocus(false)" onkeyup="searchBox.OnSearchFieldChange(event)">
</span>
<span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="../Manual/search/close.svg" alt=""></a>
</span>
</div>
</div>
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr id="projectrow">
<td id="projectalign">
<div id="projectname">CGAL 6.1 - 3D Polyhedral Surface
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- Code below is usually inserted by doxygen when SEARCHENGINE =
true. Notice that the path to the search directory is adjusted to
the top-level.-->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../Manual/search/",'.html');
</script>
<!-- window showing the filter options -->
<div id="MSearchSelectWindow" onmouseover="return searchBox.OnSearchSelectShow()" onmouseout="return searchBox.OnSearchSelectHide()" onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.9.6 -->
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync" style="display: none"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;" class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(document).ready(function(){initNavTree('index.html',''); initResizable(); });
/* @license-end */
</script>
<div id="doc-content">
<div><div class="header">
<div class="headertitle"><div class="title">User Manual </div></div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p><a class="anchor" id="Chapter_3D_Polyhedral_Surfaces"></a><a class="anchor" id="chapterPolyhedron"></a> </p><dl class="section author"><dt>Author</dt><dd>Lutz Kettner <div id="autotoc" class="toc"></div> </dd></dl>
<h1><a class="anchor" id="sectionPolyIntro"></a>
Introduction</h1>
<p>Polyhedral surfaces in three dimensions are composed of vertices, edges, facets and an incidence relationship on them. The organization beneath is a halfedge data structure, which restricts the class of representable surfaces to orientable 2-manifolds - with and without boundary. If the surface is closed we call it a <em>polyhedron</em>, for example, see the following model of a hammerhead:</p>
<div class="image">
<img src="shark.png" alt="">
</div>
<p>The polyhedral surface is realized as a container class that manages vertices, halfedges, facets with their incidences, and that maintains the combinatorial integrity of them. It is based on the highly flexible design of the halfedge data structure, see the introduction in Chapter <a class="elRef" href="../HalfedgeDS/index.html#chapterHalfedgeDS">Halfedge Data Structures</a> and <a class="el" href="citelist.html#CITEREF_k-ugpdd-99">[3]</a>. However, the polyhedral surface can be used and understood without knowing the underlying design. Some of the examples in this chapter gradually introduce applications of this flexibility.</p>
<h1><a class="anchor" id="PolyhedronDefinition"></a>
Definition</h1>
<p>A polyhedral surface <code><a class="el" href="classCGAL_1_1Polyhedron__3.html" title="A polyhedral surface Polyhedron_3 consists of vertices V, edges E, facets F and an incidence relation...">Polyhedron_3</a><<a class="el" href="classPolyhedronTraits__3.html" title="Required types and member functions for the PolyhedronTraits_3 concept. This geometric traits concept...">PolyhedronTraits_3</a>></code> in three dimensions consists of vertices <code>V</code>, edges <code>E</code>, facets <code>F</code> and an incidence relation on them. Each edge is represented by two halfedges with opposite orientations. The incidences stored with a halfedge are illustrated in the following figure:</p>
<div class="image">
<img src="halfedge_small.png" alt="">
</div>
<p>Vertices represent points in space. Edges are straight line segments between two endpoints. Facets are planar, possibly non-convex, polygons without holes. Facets are defined by the circular sequence of halfedges along their boundary. The polyhedral surface itself can have holes (with at least two facets surrounding it since a single facet cannot have a hole). The halfedges along the boundary of a hole are called <em>border halfedges</em> and have no incident facet. An edge is a <em>border edge</em> if one of its halfedges is a border halfedge. A surface is <em>closed</em> if it contains no border halfedges. A closed surface is a boundary representation for a polyhedron in three dimensions. The convention is that the halfedges are oriented counterclockwise around facets as seen from the outside of the polyhedron. An implication is that the halfedges are oriented clockwise around the vertices. The notion of the solid side of a facet as defined by the halfedge orientation extends to polyhedral surfaces with border edges although they do not define a closed object. If normal vectors are considered for the facets, normals point outwards (following the right-hand rule).</p>
<p>The strict definition can be found in <a class="el" href="citelist.html#CITEREF_k-ugpdd-99">[3]</a>. One implication of this definition is that the polyhedral surface is always an orientable and oriented 2-manifold with border edges, i.e., the neighborhood of each point on the polyhedral surface is either homeomorphic to a disc or to a half disc, except for vertices where multiple holes join. Another implication is that the smallest representable surface avoiding self intersections is a triangle (for polyhedral surfaces with border edges) or a tetrahedron (for polyhedra). Boundary representations of orientable 2-manifolds are closed under <a class="elRef" href="../BGL/group__PkgBGLEulerOperations.html">Euler</a> operations. They are extended with operations that create or close holes in the surface.</p>
<p>Other intersections besides the incidence relation are not allowed. However, this is not automatically verified in the operations, since self intersections are not easy to check efficiently. <code><a class="el" href="classCGAL_1_1Polyhedron__3.html" title="A polyhedral surface Polyhedron_3 consists of vertices V, edges E, facets F and an incidence relation...">Polyhedron_3</a><<a class="el" href="classPolyhedronTraits__3.html" title="Required types and member functions for the PolyhedronTraits_3 concept. This geometric traits concept...">PolyhedronTraits_3</a>></code> does only maintain the combinatorial integrity of the polyhedral surface (using <a class="elRef" href="../BGL/group__PkgBGLEulerOperations.html">Euler</a> operations) and does not consider the coordinates of the points or any other geometric information.</p>
<p><code><a class="el" href="classCGAL_1_1Polyhedron__3.html" title="A polyhedral surface Polyhedron_3 consists of vertices V, edges E, facets F and an incidence relation...">Polyhedron_3</a><<a class="el" href="classPolyhedronTraits__3.html" title="Required types and member functions for the PolyhedronTraits_3 concept. This geometric traits concept...">PolyhedronTraits_3</a>></code> can represent polyhedral surfaces as well as polyhedra. The interface is designed in such a way that it is easy to ignore border edges and work only with polyhedra.</p>
<h1><a class="anchor" id="PolyhedronExample"></a>
Example Programs</h1>
<p><a class="anchor" id="sectionPolyExamples"></a> The polyhedral surface is based on the highly flexible design of the halfedge data structure. Examples for this flexibility can be found in Section <a class="el" href="index.html#PolyhedronExtending">Extending Vertices, Halfedges, and Facets</a> and in Section <a class="elRef" href="../HalfedgeDS/index.html#HalfedgeDSExample">Examples</a> of the chapter on the halfedge data structure. This design is not a prerequisite to understand the following examples. See also the Section <a class="el" href="index.html#sectionPolyAdvanced">sectionPolyAdvanced</a> below for some advanced examples.</p>
<h2><a class="anchor" id="PolyhedronFirstExampleUsingDefaults"></a>
First Example Using Defaults</h2>
<p>The first example instantiates a polyhedron using a kernel as traits class. It creates a tetrahedron and stores the reference to one of its halfedges in a <code>Halfedge_handle</code>. Handles, also know as <em>trivial iterators</em>, are used to keep references to halfedges, vertices, or facets for future use. There is also a <code>Halfedge_iterator</code> type for enumerating halfedges. Such an iterator type can be used wherever a handle is required. Respective <code>Halfedge_const_handle</code> and <code>Halfedge_const_iterator</code> for a constant polyhedron and similar handles and iterators with <code>Vertex_</code> and <code>Facet_</code> prefix are provided too.</p>
<p>The example continues with a test if the halfedge actually refers to a tetrahedron. This test checks the connected component referred to by the halfedge <code>h</code> and not the polyhedral surface as a whole. This example works only on the combinatorial level of a polyhedral surface. The next example adds the geometry.</p>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_simple_8cpp-example.html">Polyhedron/polyhedron_prog_simple.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Halfedge_handle Halfedge_handle;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Polyhedron P;</div>
<div class="line"> Halfedge_handle h = P.<a class="code hl_function" href="classCGAL_1_1Polyhedron__3.html#a1ebc714bb6fc75a8aa105ffb241fe087">make_tetrahedron</a>();</div>
<div class="line"> <span class="keywordflow">if</span> ( P.is_tetrahedron(h))</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line"> <span class="keywordflow">return</span> 1;</div>
<div class="line">}</div>
<div class="ttc" id="aclassCGAL_1_1Polyhedron__3_html"><div class="ttname"><a href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3</a></div><div class="ttdoc">A polyhedral surface Polyhedron_3 consists of vertices V, edges E, facets F and an incidence relation...</div><div class="ttdef"><b>Definition:</b> Polyhedron_3.h:113</div></div>
<div class="ttc" id="aclassCGAL_1_1Polyhedron__3_html_a1ebc714bb6fc75a8aa105ffb241fe087"><div class="ttname"><a href="classCGAL_1_1Polyhedron__3.html#a1ebc714bb6fc75a8aa105ffb241fe087">CGAL::Polyhedron_3::make_tetrahedron</a></div><div class="ttdeci">Halfedge_handle make_tetrahedron()</div><div class="ttdoc">a tetrahedron is added to the polyhedral surface.</div></div>
<div class="ttc" id="anamespaceKernel_html"><div class="ttname"><a href="../Kernel_23/namespaceKernel.html">Kernel</a></div></div>
<div class="ttc" id="astructCGAL_1_1Simple__cartesian_html"><div class="ttname"><a href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian</a></div></div>
</div><!-- fragment --><h2><a class="anchor" id="PolyhedronExamplewithGeometryinVertices"></a>
Example with Geometry in Vertices</h2>
<p>We add geometry to the our construction of a tetrahedron. Four points are passed as arguments to the construction. This example demonstrates in addition the use of the vertex iterator and the access to the point in the vertices. Note the natural access notation <code>v-></code><a class="el" href="classCGAL_1_1Polyhedron__3_1_1Vertex.html#ac49f332933bd0183b55057a6d1529cd1"><code>point()</code></a>. Similarly, all information stored in a vertex, halfedge, and facet can be accessed with a member function given a handle or iterator. For example, given a halfedge handle <code>h</code> we can write <code>h-></code><a class="el" href="classCGAL_1_1Polyhedron__3_1_1Halfedge.html#a3e7b0ca74b69a5868b430f958666df27"><code>next()</code></a> to get a halfedge handle to the next halfedge, <code>h-></code><a class="el" href="classCGAL_1_1Polyhedron__3_1_1Halfedge.html#a6f1d84341f035c8ed72ef53281173fb4"><code>opposite()</code></a> for the opposite halfedge, <code>h-></code><a class="el" href="classCGAL_1_1Polyhedron__3_1_1Halfedge.html#a5d4131be8dac43edcb5f7376d2d125bd"><code>vertex()</code></a> for the incident vertex at the tip of <code>h</code>, and so on. The output of the program will be</p>
<pre class="fragment">1 0 0
0 1 0
0 0 1
0 0 0
</pre><p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_tetra_8cpp-example.html">Polyhedron/polyhedron_prog_tetra.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <iostream></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classKernel_1_1Point__3.html">Kernel::Point_3</a> Point_3;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Vertex_iterator Vertex_iterator;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Point_3 p( 1.0, 0.0, 0.0);</div>
<div class="line"> Point_3 q( 0.0, 1.0, 0.0);</div>
<div class="line"> Point_3 r( 0.0, 0.0, 1.0);</div>
<div class="line"> Point_3 s( 0.0, 0.0, 0.0);</div>
<div class="line"> </div>
<div class="line"> Polyhedron P;</div>
<div class="line"> P.make_tetrahedron( p, q, r, s);</div>
<div class="line"> <a class="code hl_functionRef" href="../Stream_support/group__PkgStreamSupportRef.html#ga7d51c854b865a7eb367e21fc43bd37b8">CGAL::IO::set_ascii_mode</a>( std::cout);</div>
<div class="line"> <span class="keywordflow">for</span> ( Vertex_iterator v = P.vertices_begin(); v != P.vertices_end(); ++v)</div>
<div class="line"> std::cout << v->point() << std::endl;</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclassKernel_1_1Point__3_html"><div class="ttname"><a href="../Kernel_23/classKernel_1_1Point__3.html">Kernel::Point_3</a></div></div>
<div class="ttc" id="agroup__PkgStreamSupportRef_html_ga7d51c854b865a7eb367e21fc43bd37b8"><div class="ttname"><a href="../Stream_support/group__PkgStreamSupportRef.html#ga7d51c854b865a7eb367e21fc43bd37b8">CGAL::IO::set_ascii_mode</a></div><div class="ttdeci">Mode set_ascii_mode(std::ios &s)</div></div>
</div><!-- fragment --><p>The polyhedron offers a point iterator for convenience. The above <code>for</code> loop simplifies to a single statement by using <code>std::copy</code> and the ostream iterator adaptor.</p>
<div class="fragment"><div class="line">std::copy( P.points_begin(), P.points_end(),</div>
<div class="line">std::ostream_iterator<Point_3>(std::cout,<span class="stringliteral">"\n"</span>));</div>
</div><!-- fragment --><h2><a class="anchor" id="PolyhedronExampleforAffineTransformation"></a>
Example for Affine Transformation</h2>
<p>An affine transformation <code>A</code> can act as a functor transforming points and a point iterator is conveniently defined for polyhedral surfaces. So, assuming we want only the point coordinates of a polyhedron <code>P</code> transformed, <code>std::transform</code> does the job in a single line.</p>
<div class="fragment"><div class="line">std::transform( P.points_begin(), P.points_end(), P.points_begin(), A);</div>
</div><!-- fragment --><h2><a class="anchor" id="PolyhedronExampleComputingPlaneEquations"></a>
Example Computing Plane Equations</h2>
<p>The polyhedral surface has already provisions to store a plane equation for each facet. However, it does not provide a function to compute plane equations.</p>
<p>This example computes the plane equations of a polyhedral surface. The actual computation is implemented in the <code>Plane_equation</code> functor. Depending on the arithmetic (exact/inexact) and the shape of the facets (convex/non-convex) different methods are useful. We assume here strictly convex facets and exact arithmetic. In our example a homogeneous representation with <code>int</code> coordinates is sufficient. The four plane equations of the tetrahedron are the output of the program.</p>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_planes_8cpp-example.html">Polyhedron/polyhedron_prog_planes.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <iostream></span></div>
<div class="line"><span class="preprocessor">#include <algorithm></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">struct </span>Plane_equation {</div>
<div class="line"> <span class="keyword">template</span> <<span class="keyword">class</span> Facet></div>
<div class="line"> <span class="keyword">typename</span> Facet::Plane_3 operator()( Facet& f) {</div>
<div class="line"> <span class="keyword">typename</span> Facet::Halfedge_handle h = f.halfedge();</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> Facet::Plane_3 Plane;</div>
<div class="line"> <span class="keywordflow">return</span> Plane( h->vertex()->point(),</div>
<div class="line"> h->next()->vertex()->point(),</div>
<div class="line"> h->next()->next()->vertex()->point());</div>
<div class="line"> }</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classKernel_1_1Point__3.html">Kernel::Point_3</a> Point_3;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classKernel_1_1Plane__3.html">Kernel::Plane_3</a> Plane_3;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Point_3 p( 1, 0, 0);</div>
<div class="line"> Point_3 q( 0, 1, 0);</div>
<div class="line"> Point_3 r( 0, 0, 1);</div>
<div class="line"> Point_3 s( 0, 0, 0);</div>
<div class="line"> Polyhedron P;</div>
<div class="line"> P.make_tetrahedron( p, q, r, s);</div>
<div class="line"> std::transform( P.facets_begin(), P.facets_end(), P.planes_begin(),</div>
<div class="line"> Plane_equation());</div>
<div class="line"> <a class="code hl_functionRef" href="../Stream_support/group__PkgStreamSupportRef.html#ga2cbb865dd83eedd780f4a452635b1d28">CGAL::IO::set_pretty_mode</a>( std::cout);</div>
<div class="line"> std::copy( P.planes_begin(), P.planes_end(),</div>
<div class="line"> std::ostream_iterator<Plane_3>( std::cout, <span class="stringliteral">"\n"</span>));</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclassKernel_1_1Plane__3_html"><div class="ttname"><a href="../Kernel_23/classKernel_1_1Plane__3.html">Kernel::Plane_3</a></div></div>
<div class="ttc" id="agroup__PkgStreamSupportRef_html_ga2cbb865dd83eedd780f4a452635b1d28"><div class="ttname"><a href="../Stream_support/group__PkgStreamSupportRef.html#ga2cbb865dd83eedd780f4a452635b1d28">CGAL::IO::set_pretty_mode</a></div><div class="ttdeci">Mode set_pretty_mode(std::ios &s)</div></div>
</div><!-- fragment --><h2><a class="anchor" id="sectionPolyVector"></a>
Example with a Vector Instead of a List Representation</h2>
<p>The polyhedron class template has actually four parameters, where three of them have default values. Using the default values explicitly in our examples above for three parameter - ignoring the fourth parameter, which would be a standard allocator for container class - the definition of a polyhedron looks like:</p>
<div class="fragment"><div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3</a>< Traits,</div>
<div class="line"><a class="code hl_class" href="classCGAL_1_1Polyhedron__items__3.html">CGAL::Polyhedron_items_3</a>,</div>
<div class="line"><a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__default.html">CGAL::HalfedgeDS_default</a>> Polyhedron;</div>
<div class="ttc" id="aclassCGAL_1_1HalfedgeDS__default_html"><div class="ttname"><a href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__default.html">CGAL::HalfedgeDS_default</a></div></div>
<div class="ttc" id="aclassCGAL_1_1Polyhedron__items__3_html"><div class="ttname"><a href="classCGAL_1_1Polyhedron__items__3.html">CGAL::Polyhedron_items_3</a></div><div class="ttdoc">The class Polyhedron_items_3 is a model of the PolyhedronItems_3 concept.</div><div class="ttdef"><b>Definition:</b> Polyhedron_items_3.h:35</div></div>
</div><!-- fragment --><p>The <code><a class="el" href="classCGAL_1_1Polyhedron__items__3.html" title="The class Polyhedron_items_3 is a model of the PolyhedronItems_3 concept.">Polyhedron_items_3</a></code> class contains the types used for vertices, edges, and facets. The <code><a class="elRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__default.html">HalfedgeDS_default</a></code> class defines the halfedge data structure used, which is a list-based representation in this case. An alternative is a vector-based representation. Using a vector provides random access for the elements in the polyhedral surface and is more space efficient, but elements cannot be deleted arbitrarily. Using a list allows arbitrary deletions, but provides only bidirectional iterators and is less space efficient. The following example creates again a tetrahedron with given points, but in a vector-based representation.</p>
<p>The vector-based representation resizes automatically if the reserved capacity is not sufficient for the new items created. Upon resizing all handles, iterators, and circulators become invalid. Their correct update in the halfedge data structure is costly, thus it is advisable to reserve enough space in advance as indicated with the alternative constructor in the comment.</p>
<div class="CGALAdvanced"> <div>Advanced</div> <p>Note that the polyhedron and not the underlying halfedge data structure triggers the resize operation, since the resize operation requires some preconditions, such as valid incidences, to be fulfilled that only the polyhedron can guarantee. </p> </div> <p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_vector_8cpp-example.html">Polyhedron/polyhedron_prog_vector.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/HalfedgeDS_vector.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <iostream></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classKernel_1_1Point__3.html">Kernel::Point_3</a> Point_3;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3</a>< <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>,</div>
<div class="line"> <a class="code hl_class" href="classCGAL_1_1Polyhedron__items__3.html">CGAL::Polyhedron_items_3</a>,</div>
<div class="line"> <a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__vector.html">CGAL::HalfedgeDS_vector</a>> Polyhedron;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Point_3 p( 1.0, 0.0, 0.0);</div>
<div class="line"> Point_3 q( 0.0, 1.0, 0.0);</div>
<div class="line"> Point_3 r( 0.0, 0.0, 1.0);</div>
<div class="line"> Point_3 s( 0.0, 0.0, 0.0);</div>
<div class="line"> </div>
<div class="line"> Polyhedron P; <span class="comment">// alternative constructor: Polyhedron P(4,12,4);</span></div>
<div class="line"> P.make_tetrahedron( p, q, r, s);</div>
<div class="line"> <a class="code hl_functionRef" href="../Stream_support/group__PkgStreamSupportRef.html#ga7d51c854b865a7eb367e21fc43bd37b8">CGAL::IO::set_ascii_mode</a>( std::cout);</div>
<div class="line"> std::copy( P.points_begin(), P.points_end(),</div>
<div class="line"> std::ostream_iterator<Point_3>( std::cout, <span class="stringliteral">"\n"</span>));</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclassCGAL_1_1HalfedgeDS__vector_html"><div class="ttname"><a href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__vector.html">CGAL::HalfedgeDS_vector</a></div></div>
</div><!-- fragment --><h2><a class="anchor" id="PolyhedronExamplewithCirculatorWritingObject"></a>
Example with Circulator Writing Object File Format (OFF)</h2>
<p>We create a tetrahedron and write it to <code>std::cout</code> using the Object File Format (OFF) <a class="el" href="citelist.html#CITEREF_cgal:p-gmgv16-96">[5]</a>. This example makes use of STL algorithms (<code>std::copy</code>, <code>std::distance</code>), STL <code>std::ostream_iterator</code>, and CGAL circulators. The polyhedral surface provides convenient circulators for the counterclockwise circular sequence of halfedges around a facet and the clockwise circular sequence of halfedges around a vertex.</p>
<p>However, the computation of the vertex index in the inner loop of the facet output is not advisable with the <code>std::distance</code> function, since it takes linear time for non random-access iterators, which leads to quadratic runtime. For better runtime the vertex index needs to be stored separately and computed once before writing the facets. It can be stored, for example, in the vertex itself or in a hash-structure. See also Section <a class="el" href="index.html#PolyhedronFile">File I/O</a>.</p>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_off_8cpp-example.html">Polyhedron/polyhedron_prog_off.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <iostream></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classKernel_1_1Point__3.html">Kernel::Point_3</a> Point_3;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Facet_iterator Facet_iterator;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Halfedge_around_facet_circulator Halfedge_facet_circulator;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Point_3 p( 0.0, 0.0, 0.0);</div>
<div class="line"> Point_3 q( 1.0, 0.0, 0.0);</div>
<div class="line"> Point_3 r( 0.0, 1.0, 0.0);</div>
<div class="line"> Point_3 s( 0.0, 0.0, 1.0);</div>
<div class="line"> </div>
<div class="line"> Polyhedron P;</div>
<div class="line"> P.make_tetrahedron( p, q, r, s);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// Write polyhedron in Object File Format (OFF).</span></div>
<div class="line"> <a class="code hl_functionRef" href="../Stream_support/group__PkgStreamSupportRef.html#ga7d51c854b865a7eb367e21fc43bd37b8">CGAL::IO::set_ascii_mode</a>( std::cout);</div>
<div class="line"> std::cout << <span class="stringliteral">"OFF"</span> << std::endl << P.size_of_vertices() << <span class="charliteral">' '</span></div>
<div class="line"> << P.size_of_facets() << <span class="stringliteral">" 0"</span> << std::endl;</div>
<div class="line"> std::copy( P.points_begin(), P.points_end(),</div>
<div class="line"> std::ostream_iterator<Point_3>( std::cout, <span class="stringliteral">"\n"</span>));</div>
<div class="line"> <span class="keywordflow">for</span> ( Facet_iterator i = P.facets_begin(); i != P.facets_end(); ++i) {</div>
<div class="line"> Halfedge_facet_circulator j = i->facet_begin();</div>
<div class="line"> <span class="comment">// Facets in polyhedral surfaces are at least triangles.</span></div>
<div class="line"> std::cout << <a class="code hl_functionRef" href="../Circulator/group__PkgHandlesAndCirculatorsFunctions.html#ga2d7bfa21e8eb046b8ae90104aa4fcce4">CGAL::circulator_size</a>(j) << <span class="charliteral">' '</span>;</div>
<div class="line"> <span class="keywordflow">do</span> {</div>
<div class="line"> std::cout << <span class="charliteral">' '</span> << std::distance(P.vertices_begin(), j->vertex());</div>
<div class="line"> } <span class="keywordflow">while</span> ( ++j != i->facet_begin());</div>
<div class="line"> std::cout << std::endl;</div>
<div class="line"> }</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="agroup__PkgHandlesAndCirculatorsFunctions_html_ga2d7bfa21e8eb046b8ae90104aa4fcce4"><div class="ttname"><a href="../Circulator/group__PkgHandlesAndCirculatorsFunctions.html#ga2d7bfa21e8eb046b8ae90104aa4fcce4">CGAL::circulator_size</a></div><div class="ttdeci">C::size_type circulator_size(C c)</div></div>
</div><!-- fragment --><h2><a class="anchor" id="PolyhedronExampleUsingEulerOperatorstoBuild"></a>
Example Using Euler Operators to Build a Cube</h2>
<p><a class="elRef" href="../BGL/group__PkgBGLEulerOperations.html">Euler</a> operators are the natural way of modifying polyhedral surfaces. We provide a set of operations for polyhedra: <a class="el" href="classCGAL_1_1Polyhedron__3.html#a3ef41ae6c3be7f0894479f3dd4fe34d5">split_facet()</a>, <a class="el" href="classCGAL_1_1Polyhedron__3.html#a4f3e7c4e0800462026443a7ad0ca6db8"><code>join_facet()</code></a>, <a class="el" href="classCGAL_1_1Polyhedron__3.html#a2b17d7bd2045397167b00616f3b4d622"><code>split_vertex()</code></a>, <a class="el" href="classCGAL_1_1Polyhedron__3.html#a8edb13d0fb5748b20a8173bec85e7243"><code>join_vertex()</code></a>, <a class="el" href="classCGAL_1_1Polyhedron__3.html#a375a1b49bc6ad2ad5c578d7a7c45e4f5"><code>split_loop()</code></a>, and <a class="el" href="classCGAL_1_1Polyhedron__3.html#ad5a29fe94196629193da3c95e5eba5e9"><code>join_loop()</code></a>. We add further convenient operators, such as <a class="el" href="classCGAL_1_1Polyhedron__3.html#ab3269baf4b4c6ce61b86545b8fa360d2"><code>split_edge()</code></a>. However, they could be implemented using the six operators above. Furthermore, we provide more operators to work with polyhedral surfaces with border edges, for example, creating and deleting holes. We refer to the references manual for the definition and illustrative figures of the <a class="elRef" href="../BGL/group__PkgBGLEulerOperations.html">Euler</a> operators.</p>
<p>The following example implements a function that appends a unit cube to a polyhedral surface. To keep track of the different steps during the creation of the cube a sequence of sketches might help with labels for the different handles that occur in the program code. The following Figure shows six selected steps from the creation sequence. These steps are also marked in the program code.</p>
<div class="image">
<img src="make_cube.png" alt="">
</div>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_cube_8cpp-example.html">Polyhedron/polyhedron_prog_cube.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <iostream></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> Poly></div>
<div class="line"><span class="keyword">typename</span> Poly::Halfedge_handle make_cube_3( Poly& P) {</div>
<div class="line"> <span class="comment">// appends a cube of size [0,1]^3 to the polyhedron P.</span></div>
<div class="line"> CGAL_precondition( P.is_valid());</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> Poly::Point_3 Point;</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> Poly::Halfedge_handle Halfedge_handle;</div>
<div class="line"> Halfedge_handle h = P.make_tetrahedron( Point( 1, 0, 0),</div>
<div class="line"> Point( 0, 0, 1),</div>
<div class="line"> Point( 0, 0, 0),</div>
<div class="line"> Point( 0, 1, 0));</div>
<div class="line"> Halfedge_handle g = h->next()->opposite()->next(); <span class="comment">// Fig. (a)</span></div>
<div class="line"> P.split_edge( h->next());</div>
<div class="line"> P.split_edge( g->next());</div>
<div class="line"> P.split_edge( g); <span class="comment">// Fig. (b)</span></div>
<div class="line"> h->next()->vertex()->point() = Point( 1, 0, 1);</div>
<div class="line"> g->next()->vertex()->point() = Point( 0, 1, 1);</div>
<div class="line"> g->opposite()->vertex()->point() = Point( 1, 1, 0); <span class="comment">// Fig. (c)</span></div>
<div class="line"> Halfedge_handle f = P.split_facet( g->next(),</div>
<div class="line"> g->next()->next()->next()); <span class="comment">// Fig. (d)</span></div>
<div class="line"> Halfedge_handle e = P.split_edge( f);</div>
<div class="line"> e->vertex()->point() = Point( 1, 1, 1); <span class="comment">// Fig. (e)</span></div>
<div class="line"> P.split_facet( e, f->next()->next()); <span class="comment">// Fig. (f)</span></div>
<div class="line"> CGAL_postcondition( P.is_valid());</div>
<div class="line"> <span class="keywordflow">return</span> h;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Halfedge_handle Halfedge_handle;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Polyhedron P;</div>
<div class="line"> Halfedge_handle h = make_cube_3( P);</div>
<div class="line"> <span class="keywordflow">return</span> (P.is_tetrahedron(h) ? 1 : 0);</div>
<div class="line">}</div>
</div><!-- fragment --><h2><a class="anchor" id="PolyhedronDraw"></a>
Draw a Polyhedron</h2>
<p><a class="anchor" id="ssecDrawPolyhedron"></a> A polyhedron can be visualized by calling the <a class="el" href="group__PkgDrawPolyhedron.html">CGAL::draw<POLY>() </a> function as shown in the following example. This function opens a new window showing the given polyhedron. A call to this function is blocking, that is the program continues as soon as the user closes the window.</p>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2draw_polyhedron_8cpp-example.html">Polyhedron/draw_polyhedron.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Exact_predicates_inexact_constructions_kernel.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/IO/Polyhedron_iostream.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/draw_polyhedron.h></span></div>
<div class="line"><span class="preprocessor">#include <fstream></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classCGAL_1_1Exact__predicates__inexact__constructions__kernel.html">CGAL::Exact_predicates_inexact_constructions_kernel</a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main(<span class="keywordtype">int</span> argc, <span class="keywordtype">char</span>* argv[])</div>
<div class="line">{</div>
<div class="line"> Polyhedron P;</div>
<div class="line"> std::ifstream in1((argc>1)?argv[1]:<a class="code hl_functionRef" href="../Manual/namespaceCGAL.html#acdae9a147ad2a3998cc21f88bc292dac">CGAL::data_file_path</a>(<span class="stringliteral">"meshes/cross_quad.off"</span>));</div>
<div class="line"> in1 >> P;</div>
<div class="line"> <a class="code hl_function" href="group__PkgDrawPolyhedron.html#ga56a8df4559b043b885be909514e6069f">CGAL::draw</a>(P);</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">return</span> EXIT_SUCCESS;</div>
<div class="line">}</div>
<div class="ttc" id="aclassCGAL_1_1Exact__predicates__inexact__constructions__kernel_html"><div class="ttname"><a href="../Kernel_23/classCGAL_1_1Exact__predicates__inexact__constructions__kernel.html">CGAL::Exact_predicates_inexact_constructions_kernel</a></div></div>
<div class="ttc" id="agroup__PkgDrawPolyhedron_html_ga56a8df4559b043b885be909514e6069f"><div class="ttname"><a href="group__PkgDrawPolyhedron.html#ga56a8df4559b043b885be909514e6069f">CGAL::draw</a></div><div class="ttdeci">void draw(const P &p, const GSOptions &gso)</div><div class="ttdoc">opens a new window and draws a polyhedron.</div></div>
<div class="ttc" id="anamespaceCGAL_html_acdae9a147ad2a3998cc21f88bc292dac"><div class="ttname"><a href="../Manual/namespaceCGAL.html#acdae9a147ad2a3998cc21f88bc292dac">CGAL::data_file_path</a></div><div class="ttdeci">std::string data_file_path(const std::string &filename)</div></div>
</div><!-- fragment --><p>This function requires <code>CGAL_Qt6</code>, and is only available if the macro <code>CGAL_USE_BASIC_VIEWER</code> is defined. Linking with the cmake target <code>CGAL::CGAL_Basic_viewer</code> will link with <code>CGAL_Qt6</code> and add the definition <code>CGAL_USE_BASIC_VIEWER</code>.</p>
<p><a class="anchor" id="fig__fig_draw_polyhedron"></a> </p><div class="image">
<img src="draw_polyhedron.png" alt="">
</div>
<div class="cgal_figure_caption"> <p> <a class="el" href="index.html#fig__fig_draw_polyhedron">Figure 26.1</a> Result of the run of the draw_polyhedron program. A window shows the polyhedron and allows to navigate through the 3D scene. </p> </div> <p> <br>
</p>
<h1><a class="anchor" id="PolyhedronFile"></a>
File I/O</h1>
<p><a class="anchor" id="sectionPolyIO"></a> The file I/O currently considers only the topology of the surface and its point coordinates. It ignores a possible plane equation or any user-added attributes, such as color.</p>
<p>The default file format supported in CGAL for output as well as for input is the <a class="elRef" href="../Stream_support/IOStreamSupportedFileFormats.html#IOStreamOFF">Object File Format (OFF)</a>, with file extension <code>.off</code>. The modifier <code>set_pretty_mode()</code> can be used to allow for (a few) structuring comments in the output. Otherwise, the output would be free of comments. The default for writing is without comments. Since this file format is the default format, iostream operators are provided for it.</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/IO/Polyhedron_iostream.h></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> PolyhedronTraits_3></div>
<div class="line">ostream& <a class="code hl_functionRef" href="../Stream_support/group__IOstreamOperators.html#gab63c7e66d05c61b2cafb1f85fd8bb3f7">operator<<</a>( ostream& out,</div>
<div class="line"><span class="keyword">const</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<PolyhedronTraits_3></a>& P);</div>
<div class="line"> </div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> PolyhedronTraits_3></div>
<div class="line">istream& <a class="code hl_functionRef" href="../Stream_support/group__IOstreamOperators.html#ga2e62094cfede6ee53227479cd7250883">operator>></a>( istream& in,</div>
<div class="line"><a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<PolyhedronTraits_3></a>& P);</div>
<div class="ttc" id="agroup__IOstreamOperators_html_ga2e62094cfede6ee53227479cd7250883"><div class="ttname"><a href="../Stream_support/group__IOstreamOperators.html#ga2e62094cfede6ee53227479cd7250883">CGAL::operator>></a></div><div class="ttdeci">istream & operator>>(istream &is, Class c)</div></div>
<div class="ttc" id="agroup__IOstreamOperators_html_gab63c7e66d05c61b2cafb1f85fd8bb3f7"><div class="ttname"><a href="../Stream_support/group__IOstreamOperators.html#gab63c7e66d05c61b2cafb1f85fd8bb3f7">CGAL::operator<<</a></div><div class="ttdeci">ostream & operator<<(ostream &os, Class c)</div></div>
</div><!-- fragment --><p>Additional formats supported for writing are OpenInventor (<code>.iv</code>) <a class="el" href="citelist.html#CITEREF_cgal:w-impoo-94">[7]</a>, VRML 1.0 and 2.0 (<code>.wrl</code>) <a class="el" href="citelist.html#CITEREF_cgal:bpp-vrml-95">[1]</a>, <a class="el" href="citelist.html#CITEREF_cgal:vrmls-97">[6]</a>, <a class="el" href="citelist.html#CITEREF_cgal:hw-vrml2h-96">[2]</a>, and <a class="elRef" href="../Stream_support/IOStreamSupportedFileFormats.html#IOStreamOBJ">Wavefront Advanced Visualizer Object Format (OBJ)</a> (<code>.obj</code>). These output functions are provided as stream operators, now acting on the stream type of the respective format.</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/IO/Polyhedron_inventor_ostream.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/IO/Polyhedron_VRML_1_ostream.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/IO/Polyhedron_VRML_2_ostream.h></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> PolyhedronTraits_3></div>
<div class="line">Inventor_ostream& <a class="code hl_functionRef" href="../Stream_support/group__IOstreamOperators.html#gab63c7e66d05c61b2cafb1f85fd8bb3f7">operator<<</a>( Inventor_ostream& out,</div>
<div class="line"><span class="keyword">const</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<PolyhedronTraits_3></a>& P);</div>
<div class="line"> </div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> PolyhedronTraits_3></div>
<div class="line">VRML_1_ostream& <a class="code hl_functionRef" href="../Stream_support/group__IOstreamOperators.html#gab63c7e66d05c61b2cafb1f85fd8bb3f7">operator<<</a>( VRML_1_ostream& out,</div>
<div class="line"><span class="keyword">const</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<PolyhedronTraits_3></a>& P);</div>
<div class="line"> </div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> PolyhedronTraits_3></div>
<div class="line">VRML_2_ostream& <a class="code hl_functionRef" href="../Stream_support/group__IOstreamOperators.html#gab63c7e66d05c61b2cafb1f85fd8bb3f7">operator<<</a>( VRML_2_ostream& out,</div>
<div class="line"><span class="keyword">const</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<PolyhedronTraits_3></a>& P);</div>
</div><!-- fragment --><p>All these file formats have in common that they represent a surface as a set of facets. Each facet is a list of indices pointing into a set of vertices. Vertices are represented as coordinate triples. The file I/O for polyhedral surfaces <code><a class="el" href="classCGAL_1_1Polyhedron__3.html" title="A polyhedral surface Polyhedron_3 consists of vertices V, edges E, facets F and an incidence relation...">Polyhedron_3</a></code> imposes certain restrictions on these formats. They must represent a permissible polyhedral surface, e.g., a 2-manifold and no isolated vertices, see Section <a class="el" href="index.html#sectionPolyIntro">Introduction</a>.</p>
<p>For more information on generic polygon meshes I/O, see the section <a class="elRef" href="../Stream_support/index.html#IOstreamPolygonMeshIO">Polygon Mesh IO</a>.</p>
<h1><a class="anchor" id="PolyhedronExtending"></a>
Extending Vertices, Halfedges, and Facets</h1>
<p><a class="anchor" id="sectionPolyExtend"></a> In Section <a class="el" href="index.html#sectionPolyVector">Example with a Vector Instead of a List Representation</a> we have seen how to change the default list representation</p>
<div class="fragment"><div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3</a>< Traits,</div>
<div class="line"><a class="code hl_class" href="classCGAL_1_1Polyhedron__items__3.html">CGAL::Polyhedron_items_3</a>,</div>
<div class="line"><a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__default.html">CGAL::HalfedgeDS_default</a>> Polyhedron;</div>
</div><!-- fragment --><p>to a vector based representation of the underlying halfedge data structure. Now we want to look a bit closer at the second template argument, <code><a class="el" href="classCGAL_1_1Polyhedron__items__3.html" title="The class Polyhedron_items_3 is a model of the PolyhedronItems_3 concept.">Polyhedron_items_3</a></code>, that specifies what kind of vertex, halfedge, and facet is used. The implementation of <code><a class="el" href="classCGAL_1_1Polyhedron__items__3.html" title="The class Polyhedron_items_3 is a model of the PolyhedronItems_3 concept.">Polyhedron_items_3</a></code> looks a bit involved with nested wrapper class templates. But ignoring this technicality, what remains are three local typedefs that define the <code>Vertex</code>, the <code>Halfedge</code>, and the <code>Face</code> for the polyhedral surface. Note that we use here <code>Face</code> instead of facet. Face is the term used for the halfedge data structure. Only the top layer of the polyhedral surface gives alias names renaming face to facet.</p>
<div class="fragment"><div class="line"><span class="keyword">class </span>Polyhedron_items_3 {</div>
<div class="line"><span class="keyword">public</span>:</div>
<div class="line"> <span class="keyword">template</span> < <span class="keyword">class</span> Refs, <span class="keyword">class</span> Traits></div>
<div class="line"> <span class="keyword">struct </span>Vertex_wrapper {</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> Traits::Point_3 Point;</div>
<div class="line"> <span class="keyword">typedef</span> <a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__vertex__base.html">CGAL::HalfedgeDS_vertex_base<Refs, CGAL::Tag_true, Point></a> Vertex;</div>
<div class="line"> };</div>
<div class="line"> <span class="keyword">template</span> < <span class="keyword">class</span> Refs, <span class="keyword">class</span> Traits></div>
<div class="line"> <span class="keyword">struct </span>Halfedge_wrapper {</div>
<div class="line"> <span class="keyword">typedef</span> <a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__halfedge__base.html">CGAL::HalfedgeDS_halfedge_base<Refs></a> Halfedge;</div>
<div class="line"> };</div>
<div class="line"> <span class="keyword">template</span> < <span class="keyword">class</span> Refs, <span class="keyword">class</span> Traits></div>
<div class="line"> <span class="keyword">struct </span>Face_wrapper {</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> Traits::Plane_3 Plane;</div>
<div class="line"> <span class="keyword">typedef</span> <a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__face__base.html">CGAL::HalfedgeDS_face_base<Refs, CGAL::Tag_true, Plane></a> Face;</div>
<div class="line"> };</div>
<div class="line">};</div>
<div class="ttc" id="aclassCGAL_1_1HalfedgeDS__face__base_html"><div class="ttname"><a href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__face__base.html">CGAL::HalfedgeDS_face_base</a></div></div>
<div class="ttc" id="aclassCGAL_1_1HalfedgeDS__halfedge__base_html"><div class="ttname"><a href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__halfedge__base.html">CGAL::HalfedgeDS_halfedge_base</a></div></div>
<div class="ttc" id="aclassCGAL_1_1HalfedgeDS__vertex__base_html"><div class="ttname"><a href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__vertex__base.html">CGAL::HalfedgeDS_vertex_base</a></div></div>
</div><!-- fragment --><p>If we look up in the reference manual the definitions of the three classes used in the typedefs, we will see the confirmation that the default polyhedron uses all supported incidences, a point in the vertex class, and a plane equation in the face class. Note how the wrapper class provides two template parameters, <code>Refs</code>, which we discuss a bit later, and <code>Traits</code>, which is the geometric traits class used by the polyhedral surface and which provides us here with the types for the point and the plane equation.</p>
<p>Using this example code we can write our own items class. Instead, we illustrate an easier way if we only want to exchange one class. We use a simpler face without the plane equation but with a color attribute added. To simplify the creation of a vertex, halfedge, or face class, it is always recommended to derive from one of the given base classes. Even if the base class would contain no data it would provide convenient type definitions. So, we derive from the base class, repeat the mandatory constructors if necessary - which is not the case for faces but would be for vertices - and add the color attribute.</p>
<div class="fragment"><div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> Refs></div>
<div class="line"><span class="keyword">struct </span>My_face : <span class="keyword">public</span> <a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__face__base.html">CGAL::HalfedgeDS_face_base</a><Refs> {</div>
<div class="line"> <a class="code hl_classRef" href="../Stream_support/classCGAL_1_1IO_1_1Color.html">CGAL::IO::Color</a> color;</div>
<div class="line">};</div>
<div class="ttc" id="aclassCGAL_1_1IO_1_1Color_html"><div class="ttname"><a href="../Stream_support/classCGAL_1_1IO_1_1Color.html">CGAL::IO::Color</a></div></div>
</div><!-- fragment --><p>The new items class is derived from the old items class and the wrapper containing the face typedef gets overridden. Note that the name of the wrapper and its template parameters are fixed. They cannot be changed even if, as in this example, a template parameter is not used.</p>
<div class="fragment"><div class="line"><span class="keyword">struct </span>My_items : <span class="keyword">public</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__items__3.html">CGAL::Polyhedron_items_3</a> {</div>
<div class="line"> <span class="keyword">template</span> <<span class="keyword">class</span> Refs, <span class="keyword">class</span> Traits></div>
<div class="line"> <span class="keyword">struct </span>Face_wrapper {</div>
<div class="line"> <span class="keyword">typedef</span> My_face<Refs> Face;</div>
<div class="line"> };</div>
<div class="line">};</div>
</div><!-- fragment --><p>When we use our new items class with the polyhedral surface, our new face class is used in the halfedge data structure and the color attribute is available in the type <code><a class="el" href="classCGAL_1_1Polyhedron__3_1_1Facet.html" title="A facet optionally stores a plane equation, and a reference to an incident halfedge that points to th...">Polyhedron_3::Facet</a></code>. However, <code><a class="el" href="classCGAL_1_1Polyhedron__3_1_1Facet.html" title="A facet optionally stores a plane equation, and a reference to an incident halfedge that points to th...">Polyhedron_3::Facet</a></code> is not the same type as our local face typedef for <code>My_face</code>, but it is derived there from. Thus, everything that we put in the local face type except constructors is then available in the <code>Polyhedron_::Facet</code> type. For more details, see the Chapter <a class="elRef" href="../HalfedgeDS/index.html#chapterHalfedgeDS">Halfedge Data Structures</a> on the halfedge data structure design.</p>
<p>Pulling all pieces together, the full example program illustrates how easy the color attribute can be accessed once it is defined.</p>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_color_8cpp-example.html">Polyhedron/polyhedron_prog_color.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/IO/Color.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"> </div>
<div class="line"><span class="comment">// A face type with a color member variable.</span></div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> Refs></div>
<div class="line"><span class="keyword">struct </span>My_face : <span class="keyword">public</span> <a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__face__base.html">CGAL::HalfedgeDS_face_base</a><Refs> {</div>
<div class="line"> <a class="code hl_classRef" href="../Stream_support/classCGAL_1_1IO_1_1Color.html">CGAL::IO::Color</a> color;</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="comment">// An items type using my face.</span></div>
<div class="line"><span class="keyword">struct </span>My_items : <span class="keyword">public</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__items__3.html">CGAL::Polyhedron_items_3</a> {</div>
<div class="line"> <span class="keyword">template</span> <<span class="keyword">class</span> Refs, <span class="keyword">class</span> Traits></div>
<div class="line"> <span class="keyword">struct </span>Face_wrapper {</div>
<div class="line"> <span class="keyword">typedef</span> My_face<Refs> Face;</div>
<div class="line"> };</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel, My_items></a> Polyhedron;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Halfedge_handle Halfedge_handle;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Polyhedron P;</div>
<div class="line"> Halfedge_handle h = P.<a class="code hl_function" href="classCGAL_1_1Polyhedron__3.html#a1ebc714bb6fc75a8aa105ffb241fe087">make_tetrahedron</a>();</div>
<div class="line"> h->facet()->color = CGAL::IO::red();</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
</div><!-- fragment --><p>We come back to the first template parameter, <code>Refs</code>, of the wrapper classes. This parameter provides us with local types that allow us to make further references between vertices, halfedges, and facets, which have not already been prepared for in the current design. These local types are <code><a class="el" href="classCGAL_1_1Polyhedron__3.html#aca51106e581d51d36bd668c819c0ac4e" title="handle to vertex.">Polyhedron_3::Vertex_handle</a></code>, <code><a class="el" href="classCGAL_1_1Polyhedron__3.html#a5ea0a8e088c2e98a6f1312d32f0a4967" title="handle to halfedge.">Polyhedron_3::Halfedge_handle</a></code>, <code><a class="el" href="classCGAL_1_1Polyhedron__3.html#ad44731fbb60766ae1ea8e46b69d3cbbf" title="handle to facet.">Polyhedron_3::Facet_handle</a></code>, and there respective <code>.._const_handle</code>. We add now a new vertex reference to a face class as follows. Encapsulation and access functions could be added for a more thorough design, but we omit that here for the sake of brevity. The integration of the face class with the items class works as illustrated above.</p>
<div class="fragment"><div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> Refs></div>
<div class="line"><span class="keyword">struct </span>My_face : <span class="keyword">public</span> <a class="code hl_classRef" href="../HalfedgeDS/classCGAL_1_1HalfedgeDS__face__base.html">CGAL::HalfedgeDS_face_base</a><Refs> {</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> Refs::Vertex_handle Vertex_handle;</div>
<div class="line"> Vertex_handle vertex_ref;</div>
<div class="line">};</div>
</div><!-- fragment --><p>More advanced examples can be found in the Section <a class="elRef" href="../HalfedgeDS/index.html#sectionHdsExamples">sectionHdsExamples</a> illustrating further the design of the halfedge data structure.</p>
<h1><a class="anchor" id="PolyhedronAdvanced"></a>
Advanced Example Programs</h1>
<p><a class="anchor" id="sectionPolyAdvanced"></a> </p>
<h2><a class="anchor" id="PolyhedronExampleCreatingaSubdivisionSurface"></a>
Example Creating a Subdivision Surface</h2>
<p>This program reads a polyhedral surface from the standard input and writes a refined polyhedral surface to the standard output. Input and output are in the Object File Format, OFF, with the common file extension <code>.off</code>.</p>
<p>The refinement is a single step of the \( \sqrt{3}\)-scheme for creating a subdivision surface <a class="el" href="citelist.html#CITEREF_cgal:k-s-00">[4]</a>. Each step subdivides a facet into triangles around a new center vertex, smoothes the position of the old vertices, and flips the old edges. The program is organized along this outline. In each of these parts, the program efficiently uses the knowledge that the newly created vertices, edges, and facets have been added to the end of the sequences. The program needs additional processing memory only for the smoothing step of the old vertices.</p>
<div class="image">
<img src="subdiv_small.png" alt="">
</div>
<p>The above figure shows three example objects, each subdivided four times. The initial object for the left sequence is the closed surface of three unit cubes glued together to a corner. The example program shown here can handle only closed surfaces, but the extended example <code>examples/Polyhedron/polyhedron_prog_subdiv_with_boundary.cpp</code> handles surfaces with boundary. So, the middle sequence starts with the same surface where one of the facets has been removed. The boundary subdivides to a nice circle. The third sequence creates a sharp edge using a trick in the object presentation. The sharp edge is actually a hole whose vertex coordinates pinch the hole shut to form an edge. The example directory <code>examples/Polyhedron/</code> contains the OFF files used here.</p>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_subdiv_8cpp-example.html">Polyhedron/polyhedron_prog_subdiv.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <iostream></span></div>
<div class="line"><span class="preprocessor">#include <algorithm></span></div>
<div class="line"><span class="preprocessor">#include <vector></span></div>
<div class="line"><span class="preprocessor">#include <cmath></span></div>
<div class="line"><span class="preprocessor">#include <fstream></span></div>
<div class="line"><span class="preprocessor">#include <cassert></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classKernel_1_1Vector__3.html">Kernel::Vector_3</a> Vector;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_classRef" href="../Kernel_23/classKernel_1_1Point__3.html">Kernel::Point_3</a> Point;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Vertex Vertex;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Vertex_iterator Vertex_iterator;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Halfedge_handle Halfedge_handle;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Edge_iterator Edge_iterator;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Facet_iterator Facet_iterator;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Halfedge_around_vertex_const_circulator HV_circulator;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::Halfedge_around_facet_circulator HF_circulator;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">void</span> create_center_vertex( Polyhedron& P, Facet_iterator f) {</div>
<div class="line"> Vector vec( 0.0, 0.0, 0.0);</div>
<div class="line"> std::size_t order = 0;</div>
<div class="line"> HF_circulator h = f->facet_begin();</div>
<div class="line"> <span class="keywordflow">do</span> {</div>
<div class="line"> vec = vec + ( h->vertex()->point() - <a class="code hl_variableRef" href="../Kernel_23/group__kernel__enums.html#ga9d272a8e3a8080b851741b6d3a44afdc">CGAL::ORIGIN</a>);</div>
<div class="line"> ++ order;</div>
<div class="line"> } <span class="keywordflow">while</span> ( ++h != f->facet_begin());</div>
<div class="line"> assert( order >= 3); <span class="comment">// guaranteed by definition of polyhedron</span></div>
<div class="line"> Point center = <a class="code hl_variableRef" href="../Kernel_23/group__kernel__enums.html#ga9d272a8e3a8080b851741b6d3a44afdc">CGAL::ORIGIN</a> + (vec / <span class="keyword">static_cast<</span><span class="keywordtype">double</span><span class="keyword">></span>(order));</div>
<div class="line"> Halfedge_handle new_center = P.create_center_vertex( f->halfedge());</div>
<div class="line"> new_center->vertex()->point() = center;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keyword">struct </span>Smooth_old_vertex {</div>
<div class="line"> Point operator()( <span class="keyword">const</span> Vertex& v)<span class="keyword"> const </span>{</div>
<div class="line"> CGAL_precondition((<a class="code hl_functionRef" href="../Circulator/group__PkgHandlesAndCirculatorsFunctions.html#ga2d7bfa21e8eb046b8ae90104aa4fcce4">CGAL::circulator_size</a>( v.vertex_begin()) & 1) == 0);</div>
<div class="line"> std::size_t degree = <a class="code hl_functionRef" href="../Circulator/group__PkgHandlesAndCirculatorsFunctions.html#ga2d7bfa21e8eb046b8ae90104aa4fcce4">CGAL::circulator_size</a>( v.vertex_begin()) / 2;</div>
<div class="line"> <span class="keywordtype">double</span> alpha = ( 4.0 - 2.0 * std::cos( 2.0 * CGAL_PI / degree)) / 9.0;</div>
<div class="line"> Vector vec = (v.point() - <a class="code hl_variableRef" href="../Kernel_23/group__kernel__enums.html#ga9d272a8e3a8080b851741b6d3a44afdc">CGAL::ORIGIN</a>) * ( 1.0 - alpha);</div>
<div class="line"> HV_circulator h = v.vertex_begin();</div>
<div class="line"> <span class="keywordflow">do</span> {</div>
<div class="line"> vec = vec + ( h->opposite()->vertex()->point() - <a class="code hl_variableRef" href="../Kernel_23/group__kernel__enums.html#ga9d272a8e3a8080b851741b6d3a44afdc">CGAL::ORIGIN</a>)</div>
<div class="line"> * alpha / <span class="keyword">static_cast<</span><span class="keywordtype">double</span><span class="keyword">></span>(degree);</div>
<div class="line"> ++ h;</div>
<div class="line"> assert( h != v.vertex_begin()); <span class="comment">// even degree guaranteed</span></div>
<div class="line"> ++ h;</div>
<div class="line"> } <span class="keywordflow">while</span> ( h != v.vertex_begin());</div>
<div class="line"> <span class="keywordflow">return</span> (<a class="code hl_variableRef" href="../Kernel_23/group__kernel__enums.html#ga9d272a8e3a8080b851741b6d3a44afdc">CGAL::ORIGIN</a> + vec);</div>
<div class="line"> }</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">void</span> <a class="code hl_functionRef" href="../BGL/group__PkgBGLEulerOperations.html#ga174af506cebf3def60b56a3501843864">flip_edge</a>( Polyhedron& P, Halfedge_handle e) {</div>
<div class="line"> Halfedge_handle h = e->next();</div>
<div class="line"> P.join_facet( e);</div>
<div class="line"> P.split_facet( h, h->next()->next());</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">void</span> subdiv( Polyhedron& P) {</div>
<div class="line"> <span class="keywordflow">if</span> ( P.size_of_facets() == 0)</div>
<div class="line"> <span class="keywordflow">return</span>;</div>
<div class="line"> <span class="comment">// We use that new vertices/halfedges/facets are appended at the end.</span></div>
<div class="line"> std::size_t nv = P.size_of_vertices();</div>
<div class="line"> Vertex_iterator last_v = P.vertices_end();</div>
<div class="line"> -- last_v; <span class="comment">// the last of the old vertices</span></div>
<div class="line"> Edge_iterator last_e = P.edges_end();</div>
<div class="line"> -- last_e; <span class="comment">// the last of the old edges</span></div>
<div class="line"> Facet_iterator last_f = P.facets_end();</div>
<div class="line"> -- last_f; <span class="comment">// the last of the old facets</span></div>
<div class="line"> </div>
<div class="line"> Facet_iterator f = P.facets_begin(); <span class="comment">// create new center vertices</span></div>
<div class="line"> <span class="keywordflow">do</span> {</div>
<div class="line"> create_center_vertex( P, f);</div>
<div class="line"> } <span class="keywordflow">while</span> ( f++ != last_f);</div>
<div class="line"> </div>
<div class="line"> std::vector<Point> pts; <span class="comment">// smooth the old vertices</span></div>
<div class="line"> pts.reserve( nv); <span class="comment">// get intermediate space for the new points</span></div>
<div class="line"> ++ last_v; <span class="comment">// make it the past-the-end position again</span></div>
<div class="line"> std::transform( P.vertices_begin(), last_v, std::back_inserter( pts),</div>
<div class="line"> Smooth_old_vertex());</div>
<div class="line"> std::copy( pts.begin(), pts.end(), P.points_begin());</div>
<div class="line"> </div>
<div class="line"> Edge_iterator e = P.edges_begin(); <span class="comment">// flip the old edges</span></div>
<div class="line"> ++ last_e; <span class="comment">// make it the past-the-end position again</span></div>
<div class="line"> <span class="keywordflow">while</span> ( e != last_e) {</div>
<div class="line"> Halfedge_handle h = e;</div>
<div class="line"> ++e; <span class="comment">// careful, incr. before flip since flip destroys current edge</span></div>
<div class="line"> <a class="code hl_functionRef" href="../BGL/group__PkgBGLEulerOperations.html#ga174af506cebf3def60b56a3501843864">flip_edge</a>( P, h);</div>
<div class="line"> };</div>
<div class="line"> CGAL_postcondition( P.is_valid());</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main(<span class="keywordtype">int</span> argc, <span class="keywordtype">char</span>* argv[]) {</div>
<div class="line"> Polyhedron P;</div>
<div class="line"> std::ifstream in1((argc>1)?argv[1]:<a class="code hl_functionRef" href="../Manual/namespaceCGAL.html#acdae9a147ad2a3998cc21f88bc292dac">CGAL::data_file_path</a>(<span class="stringliteral">"meshes/cube_quad.off"</span>));</div>
<div class="line"> in1 >> P;</div>
<div class="line"> P.normalize_border();</div>
<div class="line"> <span class="keywordflow">if</span> ( P.size_of_border_edges() != 0) {</div>
<div class="line"> std::cerr << <span class="stringliteral">"The input object has border edges. Cannot subdivide."</span></div>
<div class="line"> << std::endl;</div>
<div class="line"> std::exit(1);</div>
<div class="line"> }</div>
<div class="line"> subdiv( P);</div>
<div class="line"> std::cout << std::setprecision(17) << P;</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclassKernel_1_1Vector__3_html"><div class="ttname"><a href="../Kernel_23/classKernel_1_1Vector__3.html">Kernel::Vector_3</a></div></div>
<div class="ttc" id="agroup__PkgBGLEulerOperations_html_ga174af506cebf3def60b56a3501843864"><div class="ttname"><a href="../BGL/group__PkgBGLEulerOperations.html#ga174af506cebf3def60b56a3501843864">CGAL::Euler::flip_edge</a></div><div class="ttdeci">void flip_edge(typename boost::graph_traits< Graph >::halfedge_descriptor h, Graph &g)</div></div>
<div class="ttc" id="agroup__kernel__enums_html_ga9d272a8e3a8080b851741b6d3a44afdc"><div class="ttname"><a href="../Kernel_23/group__kernel__enums.html#ga9d272a8e3a8080b851741b6d3a44afdc">CGAL::ORIGIN</a></div><div class="ttdeci">const CGAL::Origin ORIGIN</div></div>
</div><!-- fragment --><h2><a class="anchor" id="PolyhedronExampleUsingtheIncrementalBuilder"></a>
Example Using the Incremental Builder and Modifier Mechanism</h2>
<p>A utility class <code><a class="el" href="classCGAL_1_1Polyhedron__incremental__builder__3.html" title="The auxiliary class Polyhedron_incremental_builder_3 supports the incremental construction of polyhed...">Polyhedron_incremental_builder_3</a></code> helps in creating polyhedral surfaces from a list of points followed by a list of facets that are represented as indices into the point list. This is particularly useful for implementing file reader for common file formats. It is used here to create a triangle.</p>
<p>A modifier mechanism allows to access the internal representation of the polyhedral surface, i.e., the halfedge data structure, in a controlled manner. A modifier is basically a callback mechanism using a function object. When called, the function object receives the internal halfedge data structure as a parameter and can modify it. On return, the polyhedron can check the halfedge data structure for validity. Such a modifier object must always return with a halfedge data structure that is a valid polyhedral surface. The validity check is implemented as an expensive postcondition at the end of the <code><a class="el" href="classCGAL_1_1Polyhedron__3.html#a7d5683b471d99bff3d73a467688151c5" title="This is an advanced function.">Polyhedron_3::delegate()</a></code> member function, i.e., it is not called by default, only when expensive checks are activated.</p>
<p>In this example, <code>Build_triangle</code> is such a function object derived from <code><a class="elRef" href="../Miscellany/classCGAL_1_1Modifier__base.html">Modifier_base</a><<a class="elRef" href="../HalfedgeDS/classHalfedgeDS.html">HalfedgeDS</a>></code>. The <code><a class="el" href="classCGAL_1_1Polyhedron__3.html#a7d5683b471d99bff3d73a467688151c5" title="This is an advanced function.">Polyhedron_3::delegate()</a></code> member function of the polyhedron accepts this function object and calls its <code><a class="elRef" href="../Miscellany/classCGAL_1_1Modifier__base.html#a08a0a229b834229b3d35c8fb122cb488">Modifier_base::operator()()</a></code> with a reference to its internally used halfedge data structure. Thus, this member function in <code>Build_triangle</code> can create the triangle in the halfedge data structure.</p>
<p><br>
<b>File</b> <a class="el" href="Polyhedron_2polyhedron_prog_incr_builder_8cpp-example.html">Polyhedron/polyhedron_prog_incr_builder.cpp</a> </p><div class="fragment"><div class="line"><span class="preprocessor">#include <CGAL/Simple_cartesian.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_incremental_builder_3.h></span></div>
<div class="line"><span class="preprocessor">#include <CGAL/Polyhedron_3.h></span></div>
<div class="line"><span class="preprocessor">#include <cassert></span></div>
<div class="line"> </div>
<div class="line"><span class="comment">// A modifier creating a triangle with the incremental builder.</span></div>
<div class="line"><span class="keyword">template</span> <<span class="keyword">class</span> HDS></div>
<div class="line"><span class="keyword">class </span>Build_triangle : <span class="keyword">public</span> <a class="code hl_classRef" href="../Miscellany/classCGAL_1_1Modifier__base.html">CGAL::Modifier_base</a><HDS> {</div>
<div class="line"><span class="keyword">public</span>:</div>
<div class="line"> Build_triangle() {}</div>
<div class="line"> <span class="keywordtype">void</span> operator()( HDS& hds) {</div>
<div class="line"> <span class="comment">// Postcondition: hds is a valid polyhedral surface.</span></div>
<div class="line"> <a class="code hl_class" href="classCGAL_1_1Polyhedron__incremental__builder__3.html">CGAL::Polyhedron_incremental_builder_3<HDS></a> B( hds, <span class="keyword">true</span>);</div>
<div class="line"> B.begin_surface( 3, 1, 6);</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> HDS::Vertex Vertex;</div>
<div class="line"> <span class="keyword">typedef</span> <span class="keyword">typename</span> Vertex::Point Point;</div>
<div class="line"> B.add_vertex( Point( 0, 0, 0));</div>
<div class="line"> B.add_vertex( Point( 1, 0, 0));</div>
<div class="line"> B.add_vertex( Point( 0, 1, 0));</div>
<div class="line"> B.begin_facet();</div>
<div class="line"> B.add_vertex_to_facet( 0);</div>
<div class="line"> B.add_vertex_to_facet( 1);</div>
<div class="line"> B.add_vertex_to_facet( 2);</div>
<div class="line"> B.end_facet();</div>
<div class="line"> B.end_surface();</div>
<div class="line"> }</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_structRef" href="../Kernel_23/structCGAL_1_1Simple__cartesian.html">CGAL::Simple_cartesian<double></a> <a class="code hl_namespaceRef" href="../Kernel_23/namespaceKernel.html">Kernel</a>;</div>
<div class="line"><span class="keyword">typedef</span> <a class="code hl_class" href="classCGAL_1_1Polyhedron__3.html">CGAL::Polyhedron_3<Kernel></a> Polyhedron;</div>
<div class="line"><span class="keyword">typedef</span> Polyhedron::HalfedgeDS <a class="code hl_classRef" href="../HalfedgeDS/classHalfedgeDS.html">HalfedgeDS</a>;</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> Polyhedron P;</div>
<div class="line"> Build_triangle<HalfedgeDS> <a class="code hl_functionRef" href="../Polygon_mesh_processing/group__PkgPolygonMeshProcessingRef.html#ga0542a44d0d081f84e387b1e6bcbca471">triangle</a>;</div>
<div class="line"> P.delegate( triangle);</div>
<div class="line"> assert( P.is_triangle( P.halfedges_begin()));</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclassCGAL_1_1Modifier__base_html"><div class="ttname"><a href="../Miscellany/classCGAL_1_1Modifier__base.html">CGAL::Modifier_base</a></div></div>
<div class="ttc" id="aclassCGAL_1_1Polyhedron__incremental__builder__3_html"><div class="ttname"><a href="classCGAL_1_1Polyhedron__incremental__builder__3.html">CGAL::Polyhedron_incremental_builder_3</a></div><div class="ttdoc">The auxiliary class Polyhedron_incremental_builder_3 supports the incremental construction of polyhed...</div><div class="ttdef"><b>Definition:</b> Polyhedron_incremental_builder_3.h:62</div></div>
<div class="ttc" id="aclassHalfedgeDS_html"><div class="ttname"><a href="../HalfedgeDS/classHalfedgeDS.html">HalfedgeDS</a></div></div>
<div class="ttc" id="agroup__PkgPolygonMeshProcessingRef_html_ga0542a44d0d081f84e387b1e6bcbca471"><div class="ttname"><a href="../Polygon_mesh_processing/group__PkgPolygonMeshProcessingRef.html#ga0542a44d0d081f84e387b1e6bcbca471">CGAL::Polygon_mesh_processing::triangle</a></div><div class="ttdeci">Triangle_3 triangle(typename boost::graph_traits< TriangleMesh >::face_descriptor fd, const TriangleMesh &tmesh, const NamedParameters &np=parameters::default_values())</div></div>
</div><!-- fragment --> </div></div><!-- PageDoc -->
</div><!-- contents -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.9.6-->
<!-- start footer part -->
<!-- The footer div is not part of the default but we require it to
move the footer to the bottom of the page. -->
<div id="footer">
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="footer">Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"></a> 1.9.6 </li>
</ul>
</div>
</div>
</body>
</html>