#include <assert.h>
#include <vector>
#include <boost/polygon/polygon.hpp>

using namespace std;

namespace gtl = boost::polygon;

typedef gtl::rectangle_data<int> Rectangle;
typedef gtl::polygon_data<int> Polygon;
typedef gtl::polygon_traits<Polygon>::point_type Point;

// Input polygon.
typedef int ipt[2];
const ipt data[] = {
    {645748,684196},{643709,684196},{643555,684196},{628872,684196},{620334,656269},
    {620287,656115},{620287,408944},{619486,406744},{618271,403405},{616244,402234},
    {613165,400457},{610860,400863},{607359,401480},{605855,403274},{603570,405996},
    {603570,409551},{603570,411892},{605855,414615},{607359,416409},{610860,417026},
    {613165,417432},{616244,415655},{618271,414484},{619486,411144},{620287,408944},
    {620287,656115},{620193,655807},{577589,516454},{577589,455256},{577589,452945},
    {577589,408071},{575971,408071},{553957,408071},{553957,391468},{552602,389122},
    {543288,372991},{539122,365774},{536413,365774},{509453,365774},{508099,368120},
    {504184,374899},{494618,391468},{504184,408037},{505287,409946},{509453,417162},
    {536413,417162},{539122,417162},{543288,409946},{544391,408037},{553957,391468},
    {553957,408071},{552658,408071},{552291,408712},{552193,408880},{543267,424341},
    {505308,424341},{505263,424263},{495915,408071},{494666,408071},{470986,408071},
    {470986,452945},{470986,455256},{573398,455256},{573838,455256},{576276,455256},
    {577589,455256},{577589,516454},{577551,516330},{576511,512929},{557642,512929},
    {554870,512929},{554870,465743},{553540,465743},{493705,465743},{493705,512929},
    {492687,512929},{492428,512929},{492426,512929},{492254,512929},{491889,512929},
    {491246,512929},{490218,512929},{488757,512929},{487077,512929},{485840,512929},
    {485696,512929},{445525,512929},{445525,408944},{444724,406744},{443509,403405},
    {441482,402234},{438403,400457},{436097,400863},{432598,401480},{431092,403274},
    {428807,405996},{428807,409551},{428807,411892},{431092,414615},{432598,416409},
    {436097,417026},{438403,417432},{441482,415655},{443509,414484},{444724,411144},
    {445525,408944},{445525,512929},{444596,512929},{427449,512929},{426805,512929},
    {426742,512929},{426552,512906},{426470,512895},{423088,512486},{423071,512480},
    {422987,512447},{416980,510169},{416891,510108},{411608,506461},{411537,506381},
    {407278,501575},{407228,501480},{404244,495794},{404223,495708},{402827,490045},
    {402827,487257},{402827,398779},{403269,395139},{403270,395123},{405547,389119},
    {405585,389020},{409234,383733},{409295,383645},{414100,379387},{414181,379316},
    {419867,376331},{419962,376282},{419957,376283},{420039,376263},{425528,374910},
    {425675,374874},{425711,374865},{425852,374865},{426520,374865},{427317,374865},
    {427900,374865},{487792,374865},{489490,374865},{490971,374865},{492014,374865},
    {492669,374865},{495915,374865},{505263,358674},{505317,358581},{505309,358595},
    {543267,358595},{552290,374223},{552658,374865},{559086,374865},{560783,374865},
    {562028,374865},{562164,374865},{621126,374865},{621770,374865},{621834,374865},
    {625167,375270},{625468,375306},{625489,375308},{631158,377458},{631274,377502},
    {631398,377549},{631594,377624},{636880,381272},{636968,381333},{641226,386138},
    {641297,386219},{644282,391905},{644332,392000},{645727,397662},{645748,397748},
    {645748,510126},{645748,675973},{645748,679096},{645748,679662},{645748,683732},
    {645748,683932},
};

int main()
{
    vector<Point> points;
    for(unsigned int i=0; i<sizeof(data)/sizeof(data[0]); i++)
        points.push_back(Point(data[i][0], data[i][1]));
    Polygon p;
    gtl::set_points(p, points.begin(), points.end());
    vector<Polygon> pset;
    pset.push_back(p);

    // Pre-resize by half of the increment below.  This step (which is
    // an arbitrary artifact of the way the end user code works) is
    // important, without it the resizing is perfectly fast.  Why?
    //
    // Note: setting this value to -874 (which I did when writing the
    // test case via a roundoff bug in a hand conversion) produces
    // minimal splitting and fast operation.  But -873 (the value that
    // happens to be produced by my end code) is a disaster.  Why?
    gtl::resize(pset, -873, true, 7);

    // Iteratively shrink, reporting vertex count and time elapsed at
    // each stage.  Note three things:
    //
    // 1. The vertex count is exploding far faster than it should.  As
    // documented, each acute vertex should split into N segments,
    // which won't need to be split farther.  Instead we're seeing a
    // near-doubling with each iteration.
    //
    // 2. The time complexity appears to be polynomial, not NlogN.
    //
    // 3. The number of new vertices is oddly sensitive to the value
    // of num_circle_segments.  Passing in 7 below leads to a serious
    // performance regression, but 6 is much faster.  I've observed
    // exactly the opposite on other input data.

    while(!gtl::empty(pset)) {
        time_t start = time(NULL);
        gtl::resize(pset, -1747, true, 7);
        time_t end = time(NULL);

        int n=0;
        for(unsigned int i=0; i<pset.size(); i++)
            n += pset[i].size();

        printf("%d vertices, %ld secs\n", n, end-start);
    }
    return 0;
}