Skip to Content.
Sympa Menu

cgal-discuss - [cgal-discuss] Problem with partitioning

Subject: CGAL users discussion list

List archive

[cgal-discuss] Problem with partitioning


Chronological Thread 
  • From: Kostis <>
  • To:
  • Subject: [cgal-discuss] Problem with partitioning
  • Date: Mon, 19 Jul 2010 05:54:33 -0700 (PDT)

Hi All!
I am trying to partition a polygon using the approx_convex_partition_2
function.
I just modified the approx_convex_partition_2.cpp file from the examples and
added the polygon that I want to partition by hand.

I checked that the polygon (191 vertices) that I am inserting is simple and
counterclockwise-oriented.

The result of the partitioning is 100 polygons that should be convex.
Instead, the first few polygons are convex partitions of the initial
polygon, but afterwards I get some polygons that are the initial polygon
with some more vertices that are outside the initial polygon!

Can anybody help me with this?
Is there a known problem with this function?
Am I doing something wrong?

Thank you very much for your help!!

Cheers,
Kostis

P.S. You can reproduce the problem that I have, if you change the
make_polygon function at the <CGAL>/examples/approx_convex_partition_2.cpp
file with the following one:

void make_polygon(Polygon_2& polygon) {
polygon.push_back(Point_2(590373.084673678,5628280.449842133));
polygon.push_back(Point_2(590374.0741749936,5628281.469634557));
polygon.push_back(Point_2(600372.9932141311,5628416.792090064));
polygon.push_back(Point_2(600237.5964507912,5638415.9167972375));
polygon.push_back(Point_2(600237.5964507912,5638415.9167972375));
polygon.push_back(Point_2(600102.2244249843,5648415.91132736));
polygon.push_back(Point_2(600103.2139262998,5648416.92112182));
polygon.push_back(Point_2(610103.1307125972,5648552.51352238));
polygon.push_back(Point_2(610103.1389584414,5648552.51352238));
polygon.push_back(Point_2(620103.4432994208,5648688.235896485));
polygon.push_back(Point_2(620103.451545265,5648688.235896485));
polygon.push_back(Point_2(630103.9620323516,5648824.018258379));
polygon.push_back(Point_2(630104.4650288537,5648823.888284834));
polygon.push_back(Point_2(630104.9762712001,5648823.02845985));
polygon.push_back(Point_2(630240.5297055815,5638823.433848323));
polygon.push_back(Point_2(640240.2073623943,5638958.75630383));
polygon.push_back(Point_2(640240.2073623943,5638958.75630383));
polygon.push_back(Point_2(650240.9982081869,5639094.34870439));
polygon.push_back(Point_2(650240.9982081869,5639094.34870439));
polygon.push_back(Point_2(660242.0611668414,5639229.901113091));
polygon.push_back(Point_2(660242.0694126857,5639229.901113091));
polygon.push_back(Point_2(660242.0694126857,5639229.901113091));
polygon.push_back(Point_2(670242.208836779,5639365.4735177215));
polygon.push_back(Point_2(670106.6141731761,5649365.757988828));
polygon.push_back(Point_2(670107.6036744916,5649366.777781253));
polygon.push_back(Point_2(680108.9882210736,5649502.560143147));
polygon.push_back(Point_2(680108.9964669179,5649502.560143147));
polygon.push_back(Point_2(690110.4717177872,5649638.42248876));
polygon.push_back(Point_2(690110.4717177872,5649638.42248876));
polygon.push_back(Point_2(700112.0541646323,5649774.11486897));
polygon.push_back(Point_2(700112.54891529,5649773.994893391));
polygon.push_back(Point_2(700113.0684034807,5649773.135068405));
polygon.push_back(Point_2(700248.7785089038,5639772.380692947));
polygon.push_back(Point_2(710248.497394938,5639907.963095541));
polygon.push_back(Point_2(710112.7460602935,5649908.89743437));
polygon.push_back(Point_2(710113.7273157648,5649909.917226794));
polygon.push_back(Point_2(720115.647842226,5650045.679592758));
polygon.push_back(Point_2(720115.647842226,5650045.679592758));
polygon.push_back(Point_2(730117.8239898604,5650181.441958723));
polygon.push_back(Point_2(730117.8239898604,5650181.441958723));
polygon.push_back(Point_2(730117.8239898604,5650181.441958723));
polygon.push_back(Point_2(740120.1073334706,5650317.244316546));
polygon.push_back(Point_2(740120.6103299727,5650317.114343002));
polygon.push_back(Point_2(740121.1215723191,5650316.254518017));
polygon.push_back(Point_2(740256.8069402092,5640314.830278907));
polygon.push_back(Point_2(750257.234968853,5640450.502663187));
polygon.push_back(Point_2(750121.5660926513,5650452.026881946));
polygon.push_back(Point_2(750121.5660926513,5650452.026881946));
polygon.push_back(Point_2(749985.6993161866,5660454.65087685));
polygon.push_back(Point_2(749986.6888175021,5660455.660671309));
polygon.push_back(Point_2(759988.403197856,5660591.563008782));
polygon.push_back(Point_2(759852.2972919067,5670593.327178701));
polygon.push_back(Point_2(759853.2867932222,5670594.346971125));
polygon.push_back(Point_2(769856.0483958017,5670730.629231267));
polygon.push_back(Point_2(769856.056641646,5670730.629231267));
polygon.push_back(Point_2(769856.056641646,5670730.629231267));
polygon.push_back(Point_2(779858.9501777341,5670867.031466987));
polygon.push_back(Point_2(779858.9501777341,5670867.031466987));
polygon.push_back(Point_2(789860.9201792611,5671003.423704742));
polygon.push_back(Point_2(789724.6081272045,5681005.577795294));
polygon.push_back(Point_2(789724.6081272045,5681005.577795294));
polygon.push_back(Point_2(789588.1641416391,5691007.791873635));
polygon.push_back(Point_2(779586.1858942677,5690871.23966844));
polygon.push_back(Point_2(779586.1776484235,5690871.23966844));
polygon.push_back(Point_2(769583.3665707782,5690734.627475455));
polygon.push_back(Point_2(769583.3665707782,5690734.627475455));
polygon.push_back(Point_2(769583.3665707782,5690734.627475455));
polygon.push_back(Point_2(759580.7121641746,5690597.885308927));
polygon.push_back(Point_2(759580.7121641746,5690597.885308927));
polygon.push_back(Point_2(749578.9977838208,5690461.323105767));
polygon.push_back(Point_2(749715.4582610748,5680459.808884973));
polygon.push_back(Point_2(749714.9717562613,5680458.939062023));
polygon.push_back(Point_2(749714.4687597593,5680458.799090513));
polygon.push_back(Point_2(739712.0204992631,5680322.436846652));
polygon.push_back(Point_2(739711.0062604147,5680323.426645182));
polygon.push_back(Point_2(739574.6282416036,5690325.790692997));
polygon.push_back(Point_2(739574.6282416036,5690325.790692997));
polygon.push_back(Point_2(739438.0853059067,5700327.144946353));
polygon.push_back(Point_2(729436.8986595877,5700190.442771683));
polygon.push_back(Point_2(729435.8844207394,5700191.4325702125));
polygon.push_back(Point_2(729299.1518306236,5710193.656646519));
polygon.push_back(Point_2(729300.1330860949,5710194.666440978));
polygon.push_back(Point_2(739301.4351742339,5710331.518585121));
polygon.push_back(Point_2(739164.5129296993,5720332.972818126));
polygon.push_back(Point_2(739165.4941851705,5720333.982612586));
polygon.push_back(Point_2(749167.6126118948,5720471.164689572));
polygon.push_back(Point_2(749167.6208577391,5720471.164689572));
polygon.push_back(Point_2(759170.3000018756,5720608.196797084));
polygon.push_back(Point_2(759170.8029983777,5720608.076821504));
polygon.push_back(Point_2(759171.3142407241,5720607.216996519));
polygon.push_back(Point_2(759308.2282394143,5710605.4528266005));
polygon.push_back(Point_2(769309.9426197682,5710742.374956499));
polygon.push_back(Point_2(769309.9508656125,5710742.374956499));
polygon.push_back(Point_2(769309.9508656125,5710742.374956499));
polygon.push_back(Point_2(779353.72729772,5710847.843488685));
polygon.push_back(Point_2(779354.2385400664,5710847.703517175));
polygon.push_back(Point_2(779354.7497824128,5710846.853690156));
polygon.push_back(Point_2(779450.5664931319,5700876.273172895));
polygon.push_back(Point_2(789451.5140099663,5701012.955351634));
polygon.push_back(Point_2(789376.2954182985,5710968.0490211975));
polygon.push_back(Point_2(789377.3179029911,5710969.038819727));
polygon.push_back(Point_2(799355.4244311256,5711125.237026035));
polygon.push_back(Point_2(799355.4244311256,5711125.237026035));
polygon.push_back(Point_2(799355.4244311256,5711125.237026035));
polygon.push_back(Point_2(809357.5593495385,5711263.138956497));
polygon.push_back(Point_2(809357.5593495385,5711263.138956497));
polygon.push_back(Point_2(819428.6295262658,5711348.621556762));
polygon.push_back(Point_2(819429.1325227679,5711348.491583218));
polygon.push_back(Point_2(819429.6437651142,5711347.631758233));
polygon.push_back(Point_2(819558.0315608025,5701350.136719345));
polygon.push_back(Point_2(819558.0315608025,5701350.136719345));
polygon.push_back(Point_2(819618.2592075402,5691404.981026935));
polygon.push_back(Point_2(819617.7479651939,5691404.12120195));
polygon.push_back(Point_2(819617.220231159,5691404.00122637));
polygon.push_back(Point_2(809596.6063756788,5691281.296202622));
polygon.push_back(Point_2(809733.2565073515,5681278.922156842));
polygon.push_back(Point_2(809733.2565073515,5681278.922156842));
polygon.push_back(Point_2(809869.5190843424,5671275.238377655));
polygon.push_back(Point_2(809869.5108384981,5671275.22837969));
polygon.push_back(Point_2(809869.5190843424,5671275.22837969));
polygon.push_back(Point_2(810105.8367360206,5661193.580469875));
polygon.push_back(Point_2(810105.3502312072,5661192.710646925));
polygon.push_back(Point_2(810104.8472347051,5661192.570675416));
polygon.push_back(Point_2(800005.3948619112,5661131.143178804));
polygon.push_back(Point_2(800005.3948619112,5661131.143178804));
polygon.push_back(Point_2(800005.3948619112,5661131.143178804));
polygon.push_back(Point_2(789999.2359714818,5660998.150249129));
polygon.push_back(Point_2(790220.0184525064,5650929.459701881));
polygon.push_back(Point_2(790219.4989643157,5650928.60987486));
polygon.push_back(Point_2(790218.9712302808,5650928.489899281));
polygon.push_back(Point_2(780132.2504410797,5650858.864071417));
polygon.push_back(Point_2(780268.9830311956,5640856.040117214));
polygon.push_back(Point_2(780268.5047722264,5640855.1602962995));
polygon.push_back(Point_2(780268.0017757243,5640855.02032479));
polygon.push_back(Point_2(770263.9290839018,5640720.0278021265));
polygon.push_back(Point_2(770263.9290839018,5640720.0278021265));
polygon.push_back(Point_2(770263.9208380575,5640720.0278021265));
polygon.push_back(Point_2(760261.9260989976,5640584.235442267));
polygon.push_back(Point_2(760496.1740437575,5630504.807080669));
polygon.push_back(Point_2(760495.6875389441,5630503.937257719));
polygon.push_back(Point_2(760495.184542442,5630503.797286211));
polygon.push_back(Point_2(750401.3146062364,5630440.060259697));
polygon.push_back(Point_2(750401.3146062364,5630440.060259697));
polygon.push_back(Point_2(740392.3521287465,5630310.516627927));
polygon.push_back(Point_2(740623.5573569611,5620233.217832863));
polygon.push_back(Point_2(740623.0708521476,5620232.348009913));
polygon.push_back(Point_2(740622.5678556456,5620232.208038404));
polygon.push_back(Point_2(730524.3770970289,5620172.850120536));
polygon.push_back(Point_2(730524.3770970289,5620172.850120536));
polygon.push_back(Point_2(730524.3688511846,5620172.850120536));
polygon.push_back(Point_2(720522.2421786159,5620037.627644679));
polygon.push_back(Point_2(720522.2339327716,5620037.627644679));
polygon.push_back(Point_2(710552.5134282862,5619876.630415197));
polygon.push_back(Point_2(710551.4497143719,5619877.650207622));
polygon.push_back(Point_2(710383.9848625651,5629904.099352985));
polygon.push_back(Point_2(700383.1610333952,5629768.606932074));
polygon.push_back(Point_2(700383.1610333952,5629768.606932074));
polygon.push_back(Point_2(700383.1527875509,5629768.606932074));
polygon.push_back(Point_2(690381.4878822629,5629633.104513198));
polygon.push_back(Point_2(690381.4878822629,5629633.104513198));
polygon.push_back(Point_2(680379.996139705,5629497.632088218));
polygon.push_back(Point_2(680379.9878938607,5629497.632088218));
polygon.push_back(Point_2(670379.6753070372,5629362.119671377));
polygon.push_back(Point_2(670587.7426961574,5619304.1469425475));
polygon.push_back(Point_2(670587.2644371882,5619303.257123668));
polygon.push_back(Point_2(670586.7696865305,5619303.117152158));
polygon.push_back(Point_2(660512.8134642997,5619225.712907568));
polygon.push_back(Point_2(660512.8134642997,5619225.722905532));
polygon.push_back(Point_2(660512.8052184553,5619225.712907568));
polygon.push_back(Point_2(650511.7340139565,5619090.49043171));
polygon.push_back(Point_2(650511.7340139565,5619090.49043171));
polygon.push_back(Point_2(640511.7512609048,5618955.307947713));
polygon.push_back(Point_2(640651.5348134101,5608951.984095263));
polygon.push_back(Point_2(640651.0483085967,5608951.114272313));
polygon.push_back(Point_2(640650.5535579389,5608950.974300805));
polygon.push_back(Point_2(630646.1015572788,5608819.691023135));
polygon.push_back(Point_2(630800.8760547142,5598804.269633103));
polygon.push_back(Point_2(630800.4060415893,5598803.389812188));
polygon.push_back(Point_2(630799.9030450872,5598803.24984068));
polygon.push_back(Point_2(620779.4705981815,5598684.334045645));
polygon.push_back(Point_2(620779.4623523372,5598684.334045645));
polygon.push_back(Point_2(610809.0986719966,5598525.57636031));
polygon.push_back(Point_2(610808.0432039268,5598526.596152735));
polygon.push_back(Point_2(610643.3572016477,5608549.685981877));
polygon.push_back(Point_2(600644.3062290014,5608414.753447004));
polygon.push_back(Point_2(600644.3062290014,5608414.753447004));
polygon.push_back(Point_2(590686.8555408283,5608245.687859813));
polygon.push_back(Point_2(590685.816564447,5608246.697654272));
polygon.push_back(Point_2(590508.316520132,5618280.635275378));
polygon.push_back(Point_2(590508.316520132,5618280.645273343));
}
--
View this message in context:
http://cgal-discuss.949826.n4.nabble.com/Problem-with-partitioning-tp2293936p2293936.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

Archive powered by MHonArc 2.6.16.

Top of Page