Hello,<div><br></div><div>First: we are using boost 1.45.0 with gcc -O3 on Ubuntu 10.04.  (Although similar problems appear with VS2008 on Windows 7).</div><div><br></div><div>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: &quot;//quadratic algorithm to do same work as optimal scan for cross checking&quot;.</div>

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

<div><br></div><div>Regards,<br>Josh Pieper</div><div><br></div><div>Performance results for n=10..110 measured in instructions to complete the following test program:</div><div><br></div><div><div>10 2363923</div><div>20 4427849</div>

<div>30 8695564</div><div>40 15642559</div><div>50 25530188</div><div>60 39081335</div><div>70 57151093</div><div>80 79278939</div><div>90 107261217</div><div>100 140674559</div><div>110 164340087</div></div><div><br></div>

<div><br></div><div>--------------------------</div><div><br></div><div><div>#include &lt;boost/lexical_cast.hpp&gt;</div><div>#include &lt;boost/type.hpp&gt;</div><div><br></div><div>#include &lt;boost/polygon/polygon.hpp&gt;</div>

<div>#include &lt;boost/polygon/gmp_override.hpp&gt;</div><div><br></div><div>int main(int argc, char** argv) {</div><div>  typedef boost::polygon::point_data&lt;int32_t&gt; point_type;</div><div>  typedef boost::polygon::polygon_set_data&lt;int32_t&gt; polygon_set;</div>

