Slow StraightSkeleton computation with a 420 vertices single-ring polygon about sfcgal HOT 11 CLOSED

Here's a test for the C-API: http://strk.keybit.net/tmp/issue80.patch

from sfcgal.

NOTE: with a Debug build (no optimization flags) it take ~6.2 minutes to run that test on an Intel(R) Core(TM) i7-4750HQ CPU @ 2.00GHz

from sfcgal.

Sorry, I just found out that the ~6.2 minutes was due to LD_PROFILE env variable being set.
W/out that variable, the test runs in ~15 seconds (same as when triggered by PostGIS)

from sfcgal.

The skeleton returns 835 components (segments) from the 420 input vertices.
Is 15 seconds the expected timing for this kind of input ?

from sfcgal.

@strk I tryied your polygon with pure CGAL code, and it takes 33sec on my machine:

//g++ -O3 slow_straight_skeleton.cpp -lCGAL -lCGAL_Core -lboost_thread -lgmp -lmpfr
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/create_straight_skeleton_from_polygon_with_holes_2.h>

const double POLY[] = {
1684000, 5402672.31399816,
1683946.034501, 5402654.436405,
1683891.240865, 5402626.55208,
1683828.852807, 5402603.566759,
1683763.966259, 5402588.179891,
1683710.005454, 5402593.368835,
1683643.321311, 5402617.6139,
1683558.455081, 5402667.62372,
1683479.657793, 5402723.692308,
1683393.274328, 5402782.790279,
1683344.780518, 5402828.261023,
1683302.347403, 5402879.780536,
1683275.07015, 5402920.702207,
1683275.07015, 5402961.61388,
1683285.674306, 5403005.564933,
1683312.951559, 5403060.123828,
1683325.081196, 5403107.104265,
1683319.0205, 5403163.172853,
1683291.735002, 5403213.182673,
1683214.454949, 5403316.231698,
1683131.097709, 5403404.133806,
1683071.999743, 5403438.986712,
1682985.616278, 5403446.565169,
1682940.462035, 5403442.675961,
1682880.415797, 5403428.688808,
1682817.343333, 5403380.938527,
1682774.09388, 5403321.470632,
1682729.94563, 5403243.986403,
1682692.10545, 5403159.283644,
1682682.878351, 5403080.789622,
1682680.67671, 5403039.198087,
1682654.257025, 5402965.563076,
1682628.876316, 5402937.928701,
1682608.979094, 5402917.832791,
1682537.124807, 5402882.669948,
1682377.221394, 5402803.686025,
1682327.432986, 5402778.391174,
1682247.745147, 5402720.312996,
1682225.349434, 5402712.624561,
1682183.51002, 5402714.684141,
1682145.917216, 5402727.481536,
1682113.964569, 5402740.648856,
1682089.985654, 5402764.224058,
1682069.700877, 5402801.616447,
1682051.708445, 5402871.502221,
1682004.624674, 5402975.481057,
1681970.354945, 5403065.972638,
1681952.560413, 5403113.362991,
1681928.037272, 5403171.901076,
1681920.830404, 5403207.043923,
1681928.936069, 5403248.485488,
1681963.684057, 5403315.911763,
1681985.700461, 5403387.247243,
1681982.097027, 5403427.788991,
1681972.696765, 5403453.58374,
1681959.998165, 5403485.977147,
1681917.119774, 5403543.165506,
1681871.734647, 5403590.355901,
1681801.356366, 5403642.355317,
1681698.275067, 5403702.603053,
1681626.709384, 5403743.754677,
1681565.82207, 5403762.980764,
1681486.530031, 5403783.696547,
1681395.528893, 5403795.414162,
1681308.13119, 5403794.514345,
1681281.134295, 5403807.881624,
1681309.029987, 5403814.330312,
1681347.777209, 5403821.538844,
1681443.280578, 5403812.530678,
1681535.188758, 5403799.913246,
1681627.995736, 5403769.279482,
1681693.294577, 5403734.146633,
1681743.478785, 5403709.551639,
1681819.010719, 5403658.462038,
1681882.981979, 5403607.092494,
1681939.746371, 5403555.732948,
1681968.582088, 5403515.1912,
1681992.008532, 5403477.348903,
1682001.920037, 5403427.788991,
1682003.725877, 5403371.030544,
1681981.181738, 5403316.111723,
1681950.564919, 5403242.18677,
1681946.961485, 5403179.109609,
1682053.819381, 5402931.490011,
1682074.706105, 5402867.003137,
1682087.000658, 5402829.21083,
1682109.882876, 5402779.320985,
1682132.47649, 5402759.525014,
1682162.573821, 5402744.718028,
1682197.659889, 5402742.418496,
1682230.057811, 5402752.7164,
1682274.948187, 5402775.501762,
1682361.422357, 5402825.011685,
1682456.810283, 5402864.263695,
1682563.989768, 5402917.532852,
1682603.784212, 5402945.227215,
1682636.380035, 5402982.409647,
1682648.855997, 5403036.748586,
1682663.269733, 5403154.78456,
1682694.397795, 5403228.449566,
1682727.240993, 5403287.227602,
1682756.07671, 5403341.296596,
1682792.11105, 5403388.14706,
1682830.858272, 5403421.480275,
1682900.37074, 5403459.87246,
1682942.762625, 5403465.171382,
1682975.012122, 5403470.810234,
1683049.26595, 5403469.290543,
1683114.432858, 5403443.535786,
1683203.842547, 5403370.790593,
1683279.613611, 5403273.800335,
1683328.107421, 5403210.15329,
1683356.901909, 5403151.045321,
1683353.875684, 5403104.074882,
1683331.141892, 5403043.457221,
1683309.925334, 5402970.712028,
1683311.44257, 5402916.263111,
1683346.297753, 5402870.692386,
1683408.43019, 5402805.525651,
1683487.235724, 5402746.42768,
1683575.128178, 5402690.349095,
1683641.804075, 5402647.917731,
1683706.970983, 5402616.094209,
1683741.826167, 5402610.035442,
1683781.26604, 5402615.764276,
1683816.261403, 5402623.462709,
1683915.838219, 5402676.741864,
1684000, 5402711.41802501,
1684020.618162, 5402719.913077,
1684068.00703, 5402732.710472,
1684222.971181, 5402746.287709,
1684311.424353, 5402765.24385,
1684450.572976, 5402802.756215,
1684578.837084, 5402854.785624,
1684651.433497, 5402882.619959,
1684708.305085, 5402894.717496,
1684763.964534, 5402883.829712,
1684819.632229, 5402849.946609,
1684837.781332, 5402820.902521,
1684835.357054, 5402777.341388,
1684817.207951, 5402736.199762,
1684749.451848, 5402674.492322,
1684704.676914, 5402623.672666,
1684682.899639, 5402545.018676,
1684682.899639, 5402476.052714,
1684692.58026, 5402430.072073,
1684739.771227, 5402376.822912,
1684837.781332, 5402305.437442,
1684921.270506, 5402277.603108,
1684981.770265, 5402275.1836,
1685015.652439, 5402295.759412,
1685031.38551, 5402317.53498,
1685032.589404, 5402344.159561,
1685010.812129, 5402370.774143,
1684991.450886, 5402409.496261,
1684989.026608, 5402463.955177,
1684972.089644, 5402600.687345,
1684985.398437, 5402732.580499,
1684986.610576, 5402973.371486,
1684959.984745, 5403060.493753,
1684920.058367, 5403131.88922,
1684881.335882, 5403191.177153,
1684863.186778, 5403244.416316,
1684864.398918, 5403295.235972,
1684898.281092, 5403346.055628,
1684949.10023, 5403360.582671,
1684989.991372, 5403370.170719,
1685072.524028, 5403369.050947,
1685162.065651, 5403366.631439,
1685254.023306, 5403340.006859,
1685345.989208, 5403307.333509,
1685395.596207, 5403272.25065,
1685445.211452, 5403216.581982,
1685470.616898, 5403177.869861,
1685479.085381, 5403110.103655,
1685482.045639, 5403068.682086,
1685463.360556, 5403033.869172,
1685454.883828, 5402967.322718,
1685471.829038, 5402909.244539,
1685532.328797, 5402824.54178,
1685646.071973, 5402744.678036,
1685708.996011, 5402691.438873,
1685723.508697, 5402658.765523,
1685736.825736, 5402615.20439,
1685746.506357, 5402540.189659,
1685759.81515, 5402501.467541,
1685788.857013, 5402491.789511,
1685819.10277, 5402497.83828,
1685850.568912, 5402523.243109,
1685873.558326, 5402570.433503,
1685896.54774, 5402610.355377,
1685964.303842, 5402718.053456,
1686003.026327, 5402812.434245,
1686041.748812, 5402911.654049,
1686076.843125, 5402947.956659,
1686111.929193, 5402947.956659,
1686147.023506, 5402931.010109,
1686182.109574, 5402901.976019,
1686202.682955, 5402819.692767,
1686214.779609, 5402689.009367,
1686209.939298, 5402592.209071,
1686193.002334, 5402489.360005,
1686178.481402, 5402415.54503,
1686177.269263, 5402357.466852,
1686222.044197, 5402317.53498,
1686324.894613, 5402263.086063,
1686418.064408, 5402230.412713,
1686484.616617, 5402243.720005,
1686519.710931, 5402271.554339,
1686541.488206, 5402312.695965,
1686559.637309, 5402416.754784,
1686598.359794, 5402483.311237,
1686663.699864, 5402560.745475,
1686704.838381, 5402610.355377,
1686724.199623, 5402659.965279,
1686748.401176, 5402754.356066,
1686777.44304, 5402892.297989,
1686816.165525, 5402980.630009,
1686864.560385, 5403039.917941,
1686942.005355, 5403090.737597,
1687020.654218, 5403104.054886,
1687121.088601, 5403129.459715,
1687190.056843, 5403153.664788,
1687232.440482, 5403171.661125,
1687258.83543, 5403191.157157,
1687296.032434, 5403231.338978,
1687323.334424, 5403271.630776,
1687350.331318, 5403336.817508,
1687355.138646, 5403374.309876,
1687354.940745, 5403406.803263,
1687349.539717, 5403432.697992,
1687329.213711, 5403462.211984,
1687315.904918, 5403514.241394,
1687305.012158, 5403550.544005,
1687302.868239, 5403577.968422,
1687302.58788, 5403647.344301,
1687337.682193, 5403723.578784,
1687378.82071, 5403747.773859,
1687485.299298, 5403757.461887,
1687540.966993, 5403757.461887,
1687609.935234, 5403746.564105,
1687666.509972, 5403770.889154,
1687709.800655, 5403791.874882,
1687749.595099, 5403819.559247,
1687766.993831, 5403837.255645,
1687789.191643, 5403882.346467,
1687788.993743, 5403907.341379,
1687781.30037, 5403937.335274,
1687766.103279, 5403964.729698,
1687735.915243, 5403994.523634,
1687698.231735, 5404019.328585,
1687665.635913, 5404034.025593,
1687635.645777, 5404041.324108,
1687597.558222, 5404039.734431,
1687563.065855, 5404038.334716,
1687503.176288, 5404027.946831,
1687339.207674, 5403984.07576,
1687303.42071, 5403984.07576,
1687268.425347, 5403991.384273,
1687241.733549, 5404002.382034,
1687194.897153, 5404036.974993,
1687157.386808, 5404074.487357,
1687138.025565, 5404115.628983,
1687142.865876, 5404156.770609,
1687175.535911, 5404259.619674,
1687225.14291, 5404338.273664,
1687369.140089, 5404431.4447,
1687438.108331, 5404471.376572,
1687479.246848, 5404489.522878,
1687531.888318, 5404490.732632,
1687547.802798, 5404451.100699,
1687563.304985, 5404415.957852,
1687535.508244, 5404415.757893,
1687520.517299, 5404420.656896,
1687488.020426, 5404417.967443,
1687440.631559, 5404400.071086,
1687393.242692, 5404374.786232,
1687306.15833, 5404316.708054,
1687273.859358, 5404283.914729,
1687256.559577, 5404251.321363,
1687221.861064, 5404213.539054,
1687212.254656, 5404148.452302,
1687219.956274, 5404128.556352,
1687250.14431, 5404101.261907,
1687282.731887, 5404083.95543,
1687317.8262, 5404074.157425,
1687360.317036, 5404071.957872,
1687385.31019, 5404077.146816,
1687462.697439, 5404102.731608,
1687512.683747, 5404103.031547,
1687550.169355, 5404095.823015,
1687628.084338, 5404107.160707,
1687687.743021, 5404083.215581,
1687762.219487, 5404046.013153,
1687805.402973, 5404008.720744,
1687854.358551, 5403919.598884,
1687851.934273, 5403865.149967,
1687851.934273, 5403840.944894,
1687834.997309, 5403804.652281,
1687819.264238, 5403765.930163,
1687790.271849, 5403734.876484,
1687732.987969, 5403696.994195,
1687695.593065, 5403681.697309,
1687658.099211, 5403673.908894,
1687625.610584, 5403673.708935,
1687580.621258, 5403678.417976,
1687512.939368, 5403697.914008,
1687467.950041, 5403697.624067,
1687447.953869, 5403692.525105,
1687410.558965, 5403672.239234,
1687393.259184, 5403649.643833,
1687380.956384, 5403612.051485,
1687380.420404, 5403608.582191,
1687367.92795, 5403548.124497,
1687370.352228, 5403520.290163,
1687389.738208, 5403461.882051,
1687404.737399, 5403458.482743,
1687417.229853, 5403434.787566,
1687417.518458, 5403387.297233,
1687430.316008, 5403344.805882,
1687430.711809, 5403292.316566,
1687420.9075, 5403262.222691,
1687406.106209, 5403237.127799,
1687366.311765, 5403194.346507,
1687339.01802, 5403174.150618,
1687244.33099, 5403120.971443,
1687211.941314, 5403108.284025,
1687167.042691, 5403080.489683,
1687108.860014, 5403058.404178,
1687067.366926, 5403044.806946,
1687056.465919, 5403042.517412,
1686997.664804, 5403038.708187,
1686939.581076, 5403022.981388,
1686857.304042, 5402935.859122,
1686793.176111, 5402754.356066,
1686775.018762, 5402684.170352,
1686745.985144, 5402628.511682,
1686720.571452, 5402588.57981,
1686652.807104, 5402515.974588,
1686611.668586, 5402447.008626,
1686585.051001, 5402405.867,
1686575.37038, 5402357.466852,
1686563.26548, 5402299.388674,
1686537.860034, 5402250.988525,
1686499.137549, 5402218.315176,
1686427.745029, 5402205.007884,
1686361.19282, 5402213.476161,
1686295.85275, 5402249.768774,
1686220.832058, 5402293.329907,
1686173.641091, 5402324.793502,
1686154.279849, 5402369.564389,
1686154.279849, 5402424.013307,
1686182.109574, 5402528.082124,
1686189.374162, 5402658.755525,
1686189.374162, 5402799.126953,
1686160.332299, 5402897.137004,
1686125.237985, 5402923.751586,
1686081.683436, 5402923.751586,
1686046.589123, 5402881.400207,
1686009.078777, 5402770.082865,
1685950.99505, 5402647.867742,
1685913.484704, 5402586.160302,
1685859.037394, 5402499.048033,
1685819.10277, 5402477.262468,
1685802.165806, 5402472.423453,
1685768.283632, 5402472.423453,
1685734.401458, 5402491.789511,
1685727.145115, 5402524.452862,
1685717.464493, 5402605.52636,
1685693.26294, 5402678.131582,
1685585.572214, 5402755.56582,
1685504.499073, 5402820.912519,
1685460.936277, 5402880.200451,
1685433.106553, 5402935.859122,
1685431.894414, 5402993.947298,
1685460.936277, 5403084.698826,
1685460.936277, 5403142.777004,
1685408.905, 5403229.899271,
1685337.51248, 5403281.92868,
1685229.821753, 5403319.441045,
1685108.822234, 5403347.265381,
1685005.971818, 5403344.845874,
1684916.430195, 5403326.699567,
1684889.804364, 5403294.026218,
1684899.484985, 5403226.27001,
1684946.675952, 5403143.986758,
1684981.770265, 5403067.752275,
1685003.54754, 5402989.098285,
1685019.280611, 5402887.458974,
1685015.652439, 5402772.512371,
1685007.175712, 5402592.219069,
1685019.280611, 5402466.374684,
1685031.38551, 5402392.559709,
1685042.270025, 5402371.983897,
1685054.374924, 5402341.740053,
1685054.374924, 5402318.744734,
1685045.906442, 5402289.710643,
1685007.183957, 5402259.456802,
1684949.10023, 5402241.300497,
1684875.291678, 5402258.247048,
1684795.430676, 5402294.549659,
1684711.941502, 5402363.515621,
1684667.166568, 5402415.54503,
1684650.229604, 5402485.730744,
1684663.538396, 5402594.628578,
1684697.420571, 5402662.394785,
1684771.229123, 5402726.521732,
1684808.739469, 5402774.92188,
1684812.36764, 5402816.063506,
1684780.909744, 5402851.156363,
1684740.97512, 5402870.512423,
1684690.155982, 5402868.092915,
1684630.868361, 5402843.89784,
1684517.61169, 5402795.847621,
1684435.32641, 5402765.263846,
1684290.578859, 5402730.590904,
1684228.067113, 5402721.292796,
1684133.289379, 5402698.207495,
1684030.810026, 5402682.520688
};

