For my PhD work, I need to construct the Delaunay triangulation (DT) of a given point set in any (low) dimension. So far, I have been using the C++ CGAL library with data up to 4D without any noticeable problem.
However, as I used the same class CGAL::Delaunay_d as I previously used on an 7D data set (namely UCI repository Seeds data set ), it seems like something is going wrong and I don't know how to trace my problem.
Here is a copy-pastable code to reproduce the execution:
// CGAL includes
#include <CGAL/Cartesian_d.h>
#include <CGAL/Delaunay_d.h>
#include <CGAL/Gmpq.h>
// STANDARD includes
#include <iostream>
#include <string>
#include <map>
// TYPEDEFS
typedef CGAL::Gmpq EXACT_RT;
typedef CGAL::Cartesian_d<EXACT_RT> EXACT_Kernel;
typedef EXACT_Kernel::Point_d EXACT_Point;
typedef EXACT_Kernel::Vector_d EXACT_Vector;
typedef CGAL::Delaunay_d<EXACT_Kernel> EXACT_Delaunay_any_d;
typedef EXACT_Delaunay_any_d::Vertex_handle EXACT_Vertex_handle;
// NAMESPACES
using namespace std;
using namespace CGAL;
// FUNCTIONS
int main(int argc, char *argv[]);
void delaunay_d(EXACT_Delaunay_any_d &DT, const map <unsigned, vector<EXACT_RT> > &data);
map <unsigned, vector<EXACT_RT> > data_parse(const string &data_set);
// DATASET
char seeds_data_char[] = "15,26 14,84 0,871 5,763 3,312 2,221 5,22\n\
14,88 14,57 0,8811 5,554 3,333 1,018 4,956\n\
14,29 14,09 0,905 5,291 3,337 2,699 4,825\n\
13,84 13,94 0,8955 5,324 3,379 2,259 4,805\n\
16,14 14,99 0,9034 5,658 3,562 1,355 5,175\n\
14,38 14,21 0,8951 5,386 3,312 2,462 4,956\n\
14,69 14,49 0,8799 5,563 3,259 3,586 5,219\n\
14,11 14,1 0,8911 5,42 3,302 2,7 5\n\
16,63 15,46 0,8747 6,053 3,465 2,04 5,877\n\
16,44 15,25 0,888 5,884 3,505 1,969 5,533\n\
15,26 14,85 0,8696 5,714 3,242 4,543 5,314\n\
14,03 14,16 0,8796 5,438 3,201 1,717 5,001\n\
13,89 14,02 0,888 5,439 3,199 3,986 4,738\n\
13,78 14,06 0,8759 5,479 3,156 3,136 4,872\n\
13,74 14,05 0,8744 5,482 3,114 2,932 4,825\n\
14,59 14,28 0,8993 5,351 3,333 4,185 4,781\n\
13,99 13,83 0,9183 5,119 3,383 5,234 4,781\n\
15,69 14,75 0,9058 5,527 3,514 1,599 5,046\n\
14,7 14,21 0,9153 5,205 3,466 1,767 4,649\n\
12,72 13,57 0,8686 5,226 3,049 4,102 4,914\n\
14,16 14,4 0,8584 5,658 3,129 3,072 5,176\n\
14,11 14,26 0,8722 5,52 3,168 2,688 5,219\n\
15,88 14,9 0,8988 5,618 3,507 0,7651 5,091\n\
12,08 13,23 0,8664 5,099 2,936 1,415 4,961\n\
15,01 14,76 0,8657 5,789 3,245 1,791 5,001\n\
16,19 15,16 0,8849 5,833 3,421 0,903 5,307\n\
13,02 13,76 0,8641 5,395 3,026 3,373 4,825\n\
12,74 13,67 0,8564 5,395 2,956 2,504 4,869\n\
14,11 14,18 0,882 5,541 3,221 2,754 5,038\n\
13,45 14,02 0,8604 5,516 3,065 3,531 5,097\n\
13,16 13,82 0,8662 5,454 2,975 0,8551 5,056\n\
15,49 14,94 0,8724 5,757 3,371 3,412 5,228\n\
14,09 14,41 0,8529 5,717 3,186 3,92 5,299\n\
13,94 14,17 0,8728 5,585 3,15 2,124 5,012\n\
15,05 14,68 0,8779 5,712 3,328 2,129 5,36\n\
16,12 15 0,9 5,709 3,485 2,27 5,443\n\
16,2 15,27 0,8734 5,826 3,464 2,823 5,527\n\
17,08 15,38 0,9079 5,832 3,683 2,956 5,484\n\
14,8 14,52 0,8823 5,656 3,288 3,112 5,309\n\
14,28 14,17 0,8944 5,397 3,298 6,685 5,001\n\
13,54 13,85 0,8871 5,348 3,156 2,587 5,178\n\
13,5 13,85 0,8852 5,351 3,158 2,249 5,176\n\
13,16 13,55 0,9009 5,138 3,201 2,461 4,783\n\
15,5 14,86 0,882 5,877 3,396 4,711 5,528\n\
15,11 14,54 0,8986 5,579 3,462 3,128 5,18\n\
13,8 14,04 0,8794 5,376 3,155 1,56 4,961\n\
15,36 14,76 0,8861 5,701 3,393 1,367 5,132\n\
14,99 14,56 0,8883 5,57 3,377 2,958 5,175\n\
14,79 14,52 0,8819 5,545 3,291 2,704 5,111\n\
14,86 14,67 0,8676 5,678 3,258 2,129 5,351\n\
14,43 14,4 0,8751 5,585 3,272 3,975 5,144\n\
15,78 14,91 0,8923 5,674 3,434 5,593 5,136\n\
14,49 14,61 0,8538 5,715 3,113 4,116 5,396\n\
14,33 14,28 0,8831 5,504 3,199 3,328 5,224\n\
14,52 14,6 0,8557 5,741 3,113 1,481 5,487\n\
15,03 14,77 0,8658 5,702 3,212 1,933 5,439\n\
14,46 14,35 0,8818 5,388 3,377 2,802 5,044\n\
14,92 14,43 0,9006 5,384 3,412 1,142 5,088\n\
15,38 14,77 0,8857 5,662 3,419 1,999 5,222\n\
12,11 13,47 0,8392 5,159 3,032 1,502 4,519\n\
11,42 12,86 0,8683 5,008 2,85 2,7 4,607\n\
11,23 12,63 0,884 4,902 2,879 2,269 4,703\n\
12,36 13,19 0,8923 5,076 3,042 3,22 4,605\n\
13,22 13,84 0,868 5,395 3,07 4,157 5,088\n\
12,78 13,57 0,8716 5,262 3,026 1,176 4,782\n\
12,88 13,5 0,8879 5,139 3,119 2,352 4,607\n\
14,34 14,37 0,8726 5,63 3,19 1,313 5,15\n\
14,01 14,29 0,8625 5,609 3,158 2,217 5,132\n\
14,37 14,39 0,8726 5,569 3,153 1,464 5,3\n\
12,73 13,75 0,8458 5,412 2,882 3,533 5,067\n\
17,63 15,98 0,8673 6,191 3,561 4,076 6,06\n\
16,84 15,67 0,8623 5,998 3,484 4,675 5,877\n\
17,26 15,73 0,8763 5,978 3,594 4,539 5,791\n\
19,11 16,26 0,9081 6,154 3,93 2,936 6,079\n\
16,82 15,51 0,8786 6,017 3,486 4,004 5,841\n\
16,77 15,62 0,8638 5,927 3,438 4,92 5,795\n\
17,32 15,91 0,8599 6,064 3,403 3,824 5,922\n\
20,71 17,23 0,8763 6,579 3,814 4,451 6,451\n\
18,94 16,49 0,875 6,445 3,639 5,064 6,362\n\
17,12 15,55 0,8892 5,85 3,566 2,858 5,746\n\
16,53 15,34 0,8823 5,875 3,467 5,532 5,88\n\
18,72 16,19 0,8977 6,006 3,857 5,324 5,879\n\
20,2 16,89 0,8894 6,285 3,864 5,173 6,187\n\
19,57 16,74 0,8779 6,384 3,772 1,472 6,273\n\
19,51 16,71 0,878 6,366 3,801 2,962 6,185\n\
18,27 16,09 0,887 6,173 3,651 2,443 6,197\n\
18,88 16,26 0,8969 6,084 3,764 1,649 6,109\n\
18,98 16,66 0,859 6,549 3,67 3,691 6,498\n\
21,18 17,21 0,8989 6,573 4,033 5,78 6,231\n\
20,88 17,05 0,9031 6,45 4,032 5,016 6,321\n\
20,1 16,99 0,8746 6,581 3,785 1,955 6,449\n\
18,76 16,2 0,8984 6,172 3,796 3,12 6,053\n\
18,81 16,29 0,8906 6,272 3,693 3,237 6,053\n\
18,59 16,05 0,9066 6,037 3,86 6,001 5,877\n\
18,36 16,52 0,8452 6,666 3,485 4,933 6,448\n\
16,87 15,65 0,8648 6,139 3,463 3,696 5,967\n\
19,31 16,59 0,8815 6,341 3,81 3,477 6,238\n\
18,98 16,57 0,8687 6,449 3,552 2,144 6,453\n\
18,17 16,26 0,8637 6,271 3,512 2,853 6,273\n\
18,72 16,34 0,881 6,219 3,684 2,188 6,097\n\
16,41 15,25 0,8866 5,718 3,525 4,217 5,618\n\
17,99 15,86 0,8992 5,89 3,694 2,068 5,837\n\
19,46 16,5 0,8985 6,113 3,892 4,308 6,009\n\
19,18 16,63 0,8717 6,369 3,681 3,357 6,229\n\
18,95 16,42 0,8829 6,248 3,755 3,368 6,148\n\
18,83 16,29 0,8917 6,037 3,786 2,553 5,879\n\
18,85 16,17 0,9056 6,152 3,806 2,843 6,2\n\
17,63 15,86 0,88 6,033 3,573 3,747 5,929\n\
19,94 16,92 0,8752 6,675 3,763 3,252 6,55\n\
18,55 16,22 0,8865 6,153 3,674 1,738 5,894\n\
18,45 16,12 0,8921 6,107 3,769 2,235 5,794\n\
19,38 16,72 0,8716 6,303 3,791 3,678 5,965\n\
19,13 16,31 0,9035 6,183 3,902 2,109 5,924\n\
19,14 16,61 0,8722 6,259 3,737 6,682 6,053\n\
20,97 17,25 0,8859 6,563 3,991 4,677 6,316\n\
19,06 16,45 0,8854 6,416 3,719 2,248 6,163\n\
18,96 16,2 0,9077 6,051 3,897 4,334 5,75\n\
19,15 16,45 0,889 6,245 3,815 3,084 6,185\n\
18,89 16,23 0,9008 6,227 3,769 3,639 5,966\n\
20,03 16,9 0,8811 6,493 3,857 3,063 6,32\n\
20,24 16,91 0,8897 6,315 3,962 5,901 6,188\n\
18,14 16,12 0,8772 6,059 3,563 3,619 6,011\n\
16,17 15,38 0,8588 5,762 3,387 4,286 5,703\n\
18,43 15,97 0,9077 5,98 3,771 2,984 5,905\n\
15,99 14,89 0,9064 5,363 3,582 3,336 5,144\n\
18,75 16,18 0,8999 6,111 3,869 4,188 5,992\n\
18,65 16,41 0,8698 6,285 3,594 4,391 6,102\n\
17,98 15,85 0,8993 5,979 3,687 2,257 5,919\n\
20,16 17,03 0,8735 6,513 3,773 1,91 6,185\n\
17,55 15,66 0,8991 5,791 3,69 5,366 5,661\n\
18,3 15,89 0,9108 5,979 3,755 2,837 5,962\n\
18,94 16,32 0,8942 6,144 3,825 2,908 5,949\n\
15,38 14,9 0,8706 5,884 3,268 4,462 5,795\n\
16,16 15,33 0,8644 5,845 3,395 4,266 5,795\n\
15,56 14,89 0,8823 5,776 3,408 4,972 5,847\n\
15,38 14,66 0,899 5,477 3,465 3,6 5,439\n\
17,36 15,76 0,8785 6,145 3,574 3,526 5,971\n\
15,57 15,15 0,8527 5,92 3,231 2,64 5,879\n\
15,6 15,11 0,858 5,832 3,286 2,725 5,752\n\
16,23 15,18 0,885 5,872 3,472 3,769 5,922\n\
13,07 13,92 0,848 5,472 2,994 5,304 5,395\n\
13,32 13,94 0,8613 5,541 3,073 7,035 5,44\n\
13,34 13,95 0,862 5,389 3,074 5,995 5,307\n\
12,22 13,32 0,8652 5,224 2,967 5,469 5,221\n\
11,82 13,4 0,8274 5,314 2,777 4,471 5,178\n\
11,21 13,13 0,8167 5,279 2,687 6,169 5,275\n\
11,43 13,13 0,8335 5,176 2,719 2,221 5,132\n\
12,49 13,46 0,8658 5,267 2,967 4,421 5,002\n\
12,7 13,71 0,8491 5,386 2,911 3,26 5,316\n\
10,79 12,93 0,8107 5,317 2,648 5,462 5,194\n\
11,83 13,23 0,8496 5,263 2,84 5,195 5,307\n\
12,01 13,52 0,8249 5,405 2,776 6,992 5,27\n\
12,26 13,6 0,8333 5,408 2,833 4,756 5,36\n\
11,18 13,04 0,8266 5,22 2,693 3,332 5,001\n\
11,36 13,05 0,8382 5,175 2,755 4,048 5,263\n\
11,19 13,05 0,8253 5,25 2,675 5,813 5,219\n\
11,34 12,87 0,8596 5,053 2,849 3,347 5,003\n\
12,13 13,73 0,8081 5,394 2,745 4,825 5,22\n\
11,75 13,52 0,8082 5,444 2,678 4,378 5,31\n\
11,49 13,22 0,8263 5,304 2,695 5,388 5,31\n\
12,54 13,67 0,8425 5,451 2,879 3,082 5,491\n\
12,02 13,33 0,8503 5,35 2,81 4,271 5,308\n\
12,05 13,41 0,8416 5,267 2,847 4,988 5,046\n\
12,55 13,57 0,8558 5,333 2,968 4,419 5,176\n\
11,14 12,79 0,8558 5,011 2,794 6,388 5,049\n\
12,1 13,15 0,8793 5,105 2,941 2,201 5,056\n\
12,44 13,59 0,8462 5,319 2,897 4,924 5,27\n\
12,15 13,45 0,8443 5,417 2,837 3,638 5,338\n\
11,35 13,12 0,8291 5,176 2,668 4,337 5,132\n\
11,24 13 0,8359 5,09 2,715 3,521 5,088\n\
11,02 13 0,8189 5,325 2,701 6,735 5,163\n\
11,55 13,1 0,8455 5,167 2,845 6,715 4,956\n\
11,27 12,97 0,8419 5,088 2,763 4,309 5\n\
11,4 13,08 0,8375 5,136 2,763 5,588 5,089\n\
10,83 12,96 0,8099 5,278 2,641 5,182 5,185\n\
10,8 12,57 0,859 4,981 2,821 4,773 5,063\n\
11,26 13,01 0,8355 5,186 2,71 5,335 5,092\n\
10,74 12,73 0,8329 5,145 2,642 4,702 4,963\n\
11,48 13,05 0,8473 5,18 2,758 5,876 5,002\n\
12,21 13,47 0,8453 5,357 2,893 1,661 5,178\n\
11,41 12,95 0,856 5,09 2,775 4,957 4,825\n\
12,46 13,41 0,8706 5,236 3,017 4,987 5,147\n\
12,19 13,36 0,8579 5,24 2,909 4,857 5,158\n\
11,65 13,07 0,8575 5,108 2,85 5,209 5,135\n\
12,89 13,77 0,8541 5,495 3,026 6,185 5,316\n\
11,56 13,31 0,8198 5,363 2,683 4,062 5,182\n\
11,81 13,45 0,8198 5,413 2,716 4,898 5,352\n\
10,91 12,8 0,8372 5,088 2,675 4,179 4,956\n\
11,23 12,82 0,8594 5,089 2,821 7,524 4,957\n\
10,59 12,41 0,8648 4,899 2,787 4,975 4,794\n\
10,93 12,8 0,839 5,046 2,717 5,398 5,045\n\
11,27 12,86 0,8563 5,091 2,804 3,985 5,001\n\
11,87 13,02 0,8795 5,132 2,953 3,597 5,132\n\
10,82 12,83 0,8256 5,18 2,63 4,853 5,089\n\
12,11 13,27 0,8639 5,236 2,975 4,132 5,012\n\
12,8 13,47 0,886 5,16 3,126 4,873 4,914\n\
12,79 13,53 0,8786 5,224 3,054 5,483 4,958\n\
13,37 13,78 0,8849 5,32 3,128 4,67 5,091\n\
12,62 13,67 0,8481 5,41 2,911 3,306 5,231\n\
12,76 13,38 0,8964 5,073 3,155 2,828 4,83\n\
12,38 13,44 0,8609 5,219 2,989 5,472 5,045\n\
12,67 13,32 0,8977 4,984 3,135 2,3 4,745\n\
11,18 12,72 0,868 5,009 2,81 4,051 4,828\n\
12,7 13,41 0,8874 5,183 3,091 8,456 5\n\
12,37 13,47 0,8567 5,204 2,96 3,919 5,001\n\
12,19 13,2 0,8783 5,137 2,981 3,631 4,87\n\
11,23 12,88 0,8511 5,14 2,795 4,325 5,003\n\
13,2 13,66 0,8883 5,236 3,232 8,315 5,056\n\
11,84 13,21 0,8521 5,175 2,836 3,598 5,044\n\
12,3 13,34 0,8684 5,243 2,974 5,637 5,063";
//////////
// MAIN //
//////////
int main(int argc, char *argv[]) {
// DATA SET declaration
string seeds_data(seeds_data_char);
map <unsigned, vector<EXACT_RT> > my_DATA = data_parse(seeds_data);
// DT declaration
EXACT_Delaunay_any_d my_DT(7);
// DT construction
delaunay_d(my_DT, my_DATA);
return 0;
}
// DELAUNAY TRIANGULATION function
void delaunay_d(
EXACT_Delaunay_any_d &DT,
const map <unsigned, vector<EXACT_RT> > &data)
{
// Dim size variable
int d = ((data.begin()) ->second).size();
int i = 1;
// Scanning data set -- DT construction
for(map <unsigned, vector<EXACT_RT> >::const_iterator it = data.begin(); it != data.end(); it++, i++){
// Constructing Point objects
EXACT_Point tmp = EXACT_Point(d, (it ->second).begin(), (it ->second).end());
// Inserting point in the triangulation
EXACT_Vertex_handle v_tmp = DT.insert(tmp);
// DEBUG
std::cout << "-- DEBUG POST -- " << i << " -- DT.all_simplices().size() : " << DT.all_simplices().size() << " -- DT.current_dimension() : " << DT.current_dimension() << endl;
}
}
// PARSING DATA function
map <unsigned, vector<EXACT_RT> > data_parse(
const string &data_set)
{
// RETURNED map
map <unsigned, vector<EXACT_RT> > result;
// TMP variables declaration
vector<EXACT_RT> vect;
string tmp_value;
char current_char;
for (unsigned i=0; i<data_set.length(); i++)
{
current_char = data_set[i];
// Testing if read character is tab or space (i.e. end of a number) ...
if( (current_char == '\t') || (current_char == ' ')) {
double curr_num = atof(tmp_value.c_str());
vect.push_back(EXACT_RT(curr_num)); // Storing the double value.
tmp_value.clear(); // Clearing current number
}
// ... end of a line ...
else
if ( (current_char == '\n') || (current_char == '\r') ) {
double curr_num = atof(tmp_value.c_str());
vect.push_back(EXACT_RT(curr_num)); // Storing the double value.
result.insert ( pair <unsigned, vector<EXACT_RT> > (i++, vect) ); // Feeding returned map
tmp_value.clear(); // Clearing current number
vect.clear(); // Clearing the vector containing the converted values
}
// .. storing any other character
else {
// Dealing with decimal character (from ',' to '.')
if(current_char == ',') {
// Storing current character
tmp_value.push_back('.');
}
else
// Storing current character
tmp_value.push_back(current_char);
}
}
return result;
}
As I used exact number type CGAL::Gmpq for the computation of the DT, I suspect an internal bug of CGAL but I can't assert it. My error actually occurs within the call of function EXACT_Delaunay_any_d::insert()and I don't know how to find a way to debug it.
An “EXC_BAD_ACCESS” signal stops my program while trying to insert the 78-th point, after construction of 20926 simplices.
My questions are:
- Should I use some other exact number type ?
- Is it an internal issue of CGAL function
EXACT_Delaunay_any_d::insert() ?
- Is it a problem of memory allocation related to my OS (Mac OS X 10.6.8) ?
Thanks in advance if you have any answer / clue for investigation !
Octavio
https://stackoverflow.com/questions/17404432
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian