c++ - UCI 种子数据集上的 CGAL::Delaunay_d C++: “EXC_BAD_ACCESS”

Question

对于我的博士工作，我需要在任何(低)维度中构建给定点集的 Delaunay 三角剖分 (DT)。到目前为止，我一直在使用 C++ CGAL 库处理高达 4D 的数据，没有任何明显的问题。

但是，由于我使用的类 CGAL::Delaunay_d 与我之前在 7D 数据集(即 UCI repository Seeds data set )上使用的类相同，所以似乎出了点问题，我不知道如何追踪我的问题。

这是一个可复制粘贴的代码来重现执行:

// 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;

}

因为我使用精确数字类型 CGAL::Gmpq 来计算 DT，我怀疑是 CGAL 的内部错误，但我不能断言。我的错误实际上发生在函数 EXACT_Delaunay_any_d::insert() 的调用中，我不知道如何找到调试它的方法。

在构造 20926 个单纯形之后，在尝试插入第 78 个点时，“EXC_BAD_ACCESS”信号停止了我的程序。

我的问题是:

• 我应该使用其他一些精确的数字类型吗？
• 是否是 CGAL 函数 EXACT_Delaunay_any_d::insert() 的内部问题？
• 是否与我的操作系统 (Mac OS X 10.6.8) 相关的内存分配问题？

如果您有任何调查的答案/线索，请提前致谢!

奥克塔维奥

Answer 1

有趣的是，您刚刚在 stackoverflow.com 上报告了堆栈溢出。

函数visibility_search在 Convex_hull_d.h 中是递归的(不是终端递归)并且递归的深度显然没有限制。这是一个错误。通过增加堆栈大小，您应该能够更进一步(该过程在本网站的其他问题中进行了解释)。让我们知道票价如何。

你也可以尝试减少其他堆栈的使用。也许使用 mpq_class或 CGAL::Quotient<CGAL::MP_Float>而不是 CGAL::Gmpq会有所帮助，否则可能会更糟。您也可以在将 gmp-impl.h 中的 65536 替换为 1024 后重新编译 GMP 库。