int main ()
{
    using namespace CGAL;
    typedef Exact_predicates_exact_constructions_kernel Kernel ;
    typedef Straight_skeleton_2<Kernel>  Straight_skeleton_2 ;

    Polygon_2<Kernel> outer;
    for (size_t i = 0; i<sizeof(POLY)/sizeof(double); i+=2)
    {
        outer.push_back ( Point_2<Kernel>(POLY[i], POLY[i+1]) );
    }
    std::cout << "nb of points: " << outer.size() << "\n";


    std::vector< Polygon_2<Kernel> > holes(2);

    Polygon_with_holes_2<Kernel> polygon( outer, holes.begin(), holes.end() );

    boost::shared_ptr< Straight_skeleton_2 > skeleton = create_interior_straight_skeleton_2( polygon );

    std::cerr << skeleton.get() << "\n";
    return 0;
}

from sfcgal.

Hey,
a naive question :
what is the point to use the exact kernel when you'll have to do a lot of
casting to/from double because of PostGIS?

What would be the timings with non-exact kernels?

Cheers,
Rémi-C

2015-06-15 19:13 GMT+02:00 Vincent Mora [email protected]:

@strk https://github.com/strk I tryied your polygon with pure CGAL
code, and it takes 33sec on my machine:

//g++ -O3 slow_straight_skeleton.cpp -lCGAL -lCGAL_Core -lboost_thread -lgmp -lmpfr
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/create_straight_skeleton_from_polygon_with_holes_2.h>
const double POLY[] = {1684000, 5402672.31399816,1683946.034501, 5402654.436405,1683891.240865, 5402626.55208,1683828.852807, 5402603.566759,1683763.966259, 5402588.179891,1683710.005454, 5402593.368835,1683643.321311, 5402617.6139,1683558.455081, 5402667.62372,1683479.657793, 5402723.692308,1683393.274328, 5402782.790279,1683344.780518, 5402828.261023,1683302.347403, 5402879.780536,1683275.07015, 5402920.702207,1683275.07015, 5402961.61388,1683285.674306, 5403005.564933,1683312.951559, 5403060.123828,1683325.081196, 5403107.104265,1683319.0205, 5403163.172853,1683291.735002, 5403213.182673,1683214.454949, 5403316.231698,1683131.097709, 5403404.133806,1683071.999743, 5403438.986712,1682985.616278, 5403446.565169,1682940.462035, 5403442.675961,1682880.415797, 5403428.688808,1682817.343333, 5403380.938527,1682774.09388, 5403321.470632,1682729.94563, 5403243.986403,1682692.10545, 5403159.283644,1682682.878351, 5403080.789622,1682680.67671, 5403039.198087,1682654.257025, 5402965.563076,1682628.876316, 5402937.928701,1682608.979094, 5402917.832791,1682537.124807, 5402882.669948,1682377.221394, 5402803.686025,1682327.432986, 5402778.391174,1682247.745147, 5402720.312996,1682225.349434, 5402712.624561,1682183.51002, 5402714.684141,1682145.917216, 5402727.481536,1682113.964569, 5402740.648856,1682089.985654, 5402764.224058,1682069.700877, 5402801.616447,1682051.708445, 5402871.502221,1682004.624674, 5402975.481057,1681970.354945, 5403065.972638,1681952.560413, 5403113.362991,1681928.037272, 5403171.901076,1681920.830404, 5403207.043923,1681928.936069, 5403248.485488,1681963.684057, 5403315.911763,1681985.700461, 5403387.247243,1681982.097027, 5403427.788991,1681972.696765, 5403453.58374,1681959.998165, 5403485.977147,1681917.119774, 5403543.165506,1681871.734647, 5403590.355901,1681801.356366, 5403642.355317,1681698.275067, 5403702.603053,1681626.709384, 5403743.754677,1681565.82207, 5403762.980764,1681486.530031, 5403783.696547,1681395.528893, 5403795.414162,1681308.13119, 5403794.514345,1681281.134295, 5403807.881624,1681309.029987, 5403814.330312,1681347.777209, 5403821.538844,1681443.280578, 5403812.530678,1681535.188758, 5403799.913246,1681627.995736, 5403769.279482,1681693.294577, 5403734.146633,1681743.478785, 5403709.551639,1681819.010719, 5403658.462038,1681882.981979, 5403607.092494,1681939.746371, 5403555.732948,1681968.582088, 5403515.1912,1681992.008532, 5403477.348903,1682001.920037, 5403427.788991,1682003.725877, 5403371.030544,1681981.181738, 5403316.111723,1681950.564919, 5403242.18677,1681946.961485, 5403179.109609,1682053.819381, 5402931.490011,1682074.706105, 5402867.003137,1682087.000658, 5402829.21083,1682109.882876, 5402779.320985,1682132.47649, 5402759.525014,1682162.573821, 5402744.718028,1682197.659889, 5402742.418496,1682230.057811, 5402752.7164,1682274.948187, 5402775.501762,1682361.422357, 5402825.011685,1682456.810283, 5402864.263695,1682563.989768, 5402917.532852,1682603.784212, 5402945.227215,1682636.380035, 5402982.409647,1682648.855997, 5403036.748586,1682663.269733, 5403154.78456,1682694.397795, 5403228.449566,1682727.240993, 5403287.227602,1682756.07671, 5403341.296596,1682792.11105, 5403388.14706,1682830.858272, 5403421.480275,1682900.37074, 5403459.87246,1682942.762625, 5403465.171382,1682975.012122, 5403470.810234,1683049.26595, 5403469.290543,1683114.432858, 5403443.535786,1683203.842547, 5403370.790593,1683279.613611, 5403273.800335,1683328.107421, 5403210.15329,1683356.901909, 5403151.045321,1683353.875684, 5403104.074882,1683331.141892, 5403043.457221,1683309.925334, 5402970.712028,1683311.44257, 5402916.263111,1683346.297753, 5402870.692386,1683408.43019, 5402805.525651,1683487.235724, 5402746.42768,1683575.128178, 5402690.349095,1683641.804075, 5402647.917731,1683706.970983, 5402616.094209,1683741.826167, 5402610.035442,1683781.26604, 5402615.764276,1683816.261403, 5402623.462709,1683915.838219, 5402676.741864,1684000, 5402711.41802501,1684020.618162, 5402719.913077,1684068.00703, 5402732.710472,1684222.971181, 5402746.287709,1684311.424353, 5402765.24385,1684450.572976, 5402802.756215,1684578.837084, 5402854.785624,1684651.433497, 5402882.619959,1684708.305085, 5402894.717496,1684763.964534, 5402883.829712,1684819.632229, 5402849.946609,1684837.781332, 5402820.902521,1684835.357054, 5402777.341388,1684817.207951, 5402736.199762,1684749.451848, 5402674.492322,1684704.676914, 5402623.672666,1684682.899639, 5402545.018676,1684682.899639, 5402476.052714,1684692.58026, 5402430.072073,1684739.771227, 5402376.822912,1684837.781332, 5402305.437442,1684921.270506, 5402277.603108,1684981.770265, 5402275.1836,1685015.652439, 5402295.759412,1685031.38551, 5402317.53498,1685032.589404, 5402344.159561,1685010.812129, 5402370.774143,1684991.450886, 5402409.496261,1684989.026608, 5402463.955177,1684972.089644, 5402600.687345,1684985.398437, 5402732.580499,1684986.610576, 5402973.371486,1684959.984745, 5403060.493753,1684920.058367, 5403131.88922,1684881.335882, 5403191.177153,1684863.186778, 5403244.416316,1684864.398918, 5403295.235972,1684898.281092, 5403346.055628,1684949.10023, 5403360.582671,1684989.991372, 5403370.170719,1685072.524028, 5403369.050947,1685162.065651, 5403366.631439,1685254.023306, 5403340.006859,1685345.989208, 5403307.333509,1685395.596207, 5403272.25065,1685445.211452, 5403216.581982,1685470.616898, 5403177.869861,1685479.085381, 5403110.103655,1685482.045639, 5403068.682086,1685463.360556, 5403033.869172,1685454.883828, 5402967.322718,1685471.829038, 5402909.244539,1685532.328797, 5402824.54178,1685646.071973, 5402744.678036,1685708.996011, 5402691.438873,1685723.508697, 5402658.765523,1685736.825736, 5402615.20439,1685746.506357, 5402540.189659,1685759.81515, 5402501.467541,1685788.857013, 5402491.789511,1685819.10277, 5402497.83828,1685850.568912, 5402523.243109,1685873.558326, 5402570.433503,1685896.54774, 5402610.355377,1685964.303842, 5402718.053456,1686003.026327, 5402812.434245,1686041.748812, 5402911.654049,1686076.843125, 5402947.956659,1686111.929193, 5402947.956659,1686147.023506, 5402931.010109,1686182.109574, 5402901.976019,1686202.682955, 5402819.692767,1686214.779609, 5402689.009367,1686209.939298, 5402592.209071,1686193.002334, 5402489.360005,1686178.481402, 5402415.54503,1686177.269263, 5402357.466852,1686222.044197, 5402317.53498,1686324.894613, 5402263.086063,1686418.064408, 5402230.412713,1686484.616617, 5402243.720005,1686519.710931, 5402271.554339,1686541.488206, 5402312.695965,1686559.637309, 5402416.754784,1686598.359794, 5402483.311237,1686663.699864, 5402560.745475,1686704.838381, 5402610.355377,1686724.199623, 5402659.965279,1686748.401176, 5402754.356066,1686777.44304, 5402892.297989,1686816.165525, 5402980.630009,1686864.560385, 5403039.917941,1686942.005355, 5403090.737597,1687020.654218, 5403104.054886,1687121.088601, 5403129.459715,1687190.056843, 5403153.664788,1687232.440482, 5403171.661125,1687258.83543, 5403191.157157,1687296.032434, 5403231.338978,1687323.334424, 5403271.630776,1687350.331318, 5403336.817508,1687355.138646, 5403374.309876,1687354.940745, 5403406.803263,1687349.539717, 5403432.697992,1687329.213711, 5403462.211984,1687315.904918, 5403514.241394,1687305.012158, 5403550.544005,1687302.868239, 5403577.968422,1687302.58788, 5403647.344301,1687337.682193, 5403723.578784,1687378.82071, 5403747.773859,1687485.299298, 5403757.461887,1687540.966993, 5403757.461887,1687609.935234, 5403746.564105,1687666.509972, 5403770.889154,1687709.800655, 5403791.874882,1687749.595099, 5403819.559247,1687766.993831, 5403837.255645,1687789.191643, 5403882.346467,1687788.993743, 5403907.341379,1687781.30037, 5403937.335274,1687766.103279, 5403964.729698,1687735.915243, 5403994.523634,1687698.231735, 5404019.328585,1687665.635913, 5404034.025593,1687635.645777, 5404041.324108,1687597.558222, 5404039.734431,1687563.065855, 5404038.334716,1687503.176288, 5404027.946831,1687339.207674, 5403984.07576,1687303.42071, 5403984.07576,1687268.425347, 5403991.384273,1687241.733549, 5404002.382034,1687194.897153, 5404036.974993,1687157.386808, 5404074.487357,1687138.025565, 5404115.628983,1687142.865876, 5404156.770609,1687175.535911, 5404259.619674,1687225.14291, 5404338.273664,1687369.140089, 5404431.4447,1687438.108331, 5404471.376572,1687479.246848, 5404489.522878,1687531.888318, 5404490.732632,1687547.802798, 5404451.100699,1687563.304985, 5404415.957852,1687535.508244, 5404415.757893,1687520.517299, 5404420.656896,1687488.020426, 5404417.967443,1687440.631559, 5404400.071086,1687393.242692, 5404374.786232,1687306.15833, 5404316.708054,1687273.859358, 5404283.914729,1687256.559577, 5404251.321363,1687221.861064, 5404213.539054,1687212.254656, 5404148.452302,1687219.956274, 5404128.556352,1687250.14431, 5404101.261907,1687282.731887, 5404083.95543,1687317.8262, 5404074.157425,1687360.317036, 5404071.957872,1687385.31019, 5404077.146816,1687462.697439, 5404102.731608,1687512.683747, 5404103.031547,1687550.169355, 5404095.823015,1687628.084338, 5404107.160707,1687687.743021, 5404083.215581,1687762.219487, 5404046.013153,1687805.402973, 5404008.720744,1687854.358551, 5403919.598884,1687851.934273, 5403865.149967,1687851.934273, 5403840.944894,1687834.997309, 5403804.652281,1687819.264238, 5403765.930163,1687790.271849, 5403734.876484,1687732.987969, 5403696.994195,1687695.593065, 5403681.697309,1687658.099211, 5403673.908894,1687625.610584, 5403673.708935,1687580.621258, 5403678.417976,1687512.939368, 5403697.914008,1687467.950041, 5403697.624067,1687447.953869, 5403692.525105,1687410.558965, 5403672.239234,1687393.259184, 5403649.643833,1687380.956384, 5403612.051485,1687380.420404, 5403608.582191,1687367.92795, 5403548.124497,1687370.352228, 5403520.290163,1687389.738208, 5403461.882051,1687404.737399, 5403458.482743,1687417.229853, 5403434.787566,1687417.518458, 5403387.297233,1687430.316008, 5403344.805882,1687430.711809, 5403292.316566,1687420.9075, 5403262.222691,1687406.106209, 5403237.127799,1687366.311765, 5403194.346507,1687339.01802, 5403174.150618,1687244.33099, 5403120.971443,1687211.941314, 5403108.284025,1687167.042691, 5403080.489683,1687108.860014, 5403058.404178,1687067.366926, 5403044.806946,1687056.465919, 5403042.517412,1686997.664804, 5403038.708187,1686939.581076, 5403022.981388,1686857.304042, 5402935.859122,1686793.176111, 5402754.356066,1686775.018762, 5402684.170352,1686745.985144, 5402628.511682,1686720.571452, 5402588.57981,1686652.807104, 5402515.974588,1686611.668586, 5402447.008626,1686585.051001, 5402405.867,1686575.37038, 5402357.466852,1686563.26548, 5402299.388674,1686537.860034, 5402250.988525,1686499.137549, 5402218.315176,1686427.745029, 5402205.007884,1686361.19282, 5402213.476161,1686295.85275, 5402249.768774,1686220.832058, 5402293.329907,1686173.641091, 5402324.793502,1686154.279849, 5402369.564389,1686154.279849, 5402424.013307,1686182.109574, 5402528.082124,1686189.374162, 5402658.755525,1686189.374162, 5402799.126953,1686160.332299, 5402897.137004,1686125.237985, 5402923.751586,1686081.683436, 5402923.751586,1686046.589123, 5402881.400207,1686009.078777, 5402770.082865,1685950.99505, 5402647.867742,1685913.484704, 5402586.160302,1685859.037394, 5402499.048033,1685819.10277, 5402477.262468,1685802.165806, 5402472.423453,1685768.283632, 5402472.423453,1685734.401458, 5402491.789511,1685727.145115, 5402524.452862,1685717.464493, 5402605.52636,1685693.26294, 5402678.131582,1685585.572214, 5402755.56582,1685504.499073, 5402820.912519,1685460.936277, 5402880.200451,1685433.106553, 5402935.859122,1685431.894414, 5402993.947298,1685460.936277, 5403084.698826,1685460.936277, 5403142.777004,1685408.905, 5403229.899271,1685337.51248, 5403281.92868,1685229.821753, 5403319.441045,1685108.822234, 5403347.265381,1685005.971818, 5403344.845874,1684916.430195, 5403326.699567,1684889.804364, 5403294.026218,1684899.484985, 5403226.27001,1684946.675952, 5403143.986758,1684981.770265, 5403067.752275,1685003.54754, 5402989.098285,1685019.280611, 5402887.458974,1685015.652439, 5402772.512371,1685007.175712, 5402592.219069,1685019.280611, 5402466.374684,1685031.38551, 5402392.559709,1685042.270025, 5402371.983897,1685054.374924, 5402341.740053,1685054.374924, 5402318.744734,1685045.906442, 5402289.710643,1685007.183957, 5402259.456802,1684949.10023, 5402241.300497,1684875.291678, 5402258.247048,1684795.430676, 5402294.549659,1684711.941502, 5402363.515621,1684667.166568, 5402415.54503,1684650.229604, 5402485.730744,1684663.538396, 5402594.628578,1684697.420571, 5402662.394785,1684771.229123, 5402726.521732,1684808.739469, 5402774.92188,1684812.36764, 5402816.063506,1684780.909744, 5402851.156363,1684740.97512, 5402870.512423,1684690.155982, 5402868.092915,1684630.868361, 5402843.89784,1684517.61169, 5402795.847621,1684435.32641, 5402765.263846,1684290.578859, 5402730.590904,1684228.067113, 5402721.292796,1684133.289379, 5402698.207495,1684030.810026, 5402682.520688
};
int main ()
{
using namespace CGAL;
typedef Exact_predicates_exact_constructions_kernel Kernel ;
typedef Straight_skeleton_2 Straight_skeleton_2 ;

Polygon_2<Kernel> outer;
for (size_t i = 0; i<sizeof(POLY)/sizeof(double); i+=2)
{
    outer.push_back ( Point_2<Kernel>(POLY[i], POLY[i+1]) );
}
std::cout << "nb of points: " << outer.size() << "\n";


std::vector< Polygon_2<Kernel> > holes(2);

Polygon_with_holes_2<Kernel> polygon( outer, holes.begin(), holes.end() );

boost::shared_ptr< Straight_skeleton_2 > skeleton = create_interior_straight_skeleton_2( polygon );

std::cerr << skeleton.get() << "\n";
return 0;

}

