[Boost-users] [polygon] Quadratic performance when handling any angle polygons

Subject: [Boost-users] [polygon] Quadratic performance when handling any angle polygons
From: Josh Pieper (jpieper_at_[hidden])
Date: 2011-01-19 11:23:25

Hello,

First: we are using boost 1.45.0 with gcc -O3 on Ubuntu 10.04.  (Although
similar problems appear with VS2008 on Windows 7).

We have been observing performance with boost::polygon that is significantly
worse than we were expecting when working with any angle polygons.  Namely
quadratic instead of the expected O(n log n).  While profiling, I noticed
that most of the time is spent in the overload of
line_intersection::validate_scan at detail/scan_arbitrary.hpp:154 which is
commented as: "//quadratic algorithm to do same work as optimal scan for
cross checking".

I have inlined our test program below, and some performance results measured
by instruction count under "valgrind --tool=callgrind".  Is this poor
performance because our data is degenerate, or because a vestigal quadratic
double check is still being applied?

Regards,
Josh Pieper

Performance results for n=10..110 measured in instructions to complete the
following test program:

10 2363923
20 4427849
30 8695564
40 15642559
50 25530188
60 39081335
70 57151093
80 79278939
90 107261217
100 140674559
110 164340087

--------------------------

#include <boost/lexical_cast.hpp>
#include <boost/type.hpp>

#include <boost/polygon/polygon.hpp>
#include <boost/polygon/gmp_override.hpp>

