Rejection sampling via complex hull vs. rejection sampling via envelope

readme.md

Introduction

The following branch: https://github.com/BoostGSoC19/geometry/tree/feature/uniform_point_distribution

contains a distribution class and strategies for random sampling of points in geometries including two strategies for random sampling in polygons. The first strategy is based on computing and envelope, generating random points in it, and accepting those that also happen to lie inside the original polygons. The second strategy uses the convex hull and implicitly computes its fan triangulation, choses triangles randomly (based on area) and samples uniformly on those.

Expectation

My expectations for the performance were the following:

n - number of vertices in polygon

h - number of vertices in convex hull

using envelope:

Constructing the distribution: O(n) (fastest)

Obtaining a sample (regardless of acceptance/rejection): O(1) + O(n) = O(n) (fastest)

O(1) to sample in the envelope, O(n) to evaluate within(sample, polygon)

Expected number of samples to have k accepted samples: k / (area of envelope / area of polygon) (more)

using convex hull:

Constructing the distribution: depends on bg::convex_hull, probably O(n log h) or O(n log n) plus O(h) to build the triangle cache

Obtaining a sample (regardless of acceptance/rejection): O(log h) + O(n) = O(n) (slowest)

Expected number of samples to have k accepted samples: k / (area of hull / area of polygon) (fewer)

The work per sample is probably dominated by the evaluation of within(sample, polygon) and slightly faster for envelope. The number of samples is probably significantly lower for convex hull than for envelope. Construction of the distribution is certainly much faster for envelope but irrelevant if many samples are generated from the same distribution.

A third option

If an algorithm was available to compute the triangulation of the interior of the polygon, it would probably be even more initial work than for convex hull but much less work per sample ( I expect O(log n) work per sample) and it would not be necessary to generate more than k samples.

Result