—
Reply to this email directly or view it on GitHub
#80 (comment).

from sfcgal.

Remi-C good point, using the Exact_predicates_inexact_constructions_kernel instead of the exact construction one gives a nice boost 1.3sec .vs. 33sec. I haven't tried with other kernels.

I think that the validity check and algorithm robustness may be a reason to use exact kernels... but I'm not sure... especially in this case, and considering the gain

@strk I'm not sure if SFCGAL builds globally with inexact construction kernel, but it's worth testing, and using it locally is pretty easy. Not sure about the consequences though... it may even fix things...

@mhugo your opinion ?

from sfcgal.

From the CGAL doc :
"Consider an input polygon with parallel edges separated a distance 2∗t. If you produce an offset polygon at distance t, these parallel edges will just collapse each other and vanish from the result, keeping the output as a simple polygon, just like the input. However, if you request an offset polygon at a distance t−epsilon, the result will still be a simple polygon but with edges that are so close to each other that will almost intersect. If a kernel with exact constructions is used, the offsetting algorithm can guarantee that the output contains only simple polygons. However, if inexact constructions are used the roundoff in the coordinates of the output points will cause parallel edges that almost collapse-but not so-to become really collinear or even cross each other.

Thus, it is neccessary to use a kernel with exact constructions if offset polygons must be simple, yet computing a straight skeleton using that kernel is very slow, much more than computing the offset polygons. To help with this, it is possible to construct the straight skeleton using the recommended kernel Exact_predicates_inexact_constructions_kernel, then convert the skeleton to a different kernel via the function convert_straight_skeleton_2() and input the converted skeleton to the offsetting functions.

