1

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

但是,由于我使用了与之前在 7D 数据集(即UCI 存储库Seeds数据集)上使用的相同的类 CGAL::Delaunay_d,因此似乎出了点问题,我不知道如何追踪我的问题。

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

// 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(),我不知道如何找到调试它的方法。

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

我的问题是:

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

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

奥克塔维奥

4

1 回答 1

1

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

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

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

于 2013-07-03T18:18:06.703 回答