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:
EXACT_Delaunay_any_d::insert() ?Thanks in advance if you have any answer / clue for investigation !
Octavio
Interestingly, you just reported a stack overflow on stackoverflow.com.
The function visibility_search in Convex_hull_d.h is recursive (not a terminal recursion) and the depth of the recursion is apparently not bounded. This is a bug. You should be able to get a bit further by increasing the stack size (the procedure is explained in other questions on this site). Let us know how that fares.
You can also try to reduce other stack use. Maybe using mpq_class or CGAL::Quotient<CGAL::MP_Float> instead of CGAL::Gmpq would help, or it might be even worse. You could also recompile the GMP library after replacing 65536 with 1024 in gmp-impl.h.