| 1 | #include <assert.h>
|
|---|
| 2 | #include <vector>
|
|---|
| 3 | #include <boost/polygon/polygon.hpp>
|
|---|
| 4 |
|
|---|
| 5 | using namespace std;
|
|---|
| 6 |
|
|---|
| 7 | namespace gtl = boost::polygon;
|
|---|
| 8 |
|
|---|
| 9 | typedef gtl::rectangle_data<int> Rectangle;
|
|---|
| 10 | typedef gtl::polygon_data<int> Polygon;
|
|---|
| 11 | typedef gtl::polygon_traits<Polygon>::point_type Point;
|
|---|
| 12 |
|
|---|
| 13 | // Input polygon.
|
|---|
| 14 | typedef int ipt[2];
|
|---|
| 15 | const ipt data[] = {
|
|---|
| 16 | {645748,684196},{643709,684196},{643555,684196},{628872,684196},{620334,656269},
|
|---|
| 17 | {620287,656115},{620287,408944},{619486,406744},{618271,403405},{616244,402234},
|
|---|
| 18 | {613165,400457},{610860,400863},{607359,401480},{605855,403274},{603570,405996},
|
|---|
| 19 | {603570,409551},{603570,411892},{605855,414615},{607359,416409},{610860,417026},
|
|---|
| 20 | {613165,417432},{616244,415655},{618271,414484},{619486,411144},{620287,408944},
|
|---|
| 21 | {620287,656115},{620193,655807},{577589,516454},{577589,455256},{577589,452945},
|
|---|
| 22 | {577589,408071},{575971,408071},{553957,408071},{553957,391468},{552602,389122},
|
|---|
| 23 | {543288,372991},{539122,365774},{536413,365774},{509453,365774},{508099,368120},
|
|---|
| 24 | {504184,374899},{494618,391468},{504184,408037},{505287,409946},{509453,417162},
|
|---|
| 25 | {536413,417162},{539122,417162},{543288,409946},{544391,408037},{553957,391468},
|
|---|
| 26 | {553957,408071},{552658,408071},{552291,408712},{552193,408880},{543267,424341},
|
|---|
| 27 | {505308,424341},{505263,424263},{495915,408071},{494666,408071},{470986,408071},
|
|---|
| 28 | {470986,452945},{470986,455256},{573398,455256},{573838,455256},{576276,455256},
|
|---|
| 29 | {577589,455256},{577589,516454},{577551,516330},{576511,512929},{557642,512929},
|
|---|
| 30 | {554870,512929},{554870,465743},{553540,465743},{493705,465743},{493705,512929},
|
|---|
| 31 | {492687,512929},{492428,512929},{492426,512929},{492254,512929},{491889,512929},
|
|---|
| 32 | {491246,512929},{490218,512929},{488757,512929},{487077,512929},{485840,512929},
|
|---|
| 33 | {485696,512929},{445525,512929},{445525,408944},{444724,406744},{443509,403405},
|
|---|
| 34 | {441482,402234},{438403,400457},{436097,400863},{432598,401480},{431092,403274},
|
|---|
| 35 | {428807,405996},{428807,409551},{428807,411892},{431092,414615},{432598,416409},
|
|---|
| 36 | {436097,417026},{438403,417432},{441482,415655},{443509,414484},{444724,411144},
|
|---|
| 37 | {445525,408944},{445525,512929},{444596,512929},{427449,512929},{426805,512929},
|
|---|
| 38 | {426742,512929},{426552,512906},{426470,512895},{423088,512486},{423071,512480},
|
|---|
| 39 | {422987,512447},{416980,510169},{416891,510108},{411608,506461},{411537,506381},
|
|---|
| 40 | {407278,501575},{407228,501480},{404244,495794},{404223,495708},{402827,490045},
|
|---|
| 41 | {402827,487257},{402827,398779},{403269,395139},{403270,395123},{405547,389119},
|
|---|
| 42 | {405585,389020},{409234,383733},{409295,383645},{414100,379387},{414181,379316},
|
|---|
| 43 | {419867,376331},{419962,376282},{419957,376283},{420039,376263},{425528,374910},
|
|---|
| 44 | {425675,374874},{425711,374865},{425852,374865},{426520,374865},{427317,374865},
|
|---|
| 45 | {427900,374865},{487792,374865},{489490,374865},{490971,374865},{492014,374865},
|
|---|
| 46 | {492669,374865},{495915,374865},{505263,358674},{505317,358581},{505309,358595},
|
|---|
| 47 | {543267,358595},{552290,374223},{552658,374865},{559086,374865},{560783,374865},
|
|---|
| 48 | {562028,374865},{562164,374865},{621126,374865},{621770,374865},{621834,374865},
|
|---|
| 49 | {625167,375270},{625468,375306},{625489,375308},{631158,377458},{631274,377502},
|
|---|
| 50 | {631398,377549},{631594,377624},{636880,381272},{636968,381333},{641226,386138},
|
|---|
| 51 | {641297,386219},{644282,391905},{644332,392000},{645727,397662},{645748,397748},
|
|---|
| 52 | {645748,510126},{645748,675973},{645748,679096},{645748,679662},{645748,683732},
|
|---|
| 53 | {645748,683932},
|
|---|
| 54 | };
|
|---|
| 55 |
|
|---|
| 56 | int main()
|
|---|
| 57 | {
|
|---|
| 58 | vector<Point> points;
|
|---|
| 59 | for(unsigned int i=0; i<sizeof(data)/sizeof(data[0]); i++)
|
|---|
| 60 | points.push_back(Point(data[i][0], data[i][1]));
|
|---|
| 61 | Polygon p;
|
|---|
| 62 | gtl::set_points(p, points.begin(), points.end());
|
|---|
| 63 | vector<Polygon> pset;
|
|---|
| 64 | pset.push_back(p);
|
|---|
| 65 |
|
|---|
| 66 | // Pre-resize by half of the increment below. This step (which is
|
|---|
| 67 | // an arbitrary artifact of the way the end user code works) is
|
|---|
| 68 | // important, without it the resizing is perfectly fast. Why?
|
|---|
| 69 | //
|
|---|
| 70 | // Note: setting this value to -874 (which I did when writing the
|
|---|
| 71 | // test case via a roundoff bug in a hand conversion) produces
|
|---|
| 72 | // minimal splitting and fast operation. But -873 (the value that
|
|---|
| 73 | // happens to be produced by my end code) is a disaster. Why?
|
|---|
| 74 | gtl::resize(pset, -873, true, 7);
|
|---|
| 75 |
|
|---|
| 76 | // Iteratively shrink, reporting vertex count and time elapsed at
|
|---|
| 77 | // each stage. Note three things:
|
|---|
| 78 | //
|
|---|
| 79 | // 1. The vertex count is exploding far faster than it should. As
|
|---|
| 80 | // documented, each acute vertex should split into N segments,
|
|---|
| 81 | // which won't need to be split farther. Instead we're seeing a
|
|---|
| 82 | // near-doubling with each iteration.
|
|---|
| 83 | //
|
|---|
| 84 | // 2. The time complexity appears to be polynomial, not NlogN.
|
|---|
| 85 | //
|
|---|
| 86 | // 3. The number of new vertices is oddly sensitive to the value
|
|---|
| 87 | // of num_circle_segments. Passing in 7 below leads to a serious
|
|---|
| 88 | // performance regression, but 6 is much faster. I've observed
|
|---|
| 89 | // exactly the opposite on other input data.
|
|---|
| 90 |
|
|---|
| 91 | while(!gtl::empty(pset)) {
|
|---|
| 92 | time_t start = time(NULL);
|
|---|
| 93 | gtl::resize(pset, -1747, true, 7);
|
|---|
| 94 | time_t end = time(NULL);
|
|---|
| 95 |
|
|---|
| 96 | int n=0;
|
|---|
| 97 | for(unsigned int i=0; i<pset.size(); i++)
|
|---|
| 98 | n += pset[i].size();
|
|---|
| 99 |
|
|---|
| 100 | printf("%d vertices, %ld secs\n", n, end-start);
|
|---|
| 101 | }
|
|---|
| 102 | return 0;
|
|---|
| 103 | }
|
|---|
