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(); }