<div>  typedef polygon_set::value_type value_type;</div><div><br></div><div>  int32_t sample_data[] = {</div><div>    -15417, -53418, 0, 0, -1,</div><div>    -15417, -53418, 37998, -68834, 1,</div><div>    37998, -68834, 53415, -15416, 1,</div>

<div>    0, 0, 53415, -15416, -1,</div><div>    -20188, -37532, 15869, 4788, -1,</div><div>    -20188, -37532, 22129, -73587, 1,</div><div>    22129, -73587, 58187, -31268, 1,</div><div>    15869, 4788, 58187, -31268, -1,</div>

<div>    -12388, -58060, -4666, -3001, -1,</div><div>    -12388, -58060, 42669, -65781, 1,</div><div>    42669, -65781, 50390, -10722, 1,</div><div>    -4666, -3001, 50390, -10722, -1,</div><div>    -16452, -51370, 2015, 1078, -1,</div>

<div>    -16452, -51370, 35988, -69834, 1,</div><div>    35988, -69834, 54455, -17386, 1,</div><div>    2015, 1078, 54455, -17386, -1,</div><div>    -9812, -61108, -7737, -5548, -1,</div><div>    -9812, -61108, 45744, -63182, 1,</div>

<div>    45744, -63182, 47819, -7623, 1,</div><div>    -7737, -5548, 47819, -7623, -1,</div><div>    -19695, -27418, 25940, 4341, -1,</div><div>    -19695, -27418, 12063, -73050, 1,</div><div>    12063, -73050, 57697, -41291, 1,</div>

<div>    25940, 4341, 57697, -41291, -1,</div><div>    -11871, -58680, -5330, -3460, -1,</div><div>    -11871, -58680, 43338, -65220, 1,</div><div>    43338, -65220, 49879, -10000, 1,</div><div>    -5330, -3460, 49879, -10000, -1,</div>

<div>    -12303, -10547, -4768, -65638, 1,</div><div>    -4768, -65638, 50314, -58104, 1,</div><div>    42779, -3013, 50314, -58104, -1,</div><div>    -12303, -10547, 42779, -3013, -1,</div><div>    -10105, -60739, -7415, -5202, -1,</div>

<div>    -10105, -60739, 45425, -63428, 1,</div><div>    45425, -63428, 48115, -7891, 1,</div><div>    -7415, -5202, 48115, -7891, -1,</div><div>    -9937, -60912, -7600, -5360, -1,</div><div>    -9937, -60912, 45609, -63249, 1,</div>

<div>    45609, -63249, 47946, -7697, 1,</div><div>    -7600, -5360, 47946, -7697, -1,</div><div>    -20348, -32184, 16794, -73555, 1,</div><div>    16794, -73555, 58164, -36414, 1,</div><div>    21022, 4957, 58164, -36414, -1,</div>

<div>    -20348, -32184, 21022, 4957, -1,</div><div>    -10796, -8606, -6653, -64049, 1,</div><div>    -6653, -64049, 48788, -59906, 1,</div><div>    44644, -4463, 48788, -59906, -1,</div><div>    -10796, -8606, 44644, -4463, -1,</div>

<div>    -16263, -16858, 1613, -69511, 1,</div><div>    1613, -69511, 54257, -51638, 1,</div><div>    36381, 1014, 54257, -51638, -1,</div><div>    -16263, -16858, 36381, 1014, -1,</div><div>    -20298, -33057, 17817, -73534, 1,</div>

<div>    17817, -73534, 58292, -35421, 1,</div><div>    20177, 5056, 58292, -35421, -1,</div><div>    -20298, -33057, 20177, 5056, -1,</div><div>    -11941, -9961, -5271, -65159, 1,</div><div>    -5271, -65159, 49923, -58490, 1,</div>

<div>    43253, -3292, 49923, -58490, -1,</div><div>    -11941, -9961, 43253, -3292, -1,</div><div>    -19046, -44168, 28939, -72250, 1,</div><div>    28939, -72250, 57020, -24267, 1,</div><div>    9035, 3815, 57020, -24267, -1,</div>

<div>    -19046, -44168, 9035, 3815, -1,</div><div>    -10926, -8703, -6528, -64127, 1,</div><div>    -6528, -64127, 48893, -59729, 1,</div><div>    44495, -4305, 48893, -59729, -1,</div><div>    -10926, -8703, 44495, -4305, -1,</div>

<div>    -19113, -43924, 28699, -72304, 1,</div><div>    28699, -72304, 57076, -24496, 1,</div><div>    9263, 3883, 57076, -24496, -1,</div><div>    -19113, -43924, 9263, 3883, -1,</div><div>    -18256, -21581, 6351, -71437, 1,</div>

<div>    6351, -71437, 56204, -46832, 1,</div><div>    31598, 3024, 56204, -46832, -1,</div><div>    -18256, -21581, 31598, 3024, -1,</div><div>    -20282, -31991, 16756, -73456, 1,</div><div>    16756, -73456, 58219, -36421, 1,</div>

<div>    21181, 5045, 58219, -36421, -1,</div><div>    -20282, -31991, 21181, 5045, -1,</div><div>    -19379, -25528, 10293, -72546, 1,</div><div>    10293, -72546, 57309, -42875, 1,</div><div>    27637, 4143, 57309, -42875, -1,</div>

<div>    -19379, -25528, 27637, 4143, -1,</div><div>    -16209, -16633, 1396, -69371, 1,</div><div>    1396, -69371, 54130, -51767, 1,</div><div>    36526, 970, 54130, -51767, -1,</div><div>    -16209, -16633, 36526, 970, -1,</div>

<div>    -18570, -22483, 7245, -71726, 1,</div><div>    7245, -71726, 56484, -45912, 1,</div><div>    30669, 3330, 56484, -45912, -1,</div><div>    -18570, -22483, 30669, 3330, -1,</div><div>    -19900, -40189, 24948, -73049, 1,</div>

<div>    24948, -73049, 57806, -28203, 1,</div><div>    12958, 4657, 57806, -28203, -1,</div><div>    -19900, -40189, 12958, 4657, -1,</div><div>    -20322, -36011, 20774, -73460, 1,</div><div>    20774, -73460, 58220, -32367, 1,</div>

<div>    17124, 5082, 58220, -32367, -1,</div><div>    -20322, -36011, 17124, 5082, -1,</div><div>    -555, -68328, 53079, -53671, 1,</div><div>    38424, -43, 53079, -53671, -1,</div><div>    -15210, -14699, 38424, -43, -1,</div>

<div>    -15210, -14699, -555, -68328, 1,</div><div>    21671, -61840, 21718, -61835, 1,</div><div>    14689, -61655, 21718, -61835, -1,</div><div>    14689, -61655, 42185, -65881, 1,</div><div>    42185, -65881, 50629, -10931, 1,</div>

<div>    23134, -6705, 50629, -10931, -1,</div><div>    16104, -6524, 23134, -6705, -1,</div><div>    16057, -6529, 16104, -6524, -1,</div><div>    16057, -6529, 21671, -61840, 1,</div><div>    -7903, -63005, 47680, -60927, 1,</div>

<div>    45602, -5370, 47680, -60927, -1,</div><div>    -9981, -7449, 45602, -5370, -1,</div><div>    -9981, -7449, -7903, -63005, 1,</div><div>  };</div><div><br></div><div>  value_type edge_list;</div><div><br></div><div>

  size_t num_elements = sizeof(sample_data) / (sizeof(*sample_data) * 5);</div><div><br></div><div>  if (argc &gt; 1) {</div><div>    num_elements = std::min(num_elements, boost::lexical_cast&lt;size_t&gt;(argv[1]));</div>

<div>  }</div><div><br></div><div>  for (size_t i = 0; i &lt; num_elements; i++) {</div><div>    value_type::value_type edge_plus;</div><div>    int32_t* record = &amp;sample_data[i * 5];</div><div>    edge_plus.first.first = point_type(record[0], record[1]);</div>

<div>    edge_plus.first.second = point_type(record[2], record[3]);</div><div>    edge_plus.second = record[4];</div><div>    edge_list.push_back(edge_plus);</div><div>  }</div><div><br></div><div>  polygon_set pset;</div>

<div>  pset.set(edge_list);</div><div>  pset.clean();</div><div>}</div></div><div><br></div>