Geometry Boost List: [ggl] Severe precision problems with unions

Subject: [ggl] Severe precision problems with unions
From: V D (zedxz2)
Date: 2011-10-15 18:12:39

Hi all,

I'm having considerable problems using mostly bg::union_ with double floating precision.
Sometimes the union of 2 side-by-side polygons sharing an edge would give me a self intersecting polygon. I have found that truncating the precision (using bitmasks) helps avoiding these. I am truncating 39 bits right now using 0xFFFFFF8000000000. 

I'm having a second type of problem with bg::union_ and precision.
The small main program below illustrates the problem.

The first polygon and multi-polygon were output using std::setprecision(20) and are obviously closer to the actual values in my double variables at runtime. Notice that the result of the union will contain the Polygon only. 
The second polygon and multi-polygon obviously have less precision. Notice that the result of the union is correct, it contains both the polygon and multipolygon.

Should I be truncating the precision more to avoid these problems? Any other solutions ? How to solve this ?

Thank you so much
-v

int main()
{
  typedef boost::geometry::model::d2::point_xy<double> Point;
  typedef boost::geometry::model::polygon<Point > Poly;
  typedef boost::geometry::model::multi_polygon<Poly > MultiPoly;
  
  Poly more_precision_p;
  bg::read_wkt("POLYGON((0.0051261282827810561447 1.4061168201146063694,-0.0248481132003921662 1.4073597410751779169,-0.024176593155787226563 1.4112175201924015422,-0.022529488862220822809 1.4147700436215686626,-0.020019047562341130142 1.4177752151318205875,-0.016816352598139596569 1.4200282379967557045,-0.013139659329529590828 1.4213755739831490654,-0.0092395319513548478108 1.4217254019915865904,-0.0053817543825411262581 1.4210538820111886515,-0.001829231400024942597 1.4194067777361432103,0.0011759414501799677483 1.4168963363807005607,0.0034289651713751752998 1.4136936404861550898,0.004776300301508376242 1.4100169481478890265,0.0051261282827810561447 1.4061168201146063694))", more_precision_p);
  
  MultiPoly more_precision_mp;
  bg::read_wkt("MULTIPOLYGON(((-0.52643984629333462344 0.0094957842833129132293,-0.5272900874715477082 0.0056734187709311170722,-0.52910065788723559255 0.0022013574695173929868,-0.53174817017451192491 -0.00068378544846160738135,-0.5350521998657952194 -0.0027853930486174890979,-0.53878758587590780404 -0.0039602456561389828144,-0.54269976408995102002 -0.0041282768000171742029,-0.5465221293496873578 -0.0032780354707765031741,-0.54999419020579509709 -0.0014674650943659849067,-0.55287933445969206225 0.0011800473107423763153,-0.55498094287190524732 0.0044840779711924037831,-0.5561557946673694186 0.0082194630121382346311,-0.55632382575363914512 0.012131641879316628491,-0.52936976307633576422 0.31772275448021147781,-0.5170401990715466356 0.40218339724398205481,-0.4709987138650222338 0.52119394352156256378,-0.44673904428991806359 0.56794058692473958772,-0.43772007903997722789 0.57572788731675716978,-0.40995283437272783678 0.60049235582922555476,-0.31980072436305168049 0.62332224268059688299,-0.094707446192857841494 0
.62514812522228235814,-0.070976610261311787187 0.63331246289715315001,-0.054203354696105494892 0.64502835735480590351,-0.024825891679756004193 0.67519370827643077071,0.011954343643283838611 0.75023204144345978506,0.011954343643283826468 0.75023204144345978506,0.017838069564264615735 0.77571962272561245655,0.020269698086962727873 0.81544107547962674243,0.020269698086962717465 0.81544107547962674243,0.016298068110543989517 0.96196017906682296239,0.0036735440928074569733 1.0816436905930537637,0.0036735440928074522028 1.0816436905930537637,-0.0303773850192074861 1.2740161424301239546,-0.024848113146062306145 1.4073597423853936306,0.0051261282827810544099 1.4061168201146063694,-0.0002679854641909522675 1.2760326856948760454,-0.00026798546419095140014 1.2760326856948760454,0.033397683934536293027 1.0858367781569462363,0.046255337651174760483 0.96394314124567703761,0.050294571932568532535 0.81493001827037325757,0.047629764908391630795 0.77139951789938754345,0.040410005721950546798 0.74012440386904021494,5.563920966
9416933579e-06 0.65769203391106922929,-0.034694350382019505108 0.62206148639519409649,-0.057242994230875712813 0.60631156054034684999,-0.089572949314954658506 0.59518878884021764186,-0.31594146313694837502 0.59335256200690311701,-0.39546708750227216322 0.57321369885827444524,-0.41793177642877277211 0.55317836268324283022,-0.42276779164758193641 0.54900277245026041228,-0.4436131025412277662 0.50883535335343743622,-0.4878426134284533644 0.39450849728726794519,-0.49956090098616423578 0.31423525333228852219,-0.52643984612136085488 0.0094957842681443072747,-0.52643984629333462344 0.0094957842833129132293)))", more_precision_mp);
  
  MultiPoly more_precision_result; 
  bg::union_(more_precision_mp, more_precision_p, more_precision_result);
  std::cout << "Union more precision: " << bg::wkt(more_precision_result) << std::endl;
      
   
   MultiPoly less_precision_mp;
   bg::read_wkt("MULTIPOLYGON(((-0.52644 0.00949578,-0.52729 0.00567342,-0.529101 0.00220136,-0.531748 -0.000683785,-0.535052 -0.00278539,-0.538788 -0.00396025,-0.5427 -0.00412828,-0.546522 -0.00327804,-0.549994 -0.00146747,-0.552879 0.00118005,-0.554981 0.00448408,-0.556156 0.00821946,-0.556324 0.0121316,-0.52937 0.317723,-0.51704 0.402183,-0.470999 0.521194,-0.446739 0.567941,-0.43772 0.575728,-0.409953 0.600492,-0.319801 0.623322,-0.0947074 0.625148,-0.0709766 0.633312,-0.0542034 0.645028,-0.0248259 0.675194,0.0119543 0.750232,0.0119543 0.750232,0.0178381 0.77572,0.0202697 0.815441,0.0202697 0.815441,0.0162981 0.96196,0.00367354 1.08164,0.00367354 1.08164,-0.0303774 1.27402,-0.0248481 1.40736,0.00512613 1.40612,-0.000267985 1.27603,-0.000267985 1.27603,0.0333977 1.08584,0.0462553 0.963943,0.0502946 0.81493,0.0476298 0.7714,0.04041 0.740124,5.56392e-06 0.657692,-0.0346944 0.622061,-0.057243 0.606312,-0.0895729 0.595189,-0.315941 0.593353,-0.395467 0.573214,-0.417932 0.553178,-0.422768 0.549003,-0.443613 0.
508835,-0.487843 0.394508,-0.499561 0.314235,-0.52644 0.00949578,-0.52644 0.00949578)))", less_precision_mp);
   
   Poly less_precision_end_cap;
   bg::read_wkt("POLYGON((0.00512613 1.40612,-0.0248481 1.40736,-0.0241766 1.41122,-0.0225295 1.41477,-0.020019 1.41778,-0.0168164 1.42003,-0.0131397 1.42138,-0.00923953 1.42173,-0.00538175 1.42105,-0.00182923 1.41941,0.00117594 1.4169,0.00342897 1.41369,0.0047763 1.41002,0.00512613 1.40612))", less_precision_end_cap);
   
   MultiPoly less_precision_result;
   bg::union_(less_precision_mp, less_precision_end_cap, less_precision_result);
   
   std::cout << "Union less precision: " << bg::wkt(less_precision_result) << std::endl;
   
  return 0;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/ggl/attachments/20111015/c913ce65/attachment.html