int main(int argc, char** argv) {
  typedef boost::polygon::point_data<int32_t> point_type;
  typedef boost::polygon::polygon_set_data<int32_t> polygon_set;
  typedef polygon_set::value_type value_type;

  int32_t sample_data[] = {
    -15417, -53418, 0, 0, -1,
    -15417, -53418, 37998, -68834, 1,
    37998, -68834, 53415, -15416, 1,
    0, 0, 53415, -15416, -1,
    -20188, -37532, 15869, 4788, -1,
    -20188, -37532, 22129, -73587, 1,
    22129, -73587, 58187, -31268, 1,
    15869, 4788, 58187, -31268, -1,
    -12388, -58060, -4666, -3001, -1,
    -12388, -58060, 42669, -65781, 1,
    42669, -65781, 50390, -10722, 1,
    -4666, -3001, 50390, -10722, -1,
    -16452, -51370, 2015, 1078, -1,
    -16452, -51370, 35988, -69834, 1,
    35988, -69834, 54455, -17386, 1,
    2015, 1078, 54455, -17386, -1,
    -9812, -61108, -7737, -5548, -1,
    -9812, -61108, 45744, -63182, 1,
    45744, -63182, 47819, -7623, 1,
    -7737, -5548, 47819, -7623, -1,
    -19695, -27418, 25940, 4341, -1,
    -19695, -27418, 12063, -73050, 1,
    12063, -73050, 57697, -41291, 1,
    25940, 4341, 57697, -41291, -1,
    -11871, -58680, -5330, -3460, -1,
    -11871, -58680, 43338, -65220, 1,
    43338, -65220, 49879, -10000, 1,
    -5330, -3460, 49879, -10000, -1,
    -12303, -10547, -4768, -65638, 1,
    -4768, -65638, 50314, -58104, 1,
    42779, -3013, 50314, -58104, -1,
    -12303, -10547, 42779, -3013, -1,
    -10105, -60739, -7415, -5202, -1,
    -10105, -60739, 45425, -63428, 1,
    45425, -63428, 48115, -7891, 1,
    -7415, -5202, 48115, -7891, -1,
    -9937, -60912, -7600, -5360, -1,
    -9937, -60912, 45609, -63249, 1,
    45609, -63249, 47946, -7697, 1,
    -7600, -5360, 47946, -7697, -1,
    -20348, -32184, 16794, -73555, 1,
    16794, -73555, 58164, -36414, 1,
    21022, 4957, 58164, -36414, -1,
    -20348, -32184, 21022, 4957, -1,
    -10796, -8606, -6653, -64049, 1,
    -6653, -64049, 48788, -59906, 1,
    44644, -4463, 48788, -59906, -1,
    -10796, -8606, 44644, -4463, -1,
    -16263, -16858, 1613, -69511, 1,
    1613, -69511, 54257, -51638, 1,
    36381, 1014, 54257, -51638, -1,
    -16263, -16858, 36381, 1014, -1,
    -20298, -33057, 17817, -73534, 1,
    17817, -73534, 58292, -35421, 1,
    20177, 5056, 58292, -35421, -1,
    -20298, -33057, 20177, 5056, -1,
    -11941, -9961, -5271, -65159, 1,
    -5271, -65159, 49923, -58490, 1,
    43253, -3292, 49923, -58490, -1,
    -11941, -9961, 43253, -3292, -1,
    -19046, -44168, 28939, -72250, 1,
    28939, -72250, 57020, -24267, 1,
    9035, 3815, 57020, -24267, -1,
    -19046, -44168, 9035, 3815, -1,
    -10926, -8703, -6528, -64127, 1,
    -6528, -64127, 48893, -59729, 1,
    44495, -4305, 48893, -59729, -1,
    -10926, -8703, 44495, -4305, -1,
    -19113, -43924, 28699, -72304, 1,
    28699, -72304, 57076, -24496, 1,
    9263, 3883, 57076, -24496, -1,
    -19113, -43924, 9263, 3883, -1,
    -18256, -21581, 6351, -71437, 1,
    6351, -71437, 56204, -46832, 1,
    31598, 3024, 56204, -46832, -1,
    -18256, -21581, 31598, 3024, -1,
    -20282, -31991, 16756, -73456, 1,
    16756, -73456, 58219, -36421, 1,
    21181, 5045, 58219, -36421, -1,
    -20282, -31991, 21181, 5045, -1,
    -19379, -25528, 10293, -72546, 1,
    10293, -72546, 57309, -42875, 1,
    27637, 4143, 57309, -42875, -1,
    -19379, -25528, 27637, 4143, -1,
    -16209, -16633, 1396, -69371, 1,
    1396, -69371, 54130, -51767, 1,
    36526, 970, 54130, -51767, -1,
    -16209, -16633, 36526, 970, -1,
    -18570, -22483, 7245, -71726, 1,
    7245, -71726, 56484, -45912, 1,
    30669, 3330, 56484, -45912, -1,
    -18570, -22483, 30669, 3330, -1,
    -19900, -40189, 24948, -73049, 1,
    24948, -73049, 57806, -28203, 1,
    12958, 4657, 57806, -28203, -1,
    -19900, -40189, 12958, 4657, -1,
    -20322, -36011, 20774, -73460, 1,
    20774, -73460, 58220, -32367, 1,
    17124, 5082, 58220, -32367, -1,
    -20322, -36011, 17124, 5082, -1,
    -555, -68328, 53079, -53671, 1,
    38424, -43, 53079, -53671, -1,
    -15210, -14699, 38424, -43, -1,
    -15210, -14699, -555, -68328, 1,
    21671, -61840, 21718, -61835, 1,
    14689, -61655, 21718, -61835, -1,
    14689, -61655, 42185, -65881, 1,
    42185, -65881, 50629, -10931, 1,
    23134, -6705, 50629, -10931, -1,
    16104, -6524, 23134, -6705, -1,
    16057, -6529, 16104, -6524, -1,
    16057, -6529, 21671, -61840, 1,
    -7903, -63005, 47680, -60927, 1,
    45602, -5370, 47680, -60927, -1,
    -9981, -7449, 45602, -5370, -1,
    -9981, -7449, -7903, -63005, 1,
  };

  value_type edge_list;

  size_t num_elements = sizeof(sample_data) / (sizeof(*sample_data) * 5);

  if (argc > 1) {
    num_elements = std::min(num_elements,
boost::lexical_cast<size_t>(argv[1]));
  }

  for (size_t i = 0; i < num_elements; i++) {
    value_type::value_type edge_plus;
    int32_t* record = &sample_data[i * 5];
    edge_plus.first.first = point_type(record[0], record[1]);
    edge_plus.first.second = point_type(record[2], record[3]);
    edge_plus.second = record[4];
    edge_list.push_back(edge_plus);
  }

  polygon_set pset;
  pset.set(edge_list);
  pset.clean();
}