All the offsetting functions that take polygons as input (and create the straight skeleton under the hood) apply that optimization automatically: that is, the output polygons are defined over the same kernel of the input polygons, whatever that is, yet the straight skeleton is constructed with the faster recommended kernel and converted if necessary.

Notice how some of the examples above use Exact_predicates_exact_constructions_kernel. In all cases, the straight skeleton is constructed using Exact_predicates_inexact_constructions_kernel.
"

That being said, currently only the exact kernel is used within SFCGAL. We might add support for an inexact version for some specific algorithms, and convert to exact coordinates when needed ... We did not make this choice initially, but it might be time to reconsider it. Not sure yet of the impacts.

from sfcgal.

The call in SFCGAL straightSkeleton.cpp is like this:

CGAL::create_interior_straight_skeleton_2( polygon ) ;

Bingo. From 15 seconds we're down to 0.065 seconds by using inexact construction and conversion.
I'll file a PR for further discussion

from sfcgal.

And, from PostGIS:

skeleton=# select 
st_numgeometries(st_straightSkeleton(st_removerepeatedpoints(shape,st_length(st_boundary(shape))*1e-3))) from test_poly;         
 st_numgeometries 
------------------
              795
(1 row)

Time: 321.069 ms

Used to be ~15 seconds and 860 componets in output.

from sfcgal.

Oops, sorry, I was simplifying the input.
This is a run without simplifying the input:

skeleton=# select st_numgeometries(st_straightSkeleton(shape)) from test_poly;
 st_numgeometries 
------------------
              835
(1 row)

Time: 234.980 ms

And this is a run with exact construction:

skeleton=# select st_numgeometries(st_straightSkeleton(shape)) from test_poly;
 st_numgeometries
------------------
              835
(1 row)

Time: 15624.645 ms

So, same number of components in output, 0.9% of the time to run...

from sfcgal.