Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Strange output from Delaunay triangulation

Subject: CGAL users discussion list

List archive

[cgal-discuss] Strange output from Delaunay triangulation


Chronological Thread 
  • From: Sybren A. Stüvel <>
  • To:
  • Subject: [cgal-discuss] Strange output from Delaunay triangulation
  • Date: Fri, 25 Sep 2009 19:05:47 +0200

Hi folks,

I'm building a Delaunay triangulation in 3D. After I added 29 points
and stream the triangulation to a file I get the attached output. It
contains the 29 points and 129 cells.

The first cell consists of vertices "15 0 5 19", so I assume vertex
indices are 0 based. However, another cell consists of vertices "13 7
29 19". How can this be when there are only 29 points?

Can anyone shed some light on this? I've attached a rather minimal
test program and its output. I compiled it on Ubuntu Linux using:

g++ -fno-gnu-keywords -pedantic -Wall -Weffc++ -Wextra -std=c++98 -g
-lCGAL basetest.cpp -o basetest

but I saw the same problem on Windows XP with Visual C++ 2005 SP1.

I use CGAL 3.4.

Cheers,
--
Sybren A. Stüvel
http://stuvel.eu/
#include <fstream>

#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> 
#include <CGAL/Triangulation_vertex_base_3.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_vertex_base_3<K> Vb;
typedef CGAL::Triangulation_data_structure_3<Vb> Tds;
typedef CGAL::Delaunay_triangulation_3<K, Tds> Delaunay;

typedef Delaunay::Point Point;

int main(void)
{
    Delaunay test;
    test.insert(Point(55.1547, 36.5379, 49.1516));
    test.insert(Point(63.86, 55.1547, 100.992));
    test.insert(Point(57.8907, 63.86, 111.649));
    test.insert(Point(60.8121, 57.8907, 94.9274));
    test.insert(Point(46.1601, 60.8121, 104.413));
    test.insert(Point(55.8517, 46.1601, 73.2259));
    test.insert(Point(40.771, 55.8517, 91.3627));
    test.insert(Point(60.3013, 40.771, 43.7103));
    test.insert(Point(50.3067, 60.3013, 103.587));
    test.insert(Point(60.9116, 50.3067, 92.2153));
    test.insert(Point(49.9317, 60.9116, 99.2979));
    test.insert(Point(56.6046, 49.9317, 96.0808));
    test.insert(Point(44.0764, 56.6046, 96.231));
    test.insert(Point(55.2507, 44.0764, 65.4108));
    test.insert(Point(36.5713, 55.2507, 91.6709));
    test.insert(Point(56.5443, 36.5713, 47.718));
    test.insert(Point(38.7994, 56.5443, 94.1948));
    test.insert(Point(62.6463, 38.7994, 64.4947));
    test.insert(Point(43.0816, 62.6463, 81.8163));
    test.insert(Point(48.8893, 43.0816, 91.7621));
    test.insert(Point(51.9762, 48.8893, 65.5638));
    test.insert(Point(37.4998, 51.9762, 88.4004));
    test.insert(Point(43.625, 37.4998, 25.7617));
    test.insert(Point(33.1422, 43.625, 75.9897));
    test.insert(Point(44.029, 33.1422, 18.1048));
    test.insert(Point(44.0953, 44.029, 85.8437));
    test.insert(Point(59.0262, 44.0953, 69.3357));
    test.insert(Point(57.6675, 59.0262, 92.696));
    test.insert(Point(43.528, 57.6675, 96.9036));

    std::ofstream out("test.cgal");
    out << test;
    out.close();

    return 0;
}