With the appended benchmark, the following results were obtained (number of samples reduced for big_polygon.wkt

Polygon with 2374 vertices

g++ -I../boost/ -O3 -o rejection_sampling_benchmark rejection_sampling_benchmark.cpp && ./rejection_sampling_benchmark big_polygon.wkt

Envelope acceptance probability: 0.652191

Hull acceptance probability: 0.828442

Poly length: 2374

Hull length: 32

samples: 10000

runs: 1

Hull rejection: 146 ms.

Envelope rejection: 182 ms.

samples: 100

runs: 100

Hull rejection: 170 ms.

Envelope rejection: 184 ms.

samples: 1

runs: 10000

Hull rejection: 2753 ms.

Envelope rejection: 241 ms.

Estimated cost per sample regardless of acceptance:

hull: 0.0118061 ms

env: 0.010514 ms

Polygon with 11 vertices

g++ -I../boost/ -O3 -o rejection_sampling_benchmark rejection_sampling_benchmark.cpp && ./rejection_sampling_benchmark small_polygon.wkt

Envelope acceptance probability: 0.326241

Hull acceptance probability: 0.472142

Poly length: 11

Hull length: 6

samples: 1000000

runs: 1

Hull rejection: 318 ms.

Envelope rejection: 403 ms.

samples: 10000

runs: 100

Hull rejection: 317 ms.

Envelope rejection: 403 ms.

samples: 100

runs: 10000

Hull rejection: 329 ms.

Envelope rejection: 405 ms.

samples: 1

runs: 1000000

Hull rejection: 1285 ms.

Envelope rejection: 448 ms.

Estimated cost per sample regardless of acceptance:

hull: 0.000154862 ms

env: 0.000130823 ms

big_polygon.wkt

POLYGON((13.8157247310001 48.7664301560001,13.7858557540001 48.724778951,13.7835819910001 48.7152704880001,13.7887496340001 48.7165107230001,13.7993949790001 48.7026097620001,13.8043559160001 48.6995608520001,13.8168616120001 48.6955817670001,13.8035290930001 48.687158508,13.8009452720001 48.6752212530001,13.8062162680001 48.6429234830001,13.8054927980001 48.6261286420001,13.8023922110001 48.6117109180001,13.7961910400001 48.598585104,13.7790344640001 48.573935446,13.7742802330001 48.5692070520001,13.7660120030001 48.5637551880001,13.7580538330001 48.5614814250001,13.7372799070001 48.5592593390001,13.7338692630001 48.559776103,13.725394328 48.5483814500001,13.7165059810001 48.5216905720001,13.714335571 48.5232150270001,13.6733561600001 48.5354881800001,13.6580599360001 48.551094463,13.6418335370001 48.5591043090001,13.6243669020001 48.565357158,13.5207039790001 48.5845807910001,13.4872176520001 48.581583557,13.4545581460001 48.5734445190001,13.4455664470001 48.5679151410001,13.4400887450001 48.560964661,13.4407088620001 48.557347311,13.4437060950001 48.552851461,13.4477368570001 48.534816386,13.457038615 48.5251787320001,13.4592090250001 48.516393738,13.4564184980001 48.5066527310001,13.4429826250001 48.4877133190001,13.4382283940001 48.478540752,13.4363680420001 48.4692389940001,13.4382283940001 48.4409978240001,13.4361613360001 48.4305850220001,13.4317171630001 48.423712057,13.4271696370001 48.418544413,13.4252059320001 48.41337677,13.4195215250001 48.3921635950001,13.4055688880001 48.376583151,13.3077970790001 48.3196357220001,13.2742073970001 48.307104187,13.1364380290001 48.2910586550001,13.0327751060001 48.263566793,13.0166520590001 48.2558928430001,12.9794450270001 48.232018332,12.9471989340001 48.2200035610001,12.9316960040001 48.2116319790001,12.9330395910001 48.2092548630001,12.8776424560001 48.202046001,12.8625529380001 48.196645813,12.853457886 48.189979553,12.8351644290001 48.170704244,12.822141968 48.160679017,12.782351115 48.1420238250001,12.7783203530001 48.138716533,12.7640576580001 48.123756205,12.7579598390001 48.121895854,12.7514486080001 48.1221025600001,12.7450407310001 48.1206297820001,12.7389429120001 48.113446757,12.7369792070001 48.0999592090001,12.7420434980001 48.0867817180001,12.7509318440001 48.07474111,12.7602336020001 48.064870911,12.8306169030001 48.015468242,12.8456030680001 47.9931440230001,12.8482462710001 47.98238892,12.8486003010001 47.980948385,12.8539746500001 47.9704839070001,12.8620361730001 47.962551575,12.8860140380001 47.9528880820001,12.9061678470001 47.9389096070001,12.91422937 47.935989889,12.9310758870001 47.924879456,12.9649756260001 47.87196279,12.9865763750001 47.850258688,12.9912272540001 47.8471064260001,12.926735067 47.7773949180001,12.9212573650001 47.7695401010001,12.919293661 47.7631838990001,12.9189836020001 47.756776022,12.9172266030001 47.7501614380001,12.9108187260001 47.7430300900001,12.9106120190001 47.7429267380001,12.8920085040001 47.723548076,12.9083382560001 47.7123601290001,12.9640454510001 47.7053579710001,12.979031616 47.7070891320001,13.004353068 47.714608053,13.0198559980001 47.712928569,13.0322583410001 47.7066240440001,13.0445573320001 47.696572978,13.0640910240001 47.673990377,13.072049194 47.6594692990001,13.0748397220001 47.646653545,13.0742196040001 47.6345095830001,13.072049194 47.6224172980001,13.0695687250001 47.620246887,13.057683146 47.600428976,13.0570630290001 47.5976642860001,13.0409399820001 47.583349915,13.038252807 47.5840217090001,13.0390796310001 47.5613357550001,13.0412500410001 47.5619041960001,13.040113159 47.5604572550001,13.0306046960001 47.5442566940001,13.0281242270001 47.5416470340001,13.0281242270001 47.524232077,13.0289510500001 47.5180309050001,13.0312248120001 47.5125532030001,13.0344287510001 47.5074372360001,13.0370125730001 47.501365255,13.0373226310001 47.4930453500001,13.0087972410001 47.4701010140001,13.0018725990001 47.466018576,12.991123901 47.465682679,12.9849227290001 47.4682665,12.9793416740001 47.472245586,12.969729858 47.4757337450001,12.9592912190001 47.475527039,12.9510229900001 47.4724781300001,12.9425480550001 47.470488587,12.9315926510001 47.473511658,12.8826033930001 47.4985747280001,12.836921427 47.532655335,12.8284464920001 47.5372545380001,12.8190413810001 47.5395283,12.8036418050001 47.541336975,12.7789404700001 47.554824524,12.7736694740001 47.579500021,12.7858651120001 47.602676901,12.8131502690001 47.611823629,12.7933065180001 47.6247944130001,12.7673649500001 47.6363699350001,12.7516553140001 47.649392396,12.7619906 47.6668590290001,12.744834025 47.6653604130001,12.6887134190001 47.675127259,12.6530566810001 47.675127259,12.6173999430001 47.6693394980001,12.5983830150001 47.662879944,12.5633749190001 47.6417613700001,12.5538379310001 47.6360081990001,12.5382316490001 47.631331482,12.517147664 47.6285409550001,12.4965804440001 47.6289026900001,12.482524454 47.6335794070001,12.4527588300001 47.64975413,12.4446973060001 47.656291199,12.4392196040001 47.664481914,12.428780965 47.685798442,12.4241300860001 47.691560365,12.4076969800001 47.6937307740001,12.368422892 47.683550517,12.351473023 47.681690166,12.293698771 47.6900100710001,12.271891317 47.687891337,12.2495670980001 47.6800106820001,12.2387150470001 47.6788996390001,12.2287931720001 47.6848682660001,12.22331547 47.6959011840001,12.2266227620001 47.7028775020001,12.233030639 47.7088719690001,12.2365446370001 47.716778463,12.2391284590001 47.727449646,12.2422290440001 47.7320230110001,12.2397485760001 47.7316871140001,12.225175822 47.7273721320001,12.2164941810001 47.7237031050001,12.1924129640001 47.7101638800001,12.1765999760001 47.7058230590001,12.1785636800001 47.6976581830001,12.1817676190001 47.6921288050001,12.189105672 47.6855658980001,12.1972705490001 47.6800881960001,12.2023348390001 47.6777885950001,12.2051253660001 47.6722850550001,12.2067790120001 47.6455683390001,12.205745483 47.6362149050001,12.2021281330001 47.629832866,12.1736027420001 47.605079855,12.1656445720001 47.6039688110001,11.935891154 47.610738424,11.8519686270001 47.599162903,11.8407031660001 47.5946153770001,11.8306779380001 47.5776138310001,11.8203426510001 47.5752883910001,11.7640153400001 47.583117371,11.6825732830001 47.583349915,11.6389583740001 47.5892410280001,11.6204582110001 47.58965444,11.6170475670001 47.58676056,11.5891422930001 47.5703791310001,11.5823210040001 47.559785462,11.5744661860001 47.53663442,11.569401896 47.527384339,11.5512117920001 47.5136900840001,11.5295076900001 47.5078506480001,11.48258549 47.5025796510001,11.4599512120001 47.5074372360001,11.4353532310001 47.5097109990001,11.4126156 47.506093648,11.3654866940001 47.469325867,11.3777856850001 47.4670521040001,11.3886377360001 47.462220357,11.3924617920001 47.4547789510001,11.383883504 47.4448570760001,11.3676571050001 47.4401286830001,11.3242489010001 47.439431051,11.3056453850001 47.4354002900001,11.2863184 47.4232046510001,11.2730892330001 47.4111123660001,11.2588265380001 47.4007254030001,11.2370190830001 47.39395579,11.213041219 47.395816142,11.2152116290001 47.422997945,11.1938175870001 47.428940735,11.1685994870001 47.4242640180001,11.1032804770001 47.393568218,11.0837467850001 47.3895116180001,10.9794637450001 47.3905451460001,10.9655111080001 47.3960745240001,10.9552791750001 47.4096137500001,10.9576562910001 47.409717103,10.9608602290001 47.4143163050001,10.9631339920001 47.421240947,10.9628239340001 47.4279588830001,10.9598267010001 47.432506409,10.9099072670001 47.46898997,10.8584375400001 47.485164693,10.851616252 47.4930970260001,10.8838623460001 47.508005676,10.8922339280001 47.5148786430001,10.869289591 47.5265833540001,10.8586442470001 47.530665792,10.8447949620001 47.5313117470001,10.8306356200001 47.5285728960001,10.7903280030001 47.5160672,10.7607690830001 47.513638407,10.7521907950001 47.515395406,10.7472298580001 47.5201496380001,10.7439225670001 47.525317281,10.7398918050001 47.5284695440001,10.6079101970001 47.5622659300001,10.5837256270001 47.562472636,10.5698763430001 47.555935567,10.5496191810001 47.5367894500001,10.5369067790001 47.5298648080001,10.5251245520001 47.5284695440001,10.4825431720001 47.5328620400001,10.4669368900001 47.5377196250001,10.4587720130001 47.5416470340001,10.4535010170001 47.546246236,10.4517440180001 47.554824524,10.4554647210001 47.5611807260001,10.4603223060001 47.5659866330001,10.46156254 47.5699140430001,10.4571183680001 47.5792416380001,10.4536043700001 47.58110199,10.4459562580001 47.579060771,10.4292130940001 47.5770195520001,10.4142269290001 47.5730146280001,10.4156738680001 47.564384665,10.4243555090001 47.553351746,10.430970093 47.542163798,10.4297298580001 47.532913717,10.4196012780001 47.4930453500001,10.4336572670001 47.487851868,10.4422355550001 47.4813923140001,10.447609904 47.4725814830001,10.4517440180001 47.460204977,10.4519507240001 47.4387592570001,10.4428556720001 47.41628001,10.4282829180001 47.3960486860001,10.4116431070001 47.381036683,10.403064819 47.3771092730001,10.3819808350001 47.3721224980001,10.3716455490001 47.3673941040001,10.3656510820001 47.361115418,10.3434302160001 47.3307555140001,10.325446818 47.3143224090001,10.3059131260001 47.3021784470001,10.2611613360001 47.283497416,10.2393538820001 47.2777354940001,10.1749508500001 47.272375554,10.1598755290001 47.2711209110001,10.1554313550001 47.272877909,10.1594621180001 47.2791307580001,10.1686605220001 47.290422058,10.1726912840001 47.292308248,10.1859204510001 47.2949954230001,10.1907780360001 47.298251038,10.1932585040001 47.304917298,10.1927417390001 47.3109117640001,10.1904679770001 47.3174746710001,10.2085547290001 47.3544749960001,10.2092781980001 47.3724842330001,10.1908813880001 47.379228008,10.1469564200001 47.3738019820001,10.1350708420001 47.364887797,10.1308333740001 47.362665711,10.1256657310001 47.362691549,10.1153304440001 47.3669548550001,10.1103695070001 47.3673941040001,10.0972436930001 47.3631307990001,10.0895955810001 47.359280904,10.0828776440001 47.3590741990001,10.0731624750001 47.365482076,10.0677881270001 47.375042217,10.0668579510001 47.385790914,10.0641707760001 47.396177878,10.0532153730001 47.4048595180001,10.0759530030001 47.4168742880001,10.0806038810001 47.427390442,10.0718188880001 47.4391209930001,10.0226229240001 47.4879552210001,10.0112541100001 47.4844412240001,10.0023657640001 47.4791702270001,9.99358077 47.4765864060001,9.98262536600009 47.481030579,9.98107507300008 47.4868700160001,9.98076501500009 47.489918925,9.98076501500009 47.492941997,9.97166996200014 47.5064037070001,9.95916426600013 47.5148786430001,9.94872562600008 47.524232077,9.94593509900005 47.540768534,9.93384281400006 47.534205628,9.91875329600015 47.5321902470001,9.88898767100008 47.533792216,9.8589119880001 47.541336975,9.85384769700011 47.5404068,9.84154870600008 47.5350324500001,9.83348718200008 47.534619039,9.81312666900007 47.541750387,9.80930261200012 47.5523182170001,9.81126631700005 47.5644880170001,9.80795902500006 47.5763219200001,9.79628015200007 47.584951885,9.78212080900005 47.5884142050001,9.76713464300005 47.5872773240001,9.75266524200012 47.582058004,9.73085778800009 47.5649014290001,9.71845544400011 47.546711324,9.7039860430001 47.5314151,9.6767008870001 47.5226301070001,9.61262211100006 47.5218807990001,9.5541438520001 47.5327431110001,9.54988692200004 47.5335338340001,9.54748167400007 47.534547102,9.27321130400014 47.650090027,9.23435062700008 47.6561620080001,9.19693689000013 47.6561361700001,9.18339766400007 47.6704247040001,9.12810388100013 47.6704247040001,9.01658614100012 47.6788996390001,8.99767256600009 47.6738353480001,8.98175622500005 47.6621564740001,8.94537601700009 47.6543016560001,8.90620528100004 47.6517953490001,8.88171065200009 47.6561361700001,8.8526684980001 47.6707864380001,8.85193511900007 47.6712817230001,8.83778568500014 47.6808375040001,8.83768233300012 47.6877879850001,8.85607914200011 47.6906818640001,8.8302409260001 47.707192485,8.79758142000011 47.720034079,8.77070967600011 47.7208609010001,8.76171797700007 47.701249695,8.7698828530001 47.6950743610001,8.71706954 47.6945575970001,8.71510583500012 47.7010688270001,8.71262536600005 47.708691101,8.70466719500007 47.715331523,8.70042972800013 47.7234963990001,8.70373702000012 47.7300334680001,8.71706954 47.743546855,8.71975671400008 47.747319234,8.71314213 47.757421977,8.70332360800012 47.758713887,8.69226485200011 47.757163595,8.6819295650001 47.7587397260001,8.67448815900008 47.7666978970001,8.66663334200004 47.7782734170001,8.65702152500012 47.788117778,8.64410241700011 47.791011658,8.63500736500015 47.7846037800001,8.62983972100005 47.762796326,8.61743737800009 47.7573186240001,8.6076188560001 47.7622537230001,8.60410485800014 47.774397685,8.60317468200009 47.787316793,8.60162439 47.7946031700001,8.58312422700007 47.800235901,8.55821618700008 47.8011660770001,8.54229984600008 47.7950165810001,8.55160160300008 47.7792552700001,8.53651208500008 47.774087626,8.48266524200005 47.7668529260001,8.47150313300011 47.767059632,8.46364831500009 47.7639073700001,8.4501090900001 47.750471497,8.44545821100004 47.7431851200001,8.43791345200009 47.7231863410001,8.42726810700012 47.7164684040001,8.40194665500013 47.7070891320001,8.39212813300014 47.6995185350001,8.39099125100006 47.6921288050001,8.3952287190001 47.6848165900001,8.39770918800008 47.6762899790001,8.39130131000013 47.6654637650001,8.40701094500011 47.6615621950001,8.41197188300015 47.66104543,8.43760339400012 47.6478421020001,8.45827396600012 47.639883932,8.47605065900007 47.6404006960001,8.49083011900007 47.6455683390001,8.50467940200014 47.652260437,8.51966556800011 47.657350566,8.56824141400011 47.662931621,8.5821940510001 47.6613296510001,8.59358868300009 47.65816856,8.59821374500007 47.6568854780001,8.60730879700012 47.656291199,8.60162439 47.6325975550001,8.59511315900011 47.634819641,8.59449304200004 47.6409691370001,8.5935628660001 47.6425711060001,8.58922204600012 47.6424677540001,8.58395105 47.6411241660001,8.58033369900011 47.639005432,8.57805993600007 47.6334760540001,8.57971358300011 47.6289285290001,8.58209069800009 47.625026957,8.58250411 47.6215904750001,8.58126387500005 47.614769186,8.5817806390001 47.6076636770001,8.58064375800009 47.6001705940001,8.57630536600004 47.5950230580001,8.5741325270001 47.5924449670001,8.56069665500007 47.589396057,8.55171914900004 47.5968633290001,8.54963789900006 47.598594462,8.53775231900002 47.6121336880001,8.52235274200004 47.6219005340001,8.49238041100008 47.619833476,8.46178796400008 47.606139221,8.4501090900001 47.589034323,8.44886885600008 47.5842800910001,8.42110032600004 47.5811118700001,8.41806970200011 47.5807660940001,8.35409427900004 47.5810244750001,8.31616377700001 47.587845764,8.30634525500005 47.592186585,8.29931726 47.601824239,8.29394291200009 47.611461894,8.28856856200011 47.6158027150001,8.27699304200007 47.616629537,8.25105147300013 47.6220038860001,8.23296472100012 47.6219522100001,8.17901452600006 47.6158027150001,8.17384688300007 47.613528951,8.1688859460001 47.6086455280001,8.16206465600004 47.6037621050001,8.14377119900007 47.600067241,8.12206709800009 47.5921349080001,8.11390222100007 47.587845764,8.10542728600007 47.581257019,8.10139652500007 47.5761927290001,8.09695235100014 47.5718519090001,8.08723718200011 47.5673818970001,8.04227868600009 47.5605606080001,7.91215743000015 47.5605606080001,7.90947025600011 47.5647980760001,7.9075065510001 47.574177348,7.90430261300011 47.5835566210001,7.89820479400007 47.587845764,7.83371260600012 47.590481263,7.81965661600012 47.5953388470001,7.80146651200008 47.5760893760001,7.78555017100004 47.5631961060001,7.76673994900005 47.5559614060001,7.72732044700012 47.5504226240001,7.68343754000011 47.5442566940001,7.66142338000012 47.546246236,7.64690103500007 47.551445236,7.60974694800009 47.564746399,7.61233728100009 47.5647310410001,7.63589522300009 47.5645913700001,7.64654056800009 47.5715418500001,7.65966638200004 47.5965790820001,7.6370321040001 47.5949771120001,7.58602848800012 47.5846185440001,7.59010990400014 47.594822083,7.59248702 47.5984135950001,7.5903166090001 47.6079478960001,7.58504561400008 47.6131672160001,7.57863773500011 47.616939596,7.5726432700001 47.6220038860001,7.55011234500009 47.6524413050001,7.5365731200001 47.665205384,7.52179366 47.6704247040001,7.51786625100002 47.675023906,7.51466231200004 47.685798442,7.5118717850001 47.7073216760001,7.51538578300006 47.713316142,7.53192224100013 47.7252017220001,7.53781335500014 47.731816304,7.53833011900008 47.7481460570001,7.5259277750001 47.7831568400001,7.52861494900014 47.7970319630001,7.54287764500012 47.8294330860001,7.54845869900012 47.8342389930001,7.5619979250001 47.839225769,7.5641683340001 47.8504137170001,7.55900069100008 47.8690172330001,7.55920739700014 47.873461405,7.55838057500011 47.8759935510001,7.55786381 47.878525697,7.55900069100008 47.882711488,7.5619979250001 47.887052307,7.56861250800011 47.8913672900001,7.5726432700001 47.8963023890001,7.57894779500012 47.9063276170001,7.58080814600004 47.9107976280001,7.57956791100008 47.9270498660001,7.58494226100004 47.9404082240001,7.6116073 47.9593993130001,7.62111576300006 47.971439922,7.61894535300007 48.002652487,7.57574385600014 48.0537088020001,7.5726432700001 48.0949724330001,7.57894779500012 48.114480286,7.58566573000013 48.1297248330001,7.59290043100009 48.1386648560001,7.59972172 48.144710999,7.60478601 48.1525658160001,7.60674971500015 48.1669835410001,7.61336429800008 48.1792050180001,7.67661625200014 48.2384003710001,7.68715824300011 48.252921448,7.69346276900012 48.269871318,7.69552982500008 48.2901801560001,7.70245446700008 48.311186625,7.71857751500005 48.319997457,7.73697432500006 48.3266637170001,7.75072025500009 48.3413656620001,7.75196049 48.355344137,7.74689619900005 48.3686766570001,7.74038496900008 48.381440736,7.7371810300001 48.393481344,7.7383179120001 48.4066071580001,7.74565596500011 48.4330138140001,7.75072025500009 48.444408468,7.75764489700015 48.453891093,7.76415612800014 48.4603506480001,7.76922041900011 48.470065817,7.77128747500007 48.4891085820001,7.77645511900008 48.4981777960001,7.78844405100003 48.5063426720001,7.81345544400003 48.519468486,7.81345544400003 48.526341451,7.80167321700011 48.5475804650001,7.80177657100006 48.582358704,7.81025150600007 48.6150182090001,7.85241947500012 48.6586847940001,7.86409834800008 48.664162497,7.88063480600007 48.66772817,7.89593103 48.676513163,7.92331953900009 48.698217265,7.9352051190001 48.703333232,7.9484342850001 48.711859844,7.95918298300012 48.721368307,7.96362715700013 48.729274801,7.96486739100007 48.748343405,7.97013838700011 48.7572834270001,7.9815072020001 48.7597638960001,8.00961918100012 48.760073954,8.01726729300012 48.7618309540001,8.02295170100007 48.7650865690001,8.02512211100014 48.7706159470001,8.02729252100005 48.780021058,8.0319434 48.7853437300001,8.03659427900007 48.7882892870001,8.03876468900006 48.7907697560001,8.04754968200012 48.791028137,8.0842399500001 48.8040505980001,8.09033776900014 48.8075129200001,8.10274011200005 48.8213105260001,8.14811202 48.9037344360001,8.17932458500013 48.9426984670001,8.1998915450001 48.958250331,8.20030521600003 48.958563131,8.18872969500009 48.965746155,8.09044112100008 48.9791820280001,7.93189782700011 49.0348375460001,7.9138110750001 49.0361811330001,7.85686364700013 49.0322537230001,7.77366459100011 49.048118388,7.7626058350001 49.046154683,7.73914473500014 49.0377314250001,7.72694909600011 49.0356643680001,7.71733728100011 49.0365945440001,7.69614994300005 49.041555481,7.68509118700007 49.042795716,7.67248213700012 49.0410387170001,7.66080326400007 49.0377314250001,7.6488143310001 49.0357160450001,7.64493884 49.0362944760001,7.63496504700004 49.0377831010001,7.6256632890001 49.043002421,7.61594812 49.055973206,7.60861006600007 49.0619676720001,7.58638920100012 49.0695641070001,7.54267093900006 49.0745767220001,7.52086348500012 49.0836717740001,7.50773767100006 49.0945755010001,7.48510339400011 49.1187083950001,7.4710474040001 49.1283202120001,7.47280440300008 49.1316275030001,7.47528487100004 49.1339012660001,7.48272627800006 49.137053528,7.47611169400008 49.1515229290001,7.45802494200007 49.1558637500001,7.41482344600013 49.1577757780001,7.41048262500004 49.1689378870001,7.39105228700015 49.1700230920001,7.37163380900009 49.1661736140001,7.36759118600008 49.1653722130001,7.35095137600007 49.1591710420001,7.34630049600011 49.1542101040001,7.33906579600003 49.1396890260001,7.33400150600005 49.1341596480001,7.3264567460001 49.131834208,7.30599287900014 49.1301288870001,7.29710453300004 49.128113505,7.2908000080001 49.1231008920001,7.28025801600006 49.108993226,7.27436690200005 49.1050141400001,7.26806237800014 49.1056342570001,7.24119063300014 49.1139024860001,7.15499434400002 49.1144192510001,7.13928470800005 49.1179332480001,7.1235750730001 49.123307597,7.08533451300011 49.1415493780001,7.07985681200012 49.142014465,7.07076175900005 49.1361233530001,7.07158858200006 49.1305939740001,7.07479252100012 49.1253746550001,7.07324222800011 49.120310364,7.04254642700008 49.107597962,7.02053226700008 49.118966777,7.00895674600014 49.1464069630001,7.00947351 49.1817019650001,6.98787276200011 49.1824254360001,6.92544763200004 49.2055764770001,6.91438887600015 49.2066616830001,6.88524336700004 49.2048013310001,6.84348881 49.2110541800001,6.83346358300005 49.20945221,6.82767582200009 49.19555125,6.83522058100004 49.179376526,6.83904463700009 49.1627883920001,6.8217847090001 49.1477505500001,6.80907230600013 49.145838522,6.77010827600014 49.155295309,6.72556319200004 49.1555536910001,6.71378096500013 49.1588609820001,6.70096521 49.1728652960001,6.70375573700011 49.18511261,6.70882002700009 49.1977733360001,6.70251550300009 49.2136380010001,6.69848474100007 49.213586324,6.68504886800014 49.2077985640001,6.68060469600005 49.2074885050001,6.6779175210001 49.2110541800001,6.67595381700008 49.2189089970001,6.67481693500014 49.221131084,6.67161299600008 49.225316875,6.66375817900004 49.2438687130001,6.65952071100008 49.2467625940001,6.64567142700014 49.250018209,6.64029707800009 49.2527570600001,6.63916019600015 49.256787822,6.64122725400011 49.266916403,6.63967696100011 49.27115387,6.57316939300003 49.3131151330001,6.55642622800008 49.3263959760001,6.55012170400008 49.3380231730001,6.55559940600006 49.347169902,6.5733760980001 49.3477383430001,6.57771691900007 49.3557998660001,6.57430627400004 49.361794332,6.52573042800014 49.3954873660001,6.51880578600006 49.4021536260001,6.5207694910001 49.4025670380001,6.52056278500004 49.408148092,6.51787561000012 49.4164163210001,6.51167443800011 49.424736226,6.49451786300006 49.435536601,6.40274051900013 49.4654572550001,6.39168176300012 49.46669749,6.38351688600011 49.464630432,6.36449995900006 49.456103821,6.35385461400006 49.4547602340001,6.34530707100009 49.4553486520001,6.34537967900013 49.462718404,6.34227909400011 49.4930007940001,6.34880855 49.5252897550001,6.3507540280001 49.534910381,6.3507540280001 49.566588034,6.35643843500014 49.577595113,6.37152795400004 49.59299469,6.39757287600011 49.6138719690001,6.40770145700009 49.6274111940001,6.41524621600013 49.6346458940001,6.41793339000014 49.6391417450001,6.41700321500011 49.6457563270001,6.41090539600015 49.64963206,6.40449751800011 49.652474264,6.40274051900013 49.655781555,6.41824344900004 49.669889222,6.49172733600011 49.700791728,6.48976363100007 49.702962138,6.48294234200011 49.7080781050001,6.48635298600004 49.71293569,6.49100386500001 49.714434306,6.49968550600008 49.712212219,6.49255415800013 49.7184133910001,6.48779992600012 49.7255964160001,6.48552616300012 49.7337612920001,6.48624963400002 49.742701315,6.49596480300005 49.748230693,6.49637821400006 49.7521064250001,6.49369104 49.7565505980001,6.49379439200007 49.763630269,6.49854862400005 49.7853860480001,6.49999556400005 49.7860578410001,6.50009891800008 49.7944811,6.50226932700008 49.7958763630001,6.50257938700014 49.7956696580001,6.4972050370001 49.799442038,6.49327762900012 49.7995970660001,6.46247847500007 49.8054881800001,6.41452274600005 49.8054881800001,6.3970561110001 49.8085887660001,6.38010624200007 49.8155650840001,6.35137414500008 49.8332901,6.33442427500006 49.8402147420001,6.32563928200008 49.840369772,6.31065311600011 49.8344786590001,6.30259159400012 49.8349437470001,6.30155806500005 49.8383027140001,6.29556789200009 49.8486156920001,6.29153283700012 49.8555626430001,6.28677860500011 49.8610403450001,6.27220585200007 49.867138164,6.23830611100004 49.8769050090001,6.22269982900011 49.887136943,6.18983361800008 49.938296611,6.17267704300011 49.956228333,6.16192834500009 49.9424824020001,6.15397017400005 49.9512157190001,6.1387773030001 49.9793276980001,6.12151737500011 49.996277568,6.11717655400014 50.0043907680001,6.11996708100008 50.0155012,6.11376591 50.03637848,6.10725467900005 50.044595032,6.0964026290001 50.0486257940001,6.10570438600013 50.0603046680001,6.10942509 50.0635602830001,6.10715132700011 50.063766988,6.10115686100008 50.063405254,6.09939986100011 50.0641287230001,6.10570438600013 50.0922407020001,6.11056197100004 50.105986634,6.11748661300004 50.1204560350001,6.12658166500009 50.127329,6.12947554500008 50.134046937,6.12596154700012 50.140196432,6.11583296700007 50.145467428,6.11800337700015 50.1503766890001,6.12131066800015 50.1615904750001,6.12317102 50.164897767,6.13174930800011 50.168308411,6.15169641100002 50.169341939,6.15913781700004 50.1724425260001,6.16513228400007 50.1818993120001,6.16575240000014 50.1931647750001,6.16017134600011 50.20453359,6.1468388270001 50.2140420540001,6.15717411300011 50.222723694,6.17980839 50.233007304,6.18962691200002 50.2427224730001,6.21040083800008 50.249026998,6.25339563 50.2567784630001,6.27179243900014 50.2674238080001,6.26734826700005 50.2764155070001,6.26941532400011 50.2864924120001,6.27602990700009 50.2961042280001,6.2859517820001 50.3038556920001,6.29949100700009 50.3088683070001,6.31065311600011 50.3082481900001,6.3220219320001 50.305405986,6.33545780400004 50.3038556920001,6.36201949 50.3069562790001,6.37452518700007 50.315482891,6.37339968400011 50.3230800350001,6.3724581300001 50.329435527,6.33773156700008 50.368089498,6.3363879800001 50.379923402,6.34331262200007 50.3933075970001,6.35044396900011 50.4168720510001,6.35116744 50.433563538,6.34734338400008 50.4369741830001,6.34021203600014 50.4378526820001,6.33163374800012 50.446896057,6.32615604600011 50.4570246380001,6.32326216600012 50.466016337,6.3257426350001 50.4740261840001,6.33690474400004 50.4810025020001,6.31871464000011 50.4816742960001,6.27540979000014 50.488030497,6.26011356600009 50.4926813760001,6.25783980300005 50.4940766400001,6.25556604000013 50.4945934040001,6.25308557100007 50.4940766400001,6.25091516100008 50.4926813760001,6.21711877400008 50.4860151170001,6.2071969 50.4863251750001,6.19923872900003 50.4904076130001,6.19066044100009 50.5018281050001,6.18259891700012 50.5065823370001,6.19055708800008 50.5152123010001,6.17887821400009 50.515780742,6.17081669100011 50.517951152,6.16947310300014 50.522498678,6.17732792200007 50.5301984660001,6.16068811 50.543582663,6.17908492000015 50.5619794720001,6.21060754300004 50.578670959,6.2329317630001 50.587145894,6.2329317630001 50.590763245,6.24430057700008 50.599548239,6.25132857200009 50.608436585,6.24905480900009 50.6144310510001,6.18001509600012 50.615516256,6.15944787600012 50.622389222,6.14776900200005 50.63675527,6.16110152100006 50.642181296,6.10022668500005 50.7012991340001,6.08100305200011 50.7134947720001,6.06436324 50.7144766240001,6.02477909300012 50.7075519820001,6.01154992600004 50.7085338350001,6.00762251800006 50.7169054170001,6.01134322100009 50.7274474080001,6.01082645700004 50.7370592250001,5.99418664500013 50.7425886030001,5.99273970500013 50.7444489550001,5.99263635300011 50.7462576300001,5.99325646900007 50.7480663050001,5.99491011600011 50.7499266560001,5.99708052500011 50.762949117,5.99056929500006 50.7690469360001,5.98064742000014 50.7734394330001,5.97299930800006 50.781811015,5.96876184100012 50.79462677,5.98395471200013 50.7921979780001,5.99832076 50.8007245890001,6.00359175600008 50.812610169,6.00142134600009 50.821808574,6.00049117000012 50.8304385380001,6.00927616400011 50.8404637650001,6.02302209500007 50.845424704,6.04555301900007 50.8441844690001,6.05671512900011 50.8526594040001,6.06281294800007 50.8629430140001,6.06312300600007 50.8709011840001,6.05464807100014 50.891468404,6.05650842300014 50.898082988,6.06177941900009 50.9035090130001,6.06374312400004 50.907539775,6.03108361800014 50.914722799,6.00751916500013 50.9240762330001,5.99987105300008 50.929398906,5.99728723200008 50.9373570760001,5.99584029100006 50.951774801,5.9996643480001 50.9600947060001,6.00576216700006 50.9685179650001,6.00369510900009 50.973737284,5.96783166500006 50.970998434,5.94158003700002 50.976476135,5.92773075400007 50.9776646940001,5.91419152900008 50.9752359010001,5.88824995900004 50.9671227010001,5.87460738100012 50.965365703,5.87357385200005 50.9905838010001,5.85817427500007 51.0193417360001,5.85248986800011 51.04275116,5.88049849500004 51.0520529180001,5.89434777800008 51.047143657,5.90623335800012 51.0374026490001,5.91956587700014 51.02970286,5.93796268700004 51.030943095,5.95026167800009 51.039469707,5.96948531100011 51.0649203500001,5.98292118300014 51.0746871950001,6.07542199700009 51.120369161,6.13236942600008 51.139825338,6.14725223800011 51.15225352,6.12627160700012 51.1645783490001,6.14911258900011 51.176334737,6.15707076 51.1792544560001,6.13412642400004 51.1842153940001,6.0843103440001 51.162692159,6.06084924300012 51.1709087120001,6.05371789500009 51.1893830370001,6.0566117760001 51.211707255,6.0651900630001 51.2316285200001,6.07542199700009 51.2426614390001,6.09650598100012 51.258810324,6.14776900200005 51.3181607060001,6.15820764100008 51.3245944220001,6.1836324460001 51.335704854,6.19355432100008 51.344515686,6.19892867 51.3569697060001,6.20202925600009 51.3788805130001,6.20781701600015 51.3876655080001,6.19272749900006 51.398956808,6.19407108600012 51.417379456,6.2017191970001 51.438644308,6.2053365480001 51.4584363820001,6.20047896300008 51.476574809,6.19334761500005 51.5093376670001,6.15303999800008 51.538431499,6.08648075400009 51.595533956,6.08213993300012 51.6078071090001,6.08751428200009 51.622095642,6.09919315600007 51.644471538,6.03149703 51.6629975390001,6.00855269400012 51.681187643,6.02198856600009 51.709506328,6.01206669100009 51.715862528,5.9897424720001 51.7263786820001,5.97827030400009 51.729789327,5.9492281500001 51.729375916,5.9393062740001 51.7318822230001,5.94013309700003 51.7426309210001,5.94605640000012 51.746288216,5.96235396300008 51.7563510130001,5.96411096200006 51.776556499,5.95077844200011 51.7959093220001,5.92804081200006 51.8067355350001,5.93145145700007 51.8156497200001,5.9480912680001 51.8229619350001,5.98891565 51.8274577840001,6.00824263500004 51.8325737510001,6.02891320800006 51.842108053,6.04327925600006 51.846862285,6.08400028400013 51.8536577350001,6.11645308400006 51.848283387,6.14001753700006 51.8445368450001,6.15614058400013 51.8420563760001,6.14270471200007 51.8551821900001,6.10539432700006 51.8794701130001,6.09299198400015 51.8853095500001,6.1269950760001 51.8967300410001,6.15924117 51.8872990930001,6.19138391100009 51.8711502080001,6.22518029800008 51.8625460820001,6.25639286200007 51.866809387,6.26466109200001 51.8661892710001,6.27179243900014 51.8619001270001,6.28285119600014 51.8496011350001,6.28739872200009 51.846164653,6.3257426350001 51.842547303,6.34196903400002 51.8366820280001,6.34496626800012 51.8211015830001,6.38248335800012 51.8275869750001,6.38661747200004 51.8375605270001,6.37845259600005 51.860117289,6.44253137200013 51.848360901,6.46289188700007 51.848360901,6.47942834400007 51.8530117800001,6.52862430800013 51.8764212040001,6.62815311700007 51.8975051890001,6.71667484600005 51.899262187,6.74375329600008 51.908331401,6.7670076900001 51.925513815,6.78984867300011 51.9511453250001,6.79801355000012 51.9567005420001,6.8056616610001 51.957527365,6.81072595200007 51.960576274,6.81165612700005 51.972797751,6.80917565900006 51.9795415250001,6.80400801600007 51.984373271,6.7781698 52.0012714650001,6.7128507890001 52.0238540650001,6.69093998200012 52.027858988,6.67502364100011 52.034809469,6.67295658300014 52.050054016,6.67988122500012 52.0604668180001,6.68887292500008 52.0631023160001,6.69941491700013 52.0635674040001,6.71140384900011 52.0672881070001,6.71946537300008 52.073566793,6.7276302490001 52.0863050330001,6.73290124500005 52.091989441,6.74985111500013 52.1028673300001,6.7658708080001 52.108396709,6.77157568400014 52.108792502,6.83067305500009 52.112892558,6.84328210500013 52.119998067,6.86539961700004 52.1477999880001,6.88482995600012 52.1603315230001,6.92772139500008 52.171907044,6.94766849700008 52.182810771,6.97112959800006 52.2062718710001,6.98187829600008 52.2139974980001,7.02632002700005 52.2306373090001,7.02911055500002 52.2357791140001,7.02660015200007 52.238622687,7.02073897300005 52.2452617390001,7.01185062600013 52.2666299440001,7.0124707440001 52.2849492390001,7.01970544400007 52.300038758,7.0397559 52.328615825,7.04823083500011 52.365073547,7.03417484500008 52.3907825730001,6.97330000800014 52.4513731900001,6.96699548300003 52.4495645150001,6.96079431100014 52.442846578,6.95149255300004 52.437472229,6.92648116100014 52.4329763800001,6.9002295330001 52.431917013,6.87201420000014 52.434733378,6.8203377690001 52.446825663,6.74116947400009 52.4536727910001,6.71481449400011 52.461553447,6.69507409700014 52.475609437,6.6889762780001 52.490518087,6.68752933700011 52.508139751,6.68401534000014 52.5259939580001,6.67171634900012 52.5416777550001,6.68825280700011 52.5425820930001,6.74375329600008 52.5597128300001,6.7109904380001 52.576636862,6.70396244300008 52.583070577,6.70365238400009 52.591390483,6.70819991100012 52.5996845500001,6.71016361500006 52.608650412,6.70179203200007 52.619114889,6.71908314900008 52.6267589820001,6.73703536 52.6346953330001,6.77052168700007 52.641025696,6.86539961700004 52.6419558720001,6.91841963700006 52.632189026,6.96771895300014 52.636659038,6.98280847100006 52.6327833050001,7.01846521 52.6259878540001,7.03665531400006 52.647381897,7.04399336700007 52.682625224,7.05329512500009 52.790577291,7.06197676600004 52.8240119420001,7.07215075900012 52.8413165520001,7.07985681200012 52.854423523,7.1619189860001 52.9326358040001,7.1836230880001 52.966122131,7.19282149300011 52.9980064900001,7.19437178600012 53.033844096,7.18507002700008 53.1054417930001,7.18134932400008 53.1141751110001,7.17649174 53.1193944300001,7.17266768400012 53.1257506310001,7.17194421400012 53.1377137250001,7.17442468200011 53.145775249,7.18858402500004 53.167789408,7.19540531400011 53.1849976610001,7.1985059 53.200578105,7.19747237100006 53.2166236370001,7.19459069100009 53.2450218770001,7.20443769600007 53.248277085,7.21583092500009 53.255601304,7.22461998800009 53.262925523,7.23357181100005 53.27362702,7.23698978 53.2855492210001,7.2295028 53.296576239,7.25473066500007 53.319525458,7.26832116 53.3236758480001,7.29151451900009 53.323919989,7.31316165500004 53.32050202,7.34766686300009 53.307359117,7.36654707100007 53.3028018250001,7.34253991 53.3240420590001,7.30290774800005 53.332749742,7.07520592500009 53.337591864,7.03825931100005 53.348578192,7.02361087300005 53.3764102230001,7.02328535200007 53.4505069030001,7.02767988400007 53.4673526060001,7.04704837300005 53.4977074240001,7.05144290500004 53.5126000020001,7.05974368600005 53.521714585,7.07935631600009 53.5215518250001,7.11963951900009 53.516302802,7.12501061300009 53.524359442,7.13453209700009 53.5274112,7.14177493600005 53.5371768250001,7.13998457100007 53.549790757,7.13111412900008 53.5569522160001,7.10189863400007 53.5657412780001,7.0888778 53.573716539,7.08676191500007 53.586859442,7.10092207100007 53.59788646,7.13314863400007 53.611273505,7.16944420700008 53.635484117,7.18897545700008 53.643500067,7.22608483200008 53.666489976,7.30502363400007 53.684800523,7.45883222700007 53.6951358090001,7.46957441500007 53.6907412780001,7.48023522200009 53.6820335960001,7.50391686300009 53.678656317,7.6513778 53.696966864,7.95142662900008 53.721909898,8.03142337300005 53.7080752620001,8.03142337300005 53.7006289730001,8.02491295700008 53.672552802,8.05290774800005 53.6362979190001,8.09408613400007 53.604722398,8.12761478 53.590765692,8.12761478 53.5846214860001,8.11915123800009 53.5719261740001,8.13461347700007 53.5674502620001,8.15674889400009 53.563666083,8.16797936300009 53.553208726,8.16488691500007 53.5352237,8.15544681100005 53.5260277360001,8.13379967500009 53.516302802,8.11573326900009 53.510728257,8.07634524800005 53.5086123720001,8.05876712300005 53.5020205750001,8.07699629 53.46869538,8.08619225400008 53.4561221370001,8.09978274800005 53.4474144550001,8.11247806100005 53.4510765650001,8.12387129 53.4540062520001,8.14063561300009 53.453599351,8.15235436300009 53.4497744810001,8.17139733200008 53.4365908870001,8.17855879 53.4337425800001,8.18669681100005 53.4295108090001,8.19483483200008 53.420111395,8.20533287900008 53.4107119810001,8.21973717500009 53.40643952,8.23650149800005 53.406724351,8.24870853 53.408392645,8.25945071700005 53.412298895,8.27173912900008 53.4195010440001,8.29281660200007 53.4404971370001,8.31511478 53.4749209660001,8.32048587300005 53.5092227230001,8.29151451900009 53.5293643250001,8.25220787900008 53.5230980490001,8.23121178500008 53.5252139340001,8.23316491 53.5398623720001,8.24170983200008 53.5563011740001,8.24887129 53.590277411,8.25733483200008 53.604437567,8.27068118600005 53.6128604190001,8.28760826900009 53.616888739,8.32935631600009 53.618109442,8.34848066500007 53.6128604190001,8.36329186300009 53.600572007,8.37549889400009 53.586900132,8.38770592500009 53.577134507,8.42807050900007 53.5647647160001,8.51343834700009 53.5547549500001,8.55209394600007 53.5436058610001,8.55209394600007 53.5362002620001,8.52816816500007 53.523911851,8.50619550900007 53.5079613300001,8.49000084700009 53.4863955750001,8.48389733200008 53.4573428410001,8.48503665500004 53.4011904970001,8.49089603 53.376450914,8.50440514400009 53.3580589860001,8.50733483200008 53.38279857,8.49675540500004 53.44525788,8.49756920700008 53.4747582050001,8.51286868600005 53.4964867210001,8.53581790500004 53.5061709660001,8.55665123800009 53.5182152360001,8.56576582100007 53.5466983090001,8.56080162900008 53.551703192,8.53516686300009 53.590765692,8.52751712300005 53.596625067,8.51710045700008 53.6101748720001,8.50831139400009 53.6251488300001,8.50123131600009 53.6441917990001,8.48707116 53.666937567,8.48389733200008 53.68357982,8.48609459700009 53.700425523,8.49219811300009 53.7151553410001,8.52963300900007 53.770697333,8.55616295700008 53.8309593770001,8.5732528 53.857652085,8.58757571700005 53.8704287780001,8.60710696700005 53.881537177,8.62924238400007 53.889390367,8.65186608200008 53.8924828150001,8.67269941500007 53.891587632,8.68458092500009 53.8884951840001,8.70915774800005 53.8719750020001,8.74463951900009 53.8541527360001,8.78248131600009 53.842474677,8.86068769600007 53.831000067,8.90357506600009 53.831732489,8.97624759200005 53.8424339860001,9.01628665500004 53.840521552,9.03500410200007 53.8535830750001,9.11451256600009 53.8651390650001,9.19361412900008 53.8646914730001,9.21070397200009 53.8719750020001,9.22429446700005 53.865912177,9.24073326900009 53.8641625020001,9.27466881600009 53.8651390650001,9.28337649800005 53.8616397160001,9.30534915500004 53.8445498720001,9.40267988400007 53.74241771,9.44288170700008 53.7143008480001,9.47095787900008 53.7006289730001,9.48471113400007 53.6900902360001,9.49838300900007 53.659857489,9.56706790500004 53.599595445,9.58236738400007 53.591294664,9.60092207100007 53.5863304710001,9.62476647200009 53.5846214860001,9.63721764400009 53.581000067,9.69662519600007 53.556626695,9.76400800900007 53.5476748720001,9.81902103 53.5403506530001,9.83204186300009 53.5436058610001,9.81959069100009 53.556626695,9.78207441500007 53.5697289080001,9.69239342500009 53.575913804,9.65577233200008 53.5846214860001,9.58366946700005 53.6124535180001,9.55079186300009 53.6345889340001,9.53907311300009 53.666489976,9.53614342500009 53.6937523460001,9.53223717500009 53.71116771,9.52222741 53.7166201840001,9.47527103 53.732163804,9.46021569100009 53.7354190120001,9.43580162900008 53.7486839860001,9.41244550900007 53.7787539730001,9.39665774800005 53.811021226,9.39519290500004 53.831000067,9.35873457100007 53.839544989,9.29558353 53.8718936220001,9.25782311300009 53.8855654970001,9.22046959700009 53.8907738300001,9.09343509200005 53.8924828150001,9.05543053500008 53.9028994810001,9.02995853 53.9071312520001,9.01832116 53.9027367210001,9.00782311300009 53.8924828150001,8.98462975400008 53.8970401060001,8.94947350400008 53.9129092470001,8.91602623800009 53.9374046900001,8.83334394600007 54.0364444030001,8.87183678500008 54.0469424500001,8.89063561300009 54.047796942,8.91456139400009 54.043890692,8.95386803500008 54.028306382,8.97535241 54.0240746110001,8.99724368600005 54.030218817,9.00489342500009 54.0411644550001,9.01303144600007 54.060980536,9.0185653 54.0824242210001,9.01832116 54.09788646,9.00668379 54.108140367,8.98812910200007 54.117865302,8.97445722700007 54.1280785180001,8.97730553500008 54.1394717470001,8.97730553500008 54.145697333,8.95289147200009 54.150091864,8.91797936300009 54.1463076840001,8.88542728 54.1370303410001,8.86744225400008 54.12518952,8.86068769600007 54.12518952,8.83334394600007 54.1531436220001,8.81568444100009 54.1756045590001,8.81283613400007 54.1804873720001,8.82097415500004 54.2005069030001,8.83627363400007 54.217759507,8.8466903 54.2335472680001,8.83961022200009 54.248724677,8.83961022200009 54.255560614,8.85189863400007 54.2610537780001,8.89421634200005 54.2682152360001,8.91146894600007 54.2691917990001,8.92204837300005 54.2742373720001,8.93751061300009 54.2866885440001,8.95313561300009 54.3025576840001,8.96314537900008 54.317613023,8.94027754 54.3150088560001,8.90259850400008 54.295843817,8.88111412900008 54.290269273,8.88306725400008 54.2936058610001,8.88591556100005 54.30072663,8.88795006600009 54.303941148,8.85759524800005 54.3018252620001,8.80543053500008 54.2924258480001,8.77466881600009 54.290269273,8.73894290500004 54.293890692,8.72348066500007 54.290269273,8.69019616 54.271470445,8.67847741 54.2691917990001,8.65186608200008 54.2748477230001,8.62338300900007 54.2901065120001,8.60271243600005 54.3120791690001,8.59986412900008 54.338080145,8.61402428500008 54.348374742,8.64136803500008 54.35565827,8.67204837300005 54.3592796900001,8.69556725400008 54.358587958,8.69556725400008 54.365423895,8.67758222700007 54.367905992,8.66382897200009 54.3755557310001,8.65064537900008 54.3779971370001,8.63477623800009 54.365423895,8.62623131600009 54.3764102230001,8.62916100400008 54.387681382,8.63843834700009 54.398138739,8.64844811300009 54.4063988300001,8.66976972700007 54.400824286,8.75082441500007 54.413804429,8.86068769600007 54.413804429,8.88607832100007 54.4177920590001,8.90723717500009 54.425523179,8.94947350400008 54.4473330750001,8.98804772200009 54.4584414730001,9.00473066500007 54.4658877620001,9.01148522200009 54.482123114,9.01156660200007 54.506333726,8.98609459700009 54.529282945,8.90447024800005 54.5806338560001,8.89283287900008 54.5912539730001,8.88795006600009 54.6018740910001,8.87875410200007 54.6065127620001,8.85816491 54.606146552,8.83708743600005 54.6026878930001,8.82585696700005 54.598130601,8.81902103 54.6056175800001,8.85328209700009 54.6192894550001,8.81836998800009 54.6736514340001,8.80543053500008 54.6875674500001,8.77670332100007 54.697984117,8.72266686300009 54.725531317,8.68873131600009 54.735296942,8.68873131600009 54.74217357,8.69434655 54.760239976,8.68132571700005 54.7805850280001,8.66187584700009 54.8006045590001,8.64844811300009 54.817857164,8.64275149800005 54.844183661,8.64722741 54.86737702,8.66077593400007 54.8963111560001,8.69588220200009 54.889984029,8.7327791750001 54.889053854,8.80088871200013 54.903833314,8.82424645900008 54.9059003700001,8.90413822400006 54.8979422,8.98268640100011 54.8793386840001,9.19476648 54.850399882,9.2115096440001 54.8418215940001,9.21605716900012 54.83174469,9.21905440300014 54.817792054,9.22639245600004 54.805906474,9.24406579600014 54.8017723600001,9.31703291800005 54.80161733,9.33201908400014 54.8032193,9.34173425300008 54.8090587360001,9.35599694800004 54.8113324990001,9.36695235200011 54.817016907,9.38503910300005 54.8193940230001,9.40519291100011 54.8083869430001,9.42214278100002 54.8072500610001,9.43692224100005 54.8101439420001,9.43750302705396 54.8104111273827,9.45142662900008 54.8103701840001,9.51099694100009 54.827826239,9.52995853 54.841498114,9.55437259200005 54.8471133480001,9.56690514400009 54.8601748720001,9.57992597700007 54.8662783870001,9.58318118600005 54.830267645,9.63160241 54.8198916690001,9.69304446700005 54.8180199240001,9.73462975400008 54.807318427,9.75212649800005 54.7996279970001,9.77808678500008 54.79315827,9.80176842500009 54.783392645,9.81218509200005 54.766058661,9.82374108200008 54.7567406270001,9.84986412900008 54.7593447940001,9.89535566500007 54.76947663,9.89144941500007 54.790269273,9.91504967500009 54.791205145,9.94752037900008 54.779527085,9.97046959700009 54.762640692,9.98414147200009 54.728501695,9.99048912900008 54.7205264340001,9.99952233200008 54.7129580750001,10.01823978 54.7012393250001,10.0053817070001 54.69550202,9.99219811300009 54.696478583,9.97982832100007 54.6997744810001,9.97046959700009 54.7012393250001,9.97103925900007 54.6990420590001,9.94629967500009 54.6876488300001,9.94312584700009 54.6875674500001,9.93669681100005 54.6850039730001,9.93238366 54.685248114,9.92994225400008 54.683091539,9.92945397200009 54.6738955750001,9.94410241 54.673325914,9.97022545700008 54.677923895,9.99634850400008 54.6787783870001,10.011403842 54.6670596370001,10.02214603 54.6724307310001,10.0335392590001 54.6729190120001,10.0390731130001 54.6668154970001,10.031911655 54.652777411,10.0369572270001 54.638902085,10.0376082690001 54.619086005,10.031911655 54.5777041690001,10.0268660820001 54.5599632830001,10.0200301440001 54.545843817,10.01042728 54.5343285180001,9.99781334700009 54.52366771,9.96558678500008 54.5061709660001,9.92530358200008 54.493109442,9.88200931100005 54.484849351,9.84009850400008 54.482123114,9.84009850400008 54.475287177,9.88331139400009 54.462103583,10.124685092 54.4957542990001,10.1434025400001 54.4918480490001,10.2038680350001 54.4610049500001,10.1839298840001 54.4493675800001,10.1838485040001 54.438421942,10.1917423840001 54.4261742210001,10.1970320970001 54.41010163,10.1912541020001 54.396714585,10.1770939460001 54.384263414,10.1590275400001 54.3753115910001,10.141774936 54.372259833,10.1443791020001 54.3700218770001,10.1477970710001 54.3683128930001,10.1482853520001 54.365179755,10.141774936 54.358587958,10.1525171230001 54.35179271,10.1555281910001 54.3434105490001,10.1516219410001 54.333970445,10.141774936 54.32440827,10.163747592 54.3291690120001,10.180349155 54.3411319030001,10.2038680350001 54.372259833,10.2171330090001 54.4054222680001,10.2243758470001 54.413804429,10.2343856130001 54.417710679,10.27214603 54.4200707050001,10.285817905 54.424750067,10.2924910820001 54.430161851,10.2976180350001 54.435736395,10.3068953790001 54.441107489,10.3183699880001 54.443304755,10.3608504570001 54.441107489,10.3828231130001 54.434759833,10.4433699880001 54.4063988300001,10.6010848320001 54.365423895,10.6901961600001 54.3162295590001,10.7312931650001 54.3102074240001,10.7771102220001 54.315130927,10.8108016290001 54.327378648,10.8679305350001 54.358587958,10.9008895190001 54.37103913,10.9353133470001 54.3795433610001,11.0188094410001 54.3858910180001,11.0188094410001 54.37909577,11.0008244150001 54.3785667990001,10.9758406910001 54.378404039,10.9931746750001 54.3738467470001,11.0105086600001 54.377183335,11.0339461600001 54.367621161,11.10417728 54.3928897160001,11.1355086600001 54.3858910180001,11.0983992850001 54.361517645,11.0877384770001 54.35175202,11.0817977220001 54.3546410180001,11.0665796230001 54.358587958,11.0774031910001 54.342230536,11.086599155 54.302435614,11.0944930350001 54.2835147160001,11.087087436 54.2709007830001,11.0877384770001 54.25389232,11.0944930350001 54.225083726,11.0901798840001 54.207993882,11.0805770190001 54.1988792990001,11.070974155 54.192572333,11.0665796230001 54.1839053410001,10.9504500660001 54.1394717470001,10.9103296230001 54.1091983090001,10.8928328790001 54.102525132,10.8523869150001 54.0943057310001,10.8445744150001 54.094468492,10.8361108730001 54.0899925800001,10.8293563160001 54.0928408870001,10.8222762380001 54.097357489,10.8133244150001 54.09788646,10.8054305350001 54.0948753930001,10.801442905 54.092230536,10.762868686 54.056830145,10.75261478 54.0501162780001,10.75261478 54.043890692,10.7658797540001 54.024359442,10.780446811 54.009955145,10.7996525400001 54.0005557310001,10.8269149100001 53.9954287780001,10.8655705090001 53.997788804,10.8754988940001 53.9954287780001,10.8825789720001 53.985052802,10.8835555350001 53.973130601,10.887380405 53.9639346370001,10.9021102220001 53.961371161,10.9060164720001 53.9612084010001,10.917653842 53.9607608090001,10.9226180350001 53.961371161,10.9353947270001 53.967271226,10.9646916020001 53.9854190120001,10.9812117850001 53.989243882,11.0002547540001 53.9916039080001,11.0534774100001 54.008490302,11.1750594410001 54.018011786,11.1838485040001 54.0160179710001,11.1907658210001 54.0103213560001,11.1972762380001 53.9962425800001,11.2043563160001 53.989243882,11.239919467 53.9834658870001,11.2453719410001 53.9784203150001,11.2407332690001 53.9556338560001,11.2429305350001 53.9452171900001,11.2556258470001 53.9408633480001,11.2854110040001 53.939683335,11.2937117850001 53.9408633480001,11.3341577480001 53.961371161,11.3418074880001 53.9583194030001,11.3520613940001 53.9441592470001,11.3582462900001 53.9408633480001,11.3999129570001 53.9408633480001,11.4004012380001 53.93773021,11.4387313160001 53.909125067,11.4462996750001 53.9061546900001,11.457692905 53.9061546900001,11.4589949880001 53.916693427,11.4690861340001 53.9327660180001,11.4768172540001 53.9527041690001,11.4724227220001 53.9688174500001,11.4798283210001 53.9761416690001,11.4895125660001 53.9806175800001,11.4978947270001 53.9818382830001,11.4959416020001 53.986314195,11.4935001960001 53.9976260440001,11.4917098320001 54.0023460960001,11.5258895190001 54.0227725280001,11.5258895190001 54.030218817,11.5190535820001 54.030218817,11.5190535820001 54.0364444030001,11.544606967 54.0301781270001,11.5532332690001 54.030218817,11.5734969410001 54.03904857,11.5913192070001 54.065619208,11.6047469410001 54.071234442,11.6128035820001 54.0729027360001,11.6193953790001 54.0772972680001,11.6245223320001 54.0836449240001,11.6289168630001 54.091050523,11.629567905 54.0960147160001,11.6220809250001 54.099554755,11.6220809250001 54.104681708,11.6252547540001 54.109808661,11.6294051440001 54.11322663,11.6331486340001 54.115912177,11.657888217 54.1422386740001,11.6897078790001 54.155218817,11.7287703790001 54.1585147160001,11.8122664720001 54.1498070330001,12.0506291020001 54.17991771,12.0881453790001 54.194077867,12.0932723320001 54.1654320330001,12.089528842 54.137640692,12.0916447270001 54.113999742,12.1150008470001 54.09788646,12.1053166020001 54.1100121110001,12.1003524100001 54.135972398,12.0950626960001 54.145697333,12.1054793630001 54.1573753930001,12.1342879570001 54.166978257,12.1428328790001 54.1804873720001,12.1316024100001 54.181138414,12.1208602220001 54.1799990910001,12.1106063160001 54.177435614,12.1013289720001 54.1736514340001,12.1088973320001 54.1830101580001,12.1428328790001 54.209173895,12.1630965500001 54.219916083,12.1868595710001 54.243353583,12.2009383470001 54.248724677,12.214040561 54.250962632,12.2893986340001 54.275091864,12.327321811 54.2937686220001,12.3421330090001 54.303941148,12.3781844410001 54.344916083,12.4383244150001 54.3958194030001,12.4448348320001 54.405462958,12.4860945970001 54.4473330750001,12.5019637380001 54.473578192,12.5134383470001 54.4822451840001,12.53386478 54.48826732,12.53386478 54.482123114,12.527028842 54.482123114,12.5483504570001 54.4620628930001,12.591481967 54.4517276060001,12.8191024100001 54.4517276060001,12.856618686 54.441107489,12.8796492850001 54.4487979190001,12.9083764980001 54.4446475280001,12.9211531910001 54.4334984400001,12.8963322270001 54.4200707050001,12.870778842 54.4168154970001,12.7636824880001 54.4221865910001,12.7209578790001 54.431586005,12.6945906910001 54.4336612,12.6867781910001 54.431626695,12.6761173840001 54.422552802,12.6704207690001 54.4200707050001,12.650075717 54.4200707050001,12.624196811 54.4229190120001,12.6145125660001 54.4197451840001,12.6084090500001 54.4063988300001,12.602224155 54.413804429,12.5969344410001 54.4119326840001,12.5880639980001 54.407456773,12.581716342 54.4063988300001,12.5835067070001 54.3978539080001,12.5876570970001 54.394029039,12.5940047540001 54.392767645,12.602224155 54.392075914,12.5986434250001 54.391546942,12.5958764980001 54.3915062520001,12.594411655 54.3902041690001,12.5947371750001 54.3858910180001,12.5755314460001 54.3919945330001,12.5540470710001 54.39081452,12.5359806650001 54.383734442,12.527028842 54.372259833,12.5107528 54.384263414,12.4909774100001 54.3900820980001,12.454763217 54.392075914,12.4384871750001 54.3875186220001,12.424978061 54.375921942,12.4184676440001 54.3606631530001,12.4240014980001 54.344916083,12.4096785820001 54.346625067,12.4038192070001 54.348089911,12.3967391290001 54.35175202,12.3899031910001 54.344916083,12.3964949880001 54.332953192,12.3916121750001 54.3211123720001,12.3790796230001 54.31244538,12.3625594410001 54.3102074240001,12.3696395190001 54.296576239,12.3779403 54.285874742,12.3801375660001 54.277085679,12.368825717 54.2691917990001,12.4124455090001 54.2514102230001,12.4367781910001 54.2477074240001,12.458181186 54.255560614,12.4426375660001 54.2551944030001,12.430837436 54.2586123720001,12.4103296230001 54.2691917990001,12.4168400400001 54.280951239,12.4262801440001 54.2896182310001,12.4514266290001 54.303941148,12.4572860040001 54.3063011740001,12.4682723320001 54.308335679,12.4724227220001 54.3102074240001,12.4755965500001 54.315130927,12.4765731130001 54.3277855490001,12.4786889980001 54.3318545590001,12.4956160820001 54.340277411,12.5605574880001 54.358587958,12.5470483730001 54.364488023,12.5407820970001 54.365423895,12.5407820970001 54.372259833,12.5593367850001 54.3762881530001,12.566091342 54.375921942,12.5742293630001 54.372259833,12.5742293630001 54.37909577,12.592946811 54.369330145,12.622731967 54.3739281270001,12.6772567070001 54.392075914,12.6750594410001 54.3954125020001,12.6723738940001 54.4029808610001,12.6704207690001 54.4063988300001,12.680837436 54.410874742,12.692556186 54.4136416690001,12.7048445970001 54.4146182310001,12.7175399100001 54.413804429,12.7175399100001 54.4063988300001,12.7024845710001 54.4041201840001,12.6923934250001 54.396185614,12.6865340500001 54.384751695,12.6840926440001 54.372259833,12.6966251960001 54.384955145,12.7011824880001 54.3916690120001,12.7046004570001 54.399603583,12.71355228 54.3900820980001,12.723806186 54.3812523460001,12.735036655 54.378159898,12.7461043630001 54.3858910180001,12.7578231130001 54.3797875020001,12.7685653 54.380072333,12.7783309250001 54.384751695,12.7871199880001 54.392075914,12.7898869150001 54.3843447940001,12.7946883470001 54.377142645,12.8009546230001 54.3707542990001,12.818044467 54.3579776060001,12.8217879570001 54.356146552,12.825368686 54.3572451840001,12.8354598320001 54.358587958,12.854665561 54.357855536,12.8647567070001 54.35956452,12.8759871750001 54.365423895,12.8845320970001 54.373480536,12.8948673840001 54.3897158870001,12.9038192070001 54.399603583,12.929372592 54.4143740910001,12.9690861340001 54.429388739,13.0087996750001 54.4380557310001,13.0341903 54.4336612,13.0214949880001 54.426459052,13.0210067070001 54.414536851,13.0285750660001 54.401841539,13.0403751960001 54.392075914,13.083669467 54.3789737,13.0955509770001 54.372259833,13.0766707690001 54.352525132,13.08073978 54.337144273,13.1092228520001 54.3102074240001,13.1120711600001 54.299302476,13.1120711600001 54.2884789080001,13.114919467 54.280015367,13.1259871750001 54.276597398,13.1706649100001 54.276597398,13.1706649100001 54.2691917990001,13.161306186 54.269029039,13.1546330090001 54.267320054,13.1434025400001 54.2630069030001,13.1761173840001 54.264837958,13.2283634770001 54.2473819030001,13.2631942070001 54.2424990910001,13.2888289720001 54.2342796900001,13.3217879570001 54.194525458,13.3488875660001 54.1804873720001,13.3333439460001 54.174017645,13.3215438160001 54.1668154970001,13.3465275400001 54.166937567,13.3837996750001 54.1781273460001,13.403493686 54.1736514340001,13.395681186 54.1619326840001,13.3908797540001 54.1572940120001,13.3829858730001 54.1531436220001,13.3947860040001 54.148911851,13.4021102220001 54.151312567,13.4087020190001 54.1546084660001,13.4177352220001 54.1531436220001,13.4231876960001 54.1480980490001,13.4376733730001 54.12518952,13.450368686 54.1104190120001,13.4650985040001 54.0984561220001,13.483571811 54.091294664,13.5070906910001 54.091050523,13.5070906910001 54.09788646,13.4988712900001 54.102484442,13.487478061 54.1139183610001,13.4792586600001 54.118353583,13.4792586600001 54.12518952,13.602712436 54.1394717470001,13.6323348320001 54.1475283870001,13.6834416020001 54.1680362,13.7119246750001 54.1736514340001,13.716481967 54.168443101,13.7146916020001 54.16404857,13.7082625660001 54.160874742,13.6982528 54.1593285180001,13.6982528 54.1531436220001,13.7287703790001 54.1438662780001,13.8081160820001 54.104681708,13.8081160820001 54.09788646,13.7937117850001 54.083197333,13.7854923840001 54.0639102230001,13.7732039720001 54.0463320980001,13.7461043630001 54.0364444030001,13.7581486340001 54.030991929,13.7871199880001 54.0091006530001,13.7976180350001 53.9989281270001,13.8034774100001 53.99632396,13.8317977220001 53.989243882,13.8386336600001 53.986314195,13.8431095710001 53.9795596370001,13.8462020190001 53.9722354190001,13.8491317070001 53.9675967470001,13.85027103 53.9640160180001,13.8489689460001 53.959458726,13.8486434250001 53.955552476,13.8525496750001 53.953843492,13.866872592 53.9546572940001,13.8701278 53.953843492,13.8754988940001 53.9512393250001,13.8816024100001 53.9490420590001,13.8879500660001 53.9475772160001,13.8935653 53.9470889340001,13.9060164720001 53.943060614,13.9075626960001 53.93353913,13.9013778 53.922308661,13.8901473320001 53.9129092470001,13.8185327480001 53.8779971370001,13.8081160820001 53.8651390650001,13.817067905 53.8529320330001,13.8357853520001 53.8474795590001,13.8543400400001 53.844916083,13.8628035820001 53.8412539730001,13.8691512380001 53.830308335,13.8837996750001 53.8176944030001,13.8999129570001 53.8091494810001,13.9106551440001 53.810492255,13.9842228520001 53.7739932310001,14.0173445970001 53.76951732,14.0335392590001 53.757513739,14.0374455090001 53.7552757830001,14.0615340500001 53.7564151060001,14.0688582690001 53.7552757830001,14.0940047540001 53.74632396,14.106130405 53.743353583,14.1865340500001 53.7398135440001,14.2146916020001 53.744859117,14.2265731130001 53.7586937520001,14.2341414720001 53.7617862,14.2501733730001 53.759955145,14.2644962900001 53.7516136740001,14.2674259770001 53.7354190120001,14.2595320970001 53.7279727230001,14.2127384770001 53.7080752620001,14.2253524100001 53.7037621110001,14.2400008470001 53.7007510440001,14.2561955090001 53.69944896,14.2639007202574 53.6999761596808,14.2638627520001 53.699875794,14.2651029860001 53.6717638150001,14.2609688720001 53.656209209,14.2760583900001 53.6366238410001,14.2970390220001 53.5977631640001,14.2988993730001 53.5878929650001,14.2962121990001 53.551306051,14.296935669 53.5291368620001,14.3041703700001 53.5085179650001,14.3284582930001 53.4860903940001,14.3388969320001 53.4652131150001,14.359877564 53.4440774540001,14.3703162020001 53.392297669,14.3912605110001 53.3340170030001,14.3980147700001 53.3152222700001,14.3995650640001 53.3067473350001,14.4001851800001 53.2886089080001,14.403285767 53.278790385,14.4093835860001 53.2724341840001,14.42467981 53.2646568810001,14.4286072190001 53.259075827,14.4416296800001 53.2518411260001,14.4155847570001 53.2209902960001,14.4082467040001 53.214401551,14.3977047120001 53.2109909060001,14.3877828370001 53.2020767220001,14.3806514890001 53.189855245,14.3778609620001 53.1765485640001,14.3814783120001 53.160296326,14.3874727790001 53.1461369840001,14.3895398350001 53.1316675830001,14.3595675050001 53.075056051,14.3567769770001 53.0666844690001,14.343341105 53.048623555,14.3126453050001 53.0292190550001,14.2537341720001 53.0008745330001,14.192859334 52.9816509,14.1444901930001 52.95992096,14.1444901930001 52.95369395,14.1504846600001 52.943642884,14.1626802980001 52.9081670130001,14.1649540610001 52.8956613170001,14.1608199460001 52.8767477420001,14.1504846600001 52.8646296190001,14.123922973 52.8506511440001,14.135395142 52.8365951540001,14.1527584230001 52.8283269250001,14.1737390540001 52.824347839,14.1959599200001 52.8233659870001,14.2160103750001 52.8179916390001,14.2486698820001 52.794582215,14.2759550370001 52.785719706,14.3822017820001 52.738151551,14.3977047120001 52.727118633,14.4319145100001 52.6860875460001,14.442353149 52.679963888,14.461370076 52.6745637010001,14.4901021730001 52.650637512,14.5499434810001 52.6361939500001,14.6079648280001 52.5964629630001,14.6137121990001 52.592527364,14.6448214110001 52.5769210820001,14.6168127850001 52.5410318,14.6090613200001 52.517803243,14.6276648360001 52.5074162800001,14.6323157150001 52.4967450980001,14.6157792560001 52.473283997,14.5915946860001 52.449797059,14.5398149010001 52.4218659470001,14.545395956 52.3821526080001,14.5691671140001 52.3385118610001,14.5901477460001 52.3094180300001,14.5841532800001 52.291227926,14.6065808510001 52.2757508350001,14.6404805900001 52.2650538130001,14.6689026280001 52.260997213,14.6969112550001 52.2534782930001,14.7124141840001 52.235908305,14.712104126 52.2154444380001,14.6925704350001 52.1995797730001,14.6925704350001 52.1933786010001,14.7070398360001 52.1794518030001,14.70321578 52.16516327,14.6924670820001 52.1469731650001,14.6863692630001 52.1210315960001,14.6963944910001 52.1066913860001,14.7614034430001 52.0766673790001,14.743006633 52.062533875,14.7353585200001 52.054033102,14.7321545820001 52.0450672410001,14.7302942300001 52.0358946740001,14.726056762 52.026437887,14.7044560140001 52.0022274780001,14.6990816650001 51.9925123090001,14.6955676670001 51.9314566040001,14.687092733 51.9118970740001,14.6716931560001 51.8938878380001,14.6532963460001 51.878617453,14.5959355070001 51.8424181120001,14.5828096930001 51.825080668,14.585806925 51.803893332,14.6022400310001 51.7883128870001,14.6203267820001 51.7805355840001,14.6341760660001 51.7690117390001,14.638103475 51.7426309210001,14.6484387610001 51.7172061160001,14.6709696860001 51.7007730110001,14.7195455320001 51.675632426,14.7324646400001 51.6583466590001,14.7422831620001 51.632973532,14.7439368080001 51.6066443900001,14.7321545820001 51.586619772,14.7127242430001 51.567421977,14.7045593670001 51.547991638,14.7067699600001 51.5408280640001,14.7100370680001 51.5302407840001,14.7321545820001 51.5158230590001,14.7974735920001 51.502102966,14.8185575760001 51.4926978560001,14.8185575760001 51.4925945040001,14.8413985590001 51.484429627,14.8883207600001 51.475747987,14.9109550380001 51.468978373,14.9265613200001 51.4613302610001,14.9450614830001 51.4491863,14.9553967690001 51.43541453,14.9469218350001 51.422908834,14.950647846 51.396539377,14.9566370040001 51.354153341,14.9566370040001 51.3532231650001,14.9609778240001 51.335291443,14.963768352 51.3283926390001,14.9822685140001 51.3080062870001,15.0049027920001 51.2912889610001,15.0194755450001 51.2716777550001,15.0143079010001 51.2426614390001,15.017925252 51.2395608520001,15.0220593670001 51.2367703250001,15.0049027920001 51.215608826,14.9913635660001 51.1889696250001,14.9831986900001 51.160909323,14.9820618080001 51.1356395470001,14.979994751 51.1227979540001,14.9733801680001 51.1161316940001,14.965628703 51.111506653,14.9602543540001 51.104582011,14.9584973550001 51.0947376510001,14.958290649 51.075514018,14.9552934170001 51.0640418500001,14.9106449790001 50.992650859,14.8602087810001 50.9168415330001,14.824655395 50.891830139,14.8104960530001 50.8770506800001,14.8103927 50.8584471640001,14.7945797120001 50.8316270960001,14.7850712480001 50.820051575,14.7753560790001 50.812971904,14.7592330320001 50.810181376,14.737528931 50.8106981410001,14.7004252520001 50.8159691370001,14.6621846920001 50.834365946,14.6479219970001 50.8393785610001,14.6131954350001 50.8455797320001,14.6083378500001 50.8530728150001,14.6118518470001 50.870952861,14.6288017170001 50.8961192830001,14.6345894780001 50.9094001270001,14.6292151280001 50.9207172660001,14.6171228430001 50.920872294,14.5618290610001 50.9063512170001,14.5503568930001 50.912087301,14.5558345940001 50.9242829390001,14.5678235270001 50.9386489870001,14.575574992 50.950689596,14.577435343 50.965727437,14.5743347580001 50.9754942830001,14.5666866450001 50.983400778,14.55459436 50.992650859,14.5422953690001 50.9987486780001,14.5153202720001 51.0030378220001,14.5029179280001 51.008515524,14.4935128180001 51.0167062380001,14.4901021730001 51.022700704,14.4879317630001 51.028721009,14.4821440020001 51.0371959430001,14.4734623620001 51.0233724980001,14.4620935470001 51.0196517940001,14.4258166910001 51.0209437060001,14.3978080640001 51.0131147260001,14.386749308 51.013269756,14.3758972570001 51.016990459,14.3693860270001 51.0224423220001,14.3641150310001 51.027997538,14.3565702720001 51.032338359,14.3193632400001 51.0400123090001,14.2875305580001 51.036834208,14.2635526940001 51.021434632,14.2494967040001 50.992650859,14.2383345950001 50.982470602,14.2500134690001 50.9776130170001,14.2838098550001 50.9748224900001,14.3037569580001 50.9697065230001,14.3022066650001 50.967691142,14.2937317300001 50.9639704390001,14.2928015540001 50.9534801240001,14.3183297120001 50.9375121060001,14.3552266850001 50.9306391400001,14.3818917240001 50.920872294,14.3758972570001 50.895964254,14.346545044 50.8802029420001,14.2681002200001 50.8841303510001,14.232133423 50.879376119,14.2212813720001 50.872606507,14.2029879150001 50.8551398730001,14.1907922770001 50.8479051720001,14.0349361570001 50.8025849410001,14.015712524 50.8017581180001,13.9791256100001 50.8047553510001,13.9595919190001 50.802068177,13.9488432210001 50.797210592,13.9335469970001 50.7848082480001,13.9233150640001 50.779950664,13.9107060140001 50.778762105,13.9009908440001 50.780622457,13.89251591 50.7804157520001,13.8833175050001 50.773232727,13.8790800370001 50.7635175580001,13.880320272 50.7550426230001,13.8826973880001 50.7480146280001,13.8821806240001 50.742743632,13.8753593340001 50.736542461,13.8695715740001 50.7352505490001,13.8634737550001 50.7351471970001,13.8345349530001 50.723675029,13.8165515540001 50.721349589,13.770662882 50.7246052040001,13.7490621340001 50.723209941,13.7110282800001 50.7142699180001,13.6917529700001 50.7118411260001,13.6019393310001 50.712151185,13.5565674230001 50.706725159,13.5156396890001 50.6910155240001,13.5272152100001 50.675667623,13.523287801 50.6621800750001,13.5099552810001 50.6512246710001,13.4933154710001 50.6432148230001,13.4991032300001 50.635204977,13.4981730550001 50.6291588340001,13.4921785890001 50.6244562790001,13.4822567130001 50.620890605,13.4648934320001 50.6070929980001,13.4479435630001 50.597274476,13.4293400480001 50.5943289190001,13.4070158280001 50.6013052370001,13.4004012450001 50.606576234,13.3863452560001 50.6216140750001,13.3809709060001 50.6254898070001,13.3687752680001 50.628332011,13.3659847410001 50.627091777,13.3653646240001 50.6234744270001,13.3593701580001 50.6193403120001,13.3218530680001 50.6023904430001,13.3162720130001 50.5960342410001,13.3056266680001 50.5757770800001,13.2846460370001 50.5689557900001,13.2680062260001 50.5736583460001,13.2517798250001 50.5808930470001,13.2323494870001 50.5820299280001,13.1990698650001 50.5253408820001,13.1847038170001 50.5087527470001,13.1601058350001 50.497022197,13.1073958740001 50.4989859010001,13.0791805420001 50.492784729,13.0789738360001 50.4926813760001,13.0788704830001 50.4926813760001,13.0697754310001 50.491079407,13.0603703210001 50.4906143190001,13.0510685630001 50.4911310840001,13.0422835700001 50.492784729,13.034532104 50.496505432,13.0262638750001 50.497642314,13.0178922930001 50.4963504040001,13.0096240640001 50.4926813760001,13.0031128330001 50.4519086720001,12.996601603 50.433666891,12.9824422610001 50.42296987,12.9606311030001 50.409234123,12.9525732830001 50.404159648,12.9183634850001 50.4053998820001,12.8257593180001 50.4414183560001,12.817387736 50.4430203250001,12.8083960370001 50.4418317670001,12.7943400470001 50.4358889770001,12.7881388750001 50.434338684,12.77025883 50.4359406540001,12.7542391360001 50.4353205360001,12.737909383 50.4315481570001,12.7250936280001 50.4234349580001,12.702976115 50.40152415,12.6918140060001 50.394651184,12.6787915440001 50.3937210080001,12.6253581140001 50.3999221810001,12.5505306400001 50.3963565070001,12.5102230220001 50.388760071,12.482524454 50.3735672,12.475083048 50.3694330850001,12.4715690510001 50.364472148,12.4695019940001 50.3594078580001,12.4668148190001 50.3549120080001,12.4670215250001 50.3528449510001,12.4683651130001 50.3494859830001,12.4689852290001 50.345558574,12.4668148190001 50.341889547,12.4627840580001 50.340494283,12.4537923590001 50.3407009900001,12.4501750080001 50.3393574020001,12.4382894290001 50.3325361130001,12.4089372150001 50.321994121,12.3981885170001 50.3151728310001,12.3671826580001 50.279051005,12.3558138420001 50.271402894,12.3446517330001 50.2663902800001,12.3364868570001 50.2585871380001,12.3337996830001 50.2427224730001,12.3140592860001 50.2264960740001,12.3086849360001 50.217090963,12.3055843510001 50.1993142700001,12.3085815830001 50.186911927,12.3143693440001 50.1762149050001,12.3143693440001 50.1673265590001,12.3004167070001 50.1608153280001,12.2833634840001 50.1622105920001,12.2732349040001 50.1723391730001,12.261245972 50.199882711,12.2602124430001 50.2050503550001,12.2584554450001 50.210889791,12.25432133 50.2174010210001,12.2499805100001 50.221173401,12.2325138750001 50.2324905400001,12.2299300540001 50.2348159790001,12.228896525 50.2370380660001,12.2298267010001 50.2390534470001,12.2325138750001 50.2409654750001,12.2337541100001 50.241688944,12.2350976970001 50.242257385,12.2364412840001 50.2425674450001,12.2379915770001 50.2427224730001,12.2424357500001 50.2483552040001,12.2429525150001 50.252954407,12.2396452230001 50.256571758,12.2325138750001 50.259103902,12.2037817790001 50.25956899,12.1892090250001 50.2624628710001,12.1780469160001 50.268767395,12.1741195070001 50.2765705370001,12.1744295650001 50.293727112,12.1685384520001 50.302977193,12.149314819 50.311710511,12.101343547 50.3139803380001,12.076140991 50.3151728310001,12.0991886800001 50.2997732550001,12.1072502030001 50.2908849080001,12.1109709060001 50.2766222130001,12.1091105550001 50.263806458,12.1023926190001 50.259155579,12.0920573330001 50.2548147580001,12.0795516350001 50.2427224730001,12.0898869220001 50.230836894,12.1392895920001 50.2110448200001,12.1637842200001 50.1937848920001,12.1750496820001 50.182622783,12.1826977950001 50.170737203,12.1855916750001 50.1556993610001,12.1785636800001 50.132961731,12.1791837970001 50.1179755660001,12.1878654380001 50.1028343720001,12.20202478 50.0945144650001,12.2180444740001 50.0885716760001,12.2325138750001 50.080510152,12.241402221 50.070639954,12.2434692790001 50.06040802,12.243675984 50.0513129690001,12.2468799230001 50.0449567670001,12.3981885170001 49.9927635700001,12.3992220460001 49.9927635700001,12.4145182700001 49.9830484010001,12.4513118890001 49.980567932,12.468158406 49.970232646,12.4707422280001 49.955608216,12.4638175860001 49.9421206660001,12.4626807050001 49.9312686160001,12.5036084390001 49.915765687,12.5178711350001 49.9122000120001,12.5240723060001 49.9049653120001,12.5209717200001 49.885534973,12.5129101970001 49.8702387490001,12.489862508 49.8426952110001,12.482524454 49.8272439580001,12.4624739990001 49.8312230430001,12.45637618 49.817115377,12.4558594150001 49.796134746,12.4526554770001 49.7797016400001,12.4367391350001 49.769263001,12.3953979900001 49.757894186,12.3836157630001 49.7428563440001,12.3885767 49.7323143510001,12.3989119870001 49.719498597,12.41958256 49.7002232870001,12.4339486080001 49.6918000290001,12.4492448320001 49.685030416,12.482524454 49.67469513,12.4963737390001 49.6699925750001,12.5046419680001 49.6593989050001,12.5053654370001 49.6461180630001,12.4968905030001 49.633870748,12.4994743240001 49.6325271610001,12.5074324950001 49.6299950160001,12.5026782630001 49.6221401980001,12.501954793 49.6197114060001,12.5121867270001 49.611649882,12.5360612390001 49.6031232710001,12.5466032300001 49.5955785120001,12.5536312250001 49.5847264610001,12.558282104 49.5625572720001,12.5623128670001 49.5508267220001,12.5687207440001 49.5388377890001,12.5750252680001 49.529897766,12.5828800870001 49.5224046830001,12.5937321370001 49.5150149540001,12.6049975990001 49.512792867,12.6155395920001 49.5137747200001,12.6229809980001 49.50984731,12.6243245850001 49.4930007940001,12.6272184650001 49.4601862590001,12.6321794020001 49.443959859,12.6435482180001 49.429490458,12.6630819090001 49.41889679,12.709177286 49.4047374470001,12.7293310950001 49.3911465460001,12.7620939530001 49.3432424930001,12.7779069410001 49.3325454720001,12.7977506920001 49.3278429170001,12.8566618250001 49.3222101850001,12.8753686930001 49.323863831,12.8709245190001 49.336731263,12.8846704510001 49.3395734670001,12.9229110110001 49.332700501,12.9398608810001 49.3267577110001,12.9543302820001 49.319109599,12.9824422610001 49.299627584,12.9998055420001 49.2949250290001,13.005386597 49.286760153,13.0067301840001 49.277096659,13.0112777100001 49.2677949020001,13.0432137450001 49.242938538,13.0434204510001 49.2427835090001,13.055822795 49.238184306,13.1494604890001 49.1548302210001,13.1625863030001 49.1351415,13.1785026450001 49.1183466600001,13.2068213300001 49.1074946090001,13.2672827550001 49.1056342570001,13.2873332110001 49.100569967,13.2995288490001 49.0936453250001,13.3299145910001 49.06692861,13.372392618 49.0385065720001,13.3835547280001 49.021091614,13.3841748450001 48.993031311,13.3985408930001 48.9776834110001,13.42727299 48.959958395,13.458898966 48.9450239060001,13.4822567130001 48.9376341760001,13.492592 48.955049133,13.5021004640001 48.9660562140001,13.515949747 48.970242005,13.5223954470001 48.9693419300001,13.5388940830001 48.9670380660001,13.5564640710001 48.959958395,13.5734139400001 48.9510183720001,13.5904671630001 48.9448172,13.6086572670001 48.9461607870001,13.6111377360001 48.9272472130001,13.6217830810001 48.9090571090001,13.6373893630001 48.8934508260001,13.6544425860001 48.88223704,13.6733561600001 48.876345928,13.710614868 48.872470195,13.7246708580001 48.8673025520001,13.7479252520001 48.843376363,13.7961910400001 48.7798143520001,13.8157247310001 48.7664301560001))

rejection_sampling_benchmark.cpp

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <string>
#include <fstream>

#include <boost/geometry.hpp>
#include <boost/geometry/extensions/random/uniform_point_distribution.hpp>
#include <boost/geometry/extensions/random/strategies/agnostic/uniform_convex_polygon_sampler.hpp>
#include <boost/geometry/extensions/random/strategies/agnostic/uniform_convex_hull_rejection.hpp>
#include <boost/geometry/extensions/random/strategies/cartesian/uniform_point_distribution_triangle.hpp>

namespace bg = boost::geometry;

int main(int argc, char* argv[]) {
    using point = bg::model::point<double, 2, bg::cs::cartesian>;
    using polygon = bg::model::polygon<point>;
    using box = bg::model::box<point>;
    std::default_random_engine generator;

    const std::size_t points_count = 100;
    polygon poly;
    std::ifstream infile (argv[1]);
    std::string line;
    std::getline(infile, line);
    bg::read_wkt(line, poly);
    polygon hull;
    bg::convex_hull(poly, hull);
    double poly_area = bg::area(poly);
    double hull_accept = poly_area / bg::area(hull);
    double env_accept = poly_area / bg::area(bg::return_envelope<box>(poly));
    std::cout << "Envelope acceptance probability: " << env_accept << "\n";
    std::cout << "Hull acceptance probability: " << hull_accept << "\n\n";
    std::cout << "Poly length: " << boost::size(poly.outer()) << "\n";
    std::cout << "Hull length: " << boost::size(hull.outer()) << "\n\n";

    using hull_dist_t = bg::random::uniform_point_distribution
                <
                    polygon,
                    point,
                    bg::strategy::uniform_point_distribution::uniform_convex_hull_rejection
                        <
                            point,
                            polygon,
                            bg::strategy::uniform_point_distribution
                                ::uniform_2d_cartesian_triangle<point, polygon>,
                            bg::strategy::side::side_by_triangle<double>
                        >
                >;
    using env_dist_t = bg::random::uniform_point_distribution
                <
                    polygon,
                    point
                >;

    std::size_t samples = 1'000'000;
    std::size_t runs = 1;

    do {
        std::cout << "samples: " << samples << "\nruns: " << runs << "\n\n";
        auto start = std::chrono::system_clock::now();

        for(int i = 0; i < runs; ++i) {
            hull_dist_t dist(poly);
            for(int j = 0; j < samples; ++j) {
                dist(generator);
            }
        }

        auto end = std::chrono::system_clock::now();
        auto elapsed =
            std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        std::cout << "Hull rejection: " << elapsed.count() << " ms.\n";

        start = std::chrono::system_clock::now();

            for(int i = 0; i < runs; ++i) {
            env_dist_t dist(poly);

            for(int j = 0; j < samples; ++j) {
                dist(generator);
            }
        }

        end = std::chrono::system_clock::now();
        elapsed =
            std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

        std::cout << "Envelope rejection: " << elapsed.count() << " ms.\n\n\n";
        
        samples /= 100;
        runs *= 100;
    } while(samples > 0);

    hull_dist_t dist1(poly);
    env_dist_t dist2(poly);

    std::cout << "Estimated cost per sample regardless of acceptance: \n";
    samples = 1'000'000;
    auto start = std::chrono::system_clock::now();
    for(int i = 0; i < samples; ++i)
        dist1(generator);
    auto end = std::chrono::system_clock::now();
    auto elapsed =
            std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "hull:\t" << (elapsed * hull_accept) / samples << " ms \n";

    start = std::chrono::system_clock::now();
    for(int i = 0; i < samples; ++i)
        dist2(generator);
    end = std::chrono::system_clock::now();
    elapsed =
            std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "env:\t" << (elapsed * env_accept) / samples << " ms \n";

    return 0;
}

small_polygon.wkt

POLYGON((16 21,17.1226 17.5451,20.7553 17.5451,17.8164 15.4098,18.9389 11.9549,16 14.0902,13.0611 11.9549,14.1836 15.4098,11.2447 17.5451,14.8774 17.5451,16 21))