Boost::geometry::intersection performance in Debug mode

Question

I have a question about boost::geometry::intersection performance in Debug configuration. One part of my project has a lot(millions) of intersections of polygon-polygon kind. And it is very-very slow in debug comparing to release. So I need to wait a lot of time to debug problems after this 'intersection' part. What can I do to speed up it in Debug mode?

Code example of simple Win32 console project in VS2010:

#include "stdafx.h"
#include <time.h>
#include <deque>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/foreach.hpp>

bool get_poly_intersection_area_S_2d(   const double *poly_x_1, const int poly_n_1,    const double *poly_x_2, const int poly_n_2, double *S)
{
    // intersects two 2d polygons using boost::geometry library
    // polygons are in 3d format [(x0, y0, 0.0) (x1, y1, 0.0) .... (xn, yn, 0.0) ]
    // S is resulting area of intersection
    // returns true if intersection exists (area > DBL_EPSILON) and false otherwise
    typedef boost::geometry::model::d2::point_xy<double> bg_point;
    typedef boost::geometry::model::polygon< bg_point, false, false > bg_polygon;

    *S = 0.0;

    bg_polygon bg_poly_1, bg_poly_2;

    // init boost 2d polygons by our double 3D polygons
    for(int i=0; i<poly_n_1; i++)
      bg_poly_1.outer().push_back(bg_point(poly_x_1[i*3], poly_x_1[i*3+1]));

    for(int i=0; i<poly_n_2; i++)
      bg_poly_2.outer().push_back(bg_point(poly_x_2[i*3], poly_x_2[i*3+1]));

    // correct polygons
    boost::geometry::correct(bg_poly_1);
    boost::geometry::correct(bg_poly_2);

    // call intersection
    std::deque<bg_polygon> output;
    bool res = boost::geometry::intersection(bg_poly_1, bg_poly_2, output);

    if(!res)
     return false;

    // for each polygon of intersection we add area
    BOOST_FOREACH(bg_polygon const& p, output)
    {
      double s = boost::geometry::area(p);
      *S += s;
    }

    // no intersection
    if(fabs(*S) <= DBL_EPSILON)
       return false;

    // intersection > DBL_EPSILON
    return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
double p1[4 * 3] = {0,0,0, 2,0,0, 2,2,0, 0,2,0};
double p2[4 * 3] = {1,1,0, 3,1,0, 3,3,0, 1,3,0};

clock_t start_t, finish_t;
start_t = clock();
for(int i=0;i<5000; i++)
{
    double s;
    for(int k=0; k<4; k++)
    {
        p1[k*4] += i;
        p2[k*4] += i;
    }
    get_poly_intersection_area_S_2d(p1, 4, p2, 4, &s);
}
finish_t = clock();
printf("time=%.3f s\n", double(finish_t - start_t)/1000.);

return 0;
}

In Debug it takes 15 seconds, in Release 0.1 seconds. And here only 5000 polygons intersections. For millions it will be much slower.

Answer 1

The Boost.Geometry speed is heavily influenced by the speed of stl (vector, deque, map) which is considerably slower in Debug Mode.

You might try to solve that, e.g. by this links:

Why does my STL code run so slowly when I have the debugger/IDE attached?

Why is this code 100 times slower in debug?

Especially the second link suggests setting _HAS_ITERATOR_DEBUGGING to 0 which might help a lot because iterators are heavily used inside Boost.Geometry

Alternatively you might try using stl port.

Answer 2

The best way is to work out a way to reproduce the problem you are debugging using a small dataset. This helps in MANY ways, especially when creating a regression test when you have solved the problem.

You write: "debug problems after this 'intersection' part "

This suggests to me that you should optionally save the output from the intersection part, so that you need run it only once, and then have an option to load the saved partial result and run the rest of the program from there in debug mode.