3
29
55.1547 36.5379 49.1516
63.86 55.1547 100.992
57.8907 63.86 111.649
60.8121 57.8907 94.9274
46.1601 60.8121 104.413
55.8517 46.1601 73.2259
40.771 55.8517 91.3627
60.3013 40.771 43.7103
50.3067 60.3013 103.587
60.9116 50.3067 92.2153
49.9317 60.9116 99.2979
56.6046 49.9317 96.0808
44.0764 56.6046 96.231
55.2507 44.0764 65.4108
36.5713 55.2507 91.6709
56.5443 36.5713 47.718
38.7994 56.5443 94.1948
62.6463 38.7994 64.4947
43.0816 62.6463 81.8163
48.8893 43.0816 91.7621
51.9762 48.8893 65.5638
37.4998 51.9762 88.4004
43.625 37.4998 25.7617
33.1422 43.625 75.9897
44.029 33.1422 18.1048
44.0953 44.029 85.8437
59.0262 44.0953 69.3357
57.6675 59.0262 92.696
43.528 57.6675 96.9036
129
15 24 20 0
28 0 3 4
0 2 3 4
5 19 3 11
12 5 3 9
2 12 3 9
26 24 19 21
2 9 3 4
20 10 2 18
20 1 18 0
29 19 5 11
23 25 0 8
11 28 3 4
22 15 7 19
3 12 2 20
9 11 3 4
8 2 0 4
3 5 12 20
3 20 2 0
3 5 20 0
17 19 5 29
10 27 6 4
24 1 20 25
9 12 13 11
9 13 29 11
11 19 3 28
26 18 20 24
9 29 5 11
9 12 5 13
5 13 12 20
12 10 2 20
15 0 5 19
9 5 3 11
21 1 23 8
26 18 24 14
20 18 2 0
12 11 9 4
2 12 9 4
2 10 12 4
13 19 29 11
24 25 20 0
9 13 5 29
24 0 15 19
1 16 23 8
25 16 0 8
5 15 20 0
5 17 20 15
22 24 15 19
23 1 24 25
6 26 19 21
18 14 21 8
17 22 20 15
26 20 22 24
2 8 18 4
18 8 21 27
2 18 10 4
5 0 3 19
1 16 25 23
1 16 0 25
23 16 25 8
14 1 21 8
18 2 0 8
16 18 0 8
16 1 18 8
18 1 14 8
10 18 20 27
13 17 5 29
21 23 19 8
23 0 19 8
25 1 20 0
6 24 26 21
19 0 3 28
18 1 16 0
12 28 11 4
7 15 17 19
15 19 5 17
26 22 19 24
18 8 27 4
23 25 24 0
13 7 12 20
10 27 20 6
26 22 7 19
5 13 20 17
17 7 22 15
17 7 13 22
22 7 13 20
17 22 13 20
21 23 24 19
23 0 24 19
21 1 24 23
14 1 24 21
6 24 21 14
27 18 20 6
18 1 24 14
18 1 20 24
10 18 27 4
18 14 27 21
15 22 20 24
6 26 24 14
6 18 26 14
6 18 20 26
10 6 20 26
13 7 29 19
29 7 17 19
20 22 7 26
13 7 17 29
27 14 6 21
18 14 6 27
10 28 12 4
10 6 28 4
27 28 6 4
27 8 28 4
8 0 28 4
8 0 19 28
21 8 19 28
6 21 19 28
28 6 26 19
28 26 7 19
13 7 19 28
13 19 11 28
12 13 11 28
12 7 13 28
28 12 7 20
26 28 7 20
10 28 26 20
10 12 28 20
10 6 26 28
27 21 6 28
27 8 21 28
40 45 42 97
2 12 112 71
7 1 16 18
25 32 10 56
32 5 28 17
4 7 37 14
87 49 70 76
15 2 37 5
55 35 65 30
72 35 69 94
3 27 39 20
44 68 59 78
1 15 73 25
74 81 47 83
30 18 17 5
12 7 36 32
2 112 53 61
29 14 19 4
35 2 19 14
45 18 56 17
10 66 103 75
110 109 95 80
69 40 48 94
120 24 36 28
39 27 23 41
71 12 119 3
94 52 34 100
10 32 24 41
29 41 23 4
79 17 82 28
8 14 125 38
56 75 42 45
3 15 27 4
43 67 60 89
93 98 99 26
61 18 9 8
15 37 73 23
36 7 38 5
108 37 55 30
10 24 119 102
69 0 78 22
66 27 24 28
31 47 88 0
59 33 63 57
62 11 59 58
0 19 31 46
51 45 75 82
42 13 76 97
22 78 57 89
6 115 70 116
60 54 64 96
97 46 83 86
97 76 26 104
77 55 16 61
128 96 77 50
95 38 53 8
71 3 31 19
59 48 43 58
44 69 57 72
44 11 43 57
33 50 64 90
16 62 53 35
61 44 63 72
64 62 43 72
60 50 63 93
92 80 95 8
20 41 105 82
68 114 33 87
113 67 11 88
9 40 58 22
6 49 91 98
1 25 113 56
58 62 9 63
12 36 108 120
75 103 13 83
20 46 74 31
47 6 52 81
111 95 53 54
40 88 11 48
122 29 85 121
92 101 21 65
13 117 76 104
86 46 66 29
13 51 74 84
85 86 83 105
79 86 104 84
85 82 51 84
88 6 67 89
42 87 68 78
48 87 33 90
89 91 60 93
90 106 98 70
100 80 107 65
90 34 64 94
22 26 93 9
77 21 55 65
106 54 50 107
52 0 47 51
34 91 99 70
34 98 107 100
26 101 99 92
100 124 126 80
103 39 118 105
74 20 102 105
81 123 52 85
103 66 102 84
91 127 96 107
106 92 96 99
73 38 109 125
110 108 21 126
109 21 111 127
112 110 77 128
1 111 16 113
71 114 112 68
113 115 128 67
114 116 127 49
49 117 115 126
81 118 116 123
117 119 121 102
25 120 118 39
119 73 121 23
118 120 122 79
79 123 125 121
122 104 124 117
123 101 125 126
122 124 30 108
116 124 109 101
115 110 128 106
114 127 111 54

































































































































Attachment: signature.asc
Description: Digital signature




Archive powered by MHonArc 2.6.16.

Top of Page