velipso / polybooljs Goto Github PK

View Code? Open in Web Editor NEW

601.0 14.0 90.0 93 KB

Boolean operations on polygons (union, intersection, difference, xor)

License: MIT License

Shell 0.53% JavaScript 99.47%

polygon-clipping polygon-intersection polygon-union polygon-boolean geojson

polybooljs's Introduction

polybooljs

Boolean operations on polygons (union, intersection, difference, xor).

NOTE: I am no longer maintaining this, but I have created a TypeScript version, available here: @velipso/polybool.

Features

Clips polygons for all boolean operations
Removes unnecessary vertices
Handles segments that are coincident (overlap perfectly, share vertices, one inside the other, etc)
Uses formulas that take floating point irregularities into account (via configurable epsilon)
Provides an API for constructing efficient sequences of operations
Support for GeoJSON "Polygon" and "MultiPolygon" types (experimental)

Resources

Demo + Animation
Companion Tutorial
Based somewhat on the F. Martinez (2008) algorithm: Paper, Code

Ports

Other kind souls have ported this library:

Java port by @the3deers
Java port by @Menecats
.NET port by @idormenco
Flutter/Dart port by @mohammedX6
Python port by @KaivnD
Please make a ticket if you'd like to be added here :-)

Installing

npm install polybooljs

Or, for the browser, look in the dist/ directory for a single file build. When included on a page, it will expose the global PolyBool.

Example

var PolyBool = require('polybooljs');
PolyBool.intersect({
    regions: [
      [[50,50], [150,150], [190,50]],
      [[130,50], [290,150], [290,50]]
    ],
    inverted: false
  }, {
    regions: [
      [[110,20], [110,110], [20,20]],
      [[130,170], [130,20], [260,20], [260,170]]
    ],
    inverted: false
  });
===> {
  regions: [
    [[50,50], [110,50], [110,110]],
    [[178,80], [130,50], [130,130], [150,150]],
    [[178,80], [190,50], [260,50], [260,131.25]]
  ],
  inverted: false
}

Basic Usage

var poly = PolyBool.union        (poly1, poly2);
var poly = PolyBool.intersect    (poly1, poly2);
var poly = PolyBool.difference   (poly1, poly2); // poly1 - poly2
var poly = PolyBool.differenceRev(poly1, poly2); // poly2 - poly1
var poly = PolyBool.xor          (poly1, poly2);

Where poly1, poly2, and the return value are Polygon objects, in the format of:

// polygon format
{
  regions: [ // list of regions
    // each region is a list of points
    [[50,50], [150,150], [190,50]],
    [[130,50], [290,150], [290,50]]
  ],
  inverted: false // is this polygon inverted?
}

GeoJSON (experimental)

There are also functions for converting between the native polygon format and GeoJSON.

Note: These functions are currently experimental, and I'm hoping users can provide feedback. Please comment in this issue on GitHub -- including letting me know if it's working as expected. I don't use GeoJSON, but I thought I would take a crack at conversion functions.

Use the following functions:

var geojson = PolyBool.polygonToGeoJSON(poly);
var poly    = PolyBool.polygonFromGeoJSON(geojson);

Only "Polygon" and "MultiPolygon" types are supported.

Core API

var segments = PolyBool.segments(polygon);
var combined = PolyBool.combine(segments1, segments2);
var segments = PolyBool.selectUnion(combined);
var segments = PolyBool.selectIntersect(combined);
var segments = PolyBool.selectDifference(combined);
var segments = PolyBool.selectDifferenceRev(combined);
var segments = PolyBool.selectXor(combined);
var polygon  = PolyBool.polygon(segments);

Depending on your needs, it might be more efficient to construct your own sequence of operations using the lower-level API. Note that PolyBool.union, PolyBool.intersect, etc, are just thin wrappers for convenience.

There are three types of objects you will encounter in the core API:

Polygons (discussed above, this is a list of regions and an inverted flag)
Segments
Combined Segments

The basic flow chart of the API is:

You start by converting Polygons to Segments using PolyBool.segments(poly).

You convert Segments to Combined Segments using PolyBool.combine(seg1, seg2).

You select the resulting Segments from the Combined Segments using one of the selection operators PolyBool.selectUnion(combined), PolyBool.selectIntersect(combined), etc. These selection functions return Segments.

Once you're done, you convert the Segments back to Polygons using PolyBool.polygon(segments).

Each transition is costly, so you want to navigate wisely. The selection transition is the least costly.

Advanced Example 1

Suppose you wanted to union a list of polygons together. The naive way to do it would be:

// works but not efficient
var result = polygons[0];
for (var i = 1; i < polygons.length; i++)
  result = PolyBool.union(result, polygons[i]);
return result;

Instead, it's more efficient to use the core API directly, like this:

// works AND efficient
var segments = PolyBool.segments(polygons[0]);
for (var i = 1; i < polygons.length; i++){
  var seg2 = PolyBool.segments(polygons[i]);
  var comb = PolyBool.combine(segments, seg2);
  segments = PolyBool.selectUnion(comb);
}
return PolyBool.polygon(segments);

Advanced Example 2

Suppose you want to calculate all operations on two polygons. The naive way to do it would be:

// works but not efficient
return {
  union        : PolyBool.union        (poly1, poly2),
  intersect    : PolyBool.intersect    (poly1, poly2),
  difference   : PolyBool.difference   (poly1, poly2),
  differenceRev: PolyBool.differenceRev(poly1, poly2),
  xor          : PolyBool.xor          (poly1, poly2)
};

Instead, it's more efficient to use the core API directly, like this:

// works AND efficient
var seg1 = PolyBool.segments(poly1);
var seg2 = PolyBool.segments(poly2);
var comb = PolyBool.combine(seg1, seg2);
return {
  union        : PolyBool.polygon(PolyBool.selectUnion        (comb)),
  intersect    : PolyBool.polygon(PolyBool.selectIntersect    (comb)),
  difference   : PolyBool.polygon(PolyBool.selectDifference   (comb)),
  differenceRev: PolyBool.polygon(PolyBool.selectDifferenceRev(comb)),
  xor          : PolyBool.polygon(PolyBool.selectXor          (comb))
};

Advanced Example 3

As an added bonus, just going from Polygon to Segments and back performs simplification on the polygon.

Suppose you have garbage polygon data and just want to clean it up. The naive way to do it would be:

// union the polygon with nothing in order to clean up the data
// works but not efficient
var cleaned = PolyBool.union(polygon, { regions: [], inverted: false });

Instead, skip the combination and selection phase:

// works AND efficient
var cleaned = PolyBool.polygon(PolyBool.segments(polygon));

Epsilon

Due to the beauty of floating point reality, floating point calculations are not exactly perfect. This is a problem when trying to detect whether lines are on top of each other, or if vertices are exactly the same.

Normally you would expect this to work:

if (A === B)
  /* A and B are equal */;
else
  /* A and B are not equal */;

But for inexact floating point math, instead we use:

if (Math.abs(A - B) < epsilon)
  /* A and B are equal */;
else
  /* A and B are not equal */;

You can set the epsilon value using:

PolyBool.epsilon(newEpsilonValue);

Or, if you just want to get the current value:

var currentEpsilon = PolyBool.epsilon();

The default epsilon value is 0.0000000001.

If your polygons are really really large or really really tiny, then you will probably have to come up with your own epsilon value -- otherwise, the default should be fine.

If PolyBool detects that your epsilon is too small or too large, it will throw an error:

PolyBool: Zero-length segment detected; your epsilon is probably too small or too large

Build Log

The library also has an option for tracking execution of the internal algorithms. This is useful for debugging or creating the animation on the demo page.

By default, the logging is disabled. But you can enable or reset it via:

var buildLog = PolyBool.buildLog(true);

The return value is an empty list that will have log entries added to it as more API calls are made.

You can inspect the log by looking in the values:

buildLog.forEach(function(logEntry){
  console.log(logEntry.type, logEntry.data);
});

Don't rely on the build log functionality to be consistent across releases.

You can disable the build log via:

PolyBool.buildLog(false);

You can get the current list (or false if disabled) via:

var currentLog = PolyBool.buildLog();

polybooljs's People

Contributors

Stargazers

Watchers

Forkers

fijixfiji egjiri idormenco asnowbear manubb townewgokgok konradqcharczyk maheshnaikm rakesh-webdeveloper js-van joegeorge-git zhhd n15e manuelschmidt vmalepati1 jsxcad whoamipls smarteacher tjhxrrr reggino kaixiang1992 theohonohan b1sounours geopic eddig 1094293008 helingping pilihou pb57124 guoliangjun yesonghong gelivablechina jamshan fil wavebbg godxkey mrdongxf winaungcho zgww moli3663 skrat ryanbtseng 6ziliuliu visualfox jiangyuan15 liuqiang2030 haodouya changshazhou zero-meta funfrog-by xiaoming0716 mulinsendong ue007 continuemycoding wenluzhizhi 13071058995 nofel-scale lyjpeppers peakrock flexelektro 303182519 cheungbass sivhma aninam may3rd bplok20010 cjjkoko gamlittle sunsnail0 davidinterad lanbozhanglu meadowair aiadaniel williamfindtheresa winnerlbm n1ka96 jujuadams pointgh 9144809728 rijqpo34 darkomenz bytesfellow ruolidevelop sue602

polybooljs's Issues

Failure case

This hoses up during the self-intersection phase

{
  "poly1": {
    "regions": [
      [
        [
          500,
          60
        ],
        [
          500,
          150
        ],
        [
          320,
          150
        ],
        [
          260,
          210
        ],
        [
          200,
          150
        ],
        [
          200,
          60
        ]
      ]
    ],
    "inverted": false
  },
  "poly2": {
    "regions": [
      [
        [
          500,
          60
        ],
        [
          500,
          150
        ],
        [
          460,
          190
        ],
        [
          460,
          110
        ],
        [
          400,
          180
        ],
        [
          70,
          90
        ]
      ],
      [
        [
          220,
          170
        ],
        [
          580,
          130
        ],
        [
          310,
          160
        ],
        [
          310,
          210
        ],
        [
          260,
          170
        ],
        [
          240,
          190
        ]
      ]
    ],
    "inverted": false
  }
}

Right Epsilon for 6 decimal GeoJSON ?

What would be the best epsilon for GeoJSON with 6 decimals coordinates ?

algorithm comparison

not really an issue, but I wanted to dump a reference here too:

I made a small comparison between some boolean operation algorithms and
wanted to share the results: https://daef.github.io/poly-bool-comparison/

Yet another Java implementation

Hi @velipso, I'm creating this issue to let you know that I've created another Java port of this library, you can find it here https://github.com/Menecats/polybool-java.

This is a pure Java port of your library, I've also made the experimental Epsilon code from PR #8 available for use.
It's already available on Maven central Here

Cheers,
menecats

Adapt code for polyline clipping.

How hard would it be to adapt this code more directly to polyline-polygon clipping? Basically one of your shapes has no region on either side of it and is just a bunch of segments but you solve whether those segments have the other region on both sides allowing you to extract all the segments with the clip region on both sides thereby giving you those segments found inside the polygon. Equally if you solve for those segments which don't have both sides, you'd get the polyline occlusion.

I assume it's the matching results routine and the quite possibly some tweaks for determining the insideness of the segments.

Are bezier curves supported?

Hi, great library. The example and documentation don't talk much about bezier curves. Are they supported?

Geometric meaning of epsilon?

I understand the necessity for epsilon in floating-point comparisons, but is there some geometric interpretation to it? Something like "the minimum edge length to not cause errors is x * epsilon" for some factor x?

Polygon Union produces incorrect result

I have a case where when performing a union between to polygons where the result should be a doughnut shape, but the resulting polygon is completely filled.

This how the bigger polygon looks like:

The smaller polygon fills the missing piece on the track. What I expected is to get the complete track, what you get back is a completely filled shape.

Here are the points for the 2 polygons:
[[2796008.64832628, 333425.207920873], [2796007.03499144, 333431.259997593], [2796006.73954923, 333431.83983557], [2795999.27253848, 333445.988906098], [2795962.15502816, 333504.628835434], [2795963.28196301, 333505.350859358], [2795944.0748989, 333535.32264442], [2795871.62085854, 333651.640757779], [2795746.48419616, 333850.695125205], [2795736.09880924, 333868.881332771], [2795733.04605178, 333875.911888783], [2795730.83572409, 333882.964101318], [2795729.44088609, 333889.955644238], [2795728.74628529, 333897.824134068], [2795728.85525494, 333904.00936056], [2795729.76908333, 333912.341124962], [2795737.20384889, 333951.9332175], [2795737.30565133, 333952.575972848], [2795738.17681153, 333959.301411651], [2795737.38069225, 333966.48282041], [2795737.27888981, 333967.125575758], [2795734.04509632, 333974.892500239], [2795733.74965411, 333975.472338215], [2795723.52682623, 333988.469986966], [2795718.35987128, 333995.793124714], [2795606.45675451, 334172.546758759], [2795594.79923167, 334189.723561546], [2795563.02893866, 334230.997583318], [2795562.56877664, 334231.457745341], [2795554.56607344, 334239.139127599], [2795537.94206851, 334252.282248975], [2795529.49457203, 334260.016946758], [2795522.32456479, 334268.021114406], [2795512.93901584, 334280.609390501], [2795487.76313888, 334323.643931164], [2795471.73293785, 334348.630608586], [2795464.48846948, 334360.884754142], [2795458.90317081, 334371.925761292], [2795452.12267386, 334387.904526936], [2795451.82723165, 334388.484364912], [2795444.77792342, 334401.269637576], [2795225.77157185, 334750.960399843], [2795220.76106677, 334758.118773856], [2795215.3296282, 334764.460086763], [2795209.56576393, 334770.265462336], [2795209.10560191, 334770.725624359], [2795199.19391887, 334779.358586509], [2795195.00097342, 334784.803058442], [2795192.27344514, 334791.213170391], [2795190.84562656, 334799.942553383], [2795191.09813367, 334809.33495003], [2795192.91494662, 334820.463129733], [2795193.01674906, 334821.105885081], [2795192.96989956, 334824.93927199], [2795192.20238478, 334829.910211483], [2795192.10058233, 334830.552966831], [2795190.43545715, 334835.821185349], [2795187.58914691, 334842.11052285], [2795187.29370471, 334842.690360827], [2795177.76031327, 334859.810578134], [2795161.61976526, 334886.391697013], [2795145.87270405, 334908.333803526], [2795135.84060824, 334923.573346156], [2795083.51592182, 335007.747379794], [2794971.40807191, 335184.849988637], [2794925.59949378, 335259.703666636], [2794857.63790023, 335367.307465935], [2794674.57777531, 335660.632314422], [2794654.4562924, 335690.692744142], [2794639.65107464, 335708.813901674], [2794637.4761162, 335712.857099682], [2794628.91615444, 335732.137169466], [2794628.62071223, 335732.717007442], [2794616.27539864, 335753.525609198], [2794530.95812759, 335889.32676952], [2794461.06716593, 336001.641926197], [2794414.66797061, 336074.81447656], [2794265.62286505, 336315.176892708], [2794148.65681456, 336501.1117366], [2794127.77916591, 336536.463115305], [2794123.74076269, 336544.581531103], [2794120.47414264, 336552.629574806], [2794115.71556772, 336566.984145519], [2794103.66565767, 336611.863980495], [2794090.52998466, 336657.319099604], [2794085.14970894, 336672.253545649], [2794079.6328158, 336683.183880648], [2794079.33737359, 336683.763718625], [2794015.79590679, 336785.586097949], [2793998.86604457, 336811.546542464], [2793910.2715925, 336952.104793435], [2793833.83838893, 337074.482068228], [2793789.71622394, 337143.071734606], [2793712.53132262, 337269.248163929], [2793682.91506027, 337316.493506522], [2793675.14508326, 337328.013853827], [2793663.93042073, 337341.983185476], [2793652.71639214, 337353.322106472], [2793652.25623012, 337353.782268495], [2793633.28934057, 337370.064200683], [2793597.14741057, 337399.10539945], [2793588.39283385, 337407.958276045], [2793579.76537347, 337419.215575832], [2793562.50361221, 337444.698088895], [2793527.13601331, 337502.034377124], [2793523.79134175, 337506.303072934], [2793523.33117973, 337506.763234957], [2793519.75079381, 337510.2745172], [2793514.60059485, 337513.795149675], [2793514.02075687, 337514.090591881], [2793509.90563726, 337515.916025758], [2793503.67069607, 337517.520546664], [2793503.02794072, 337517.62234911], [2793495.20539438, 337518.227543182], [2793485.23964322, 337517.884159214], [2793471.28543083, 337516.569018905], [2793456.5398361, 337514.460565929], [2793455.89708075, 337514.358763483], [2793436.92361815, 337510.828358678], [2793417.06337547, 337506.69994132], [2793402.82814201, 337503.142828504], [2793390.29372775, 337498.906964192], [2793378.81711112, 337493.758949417], [2793378.23727315, 337493.463507211], [2793352.3473403, 337479.020692614], [2793325.22302875, 337462.709331566], [2793316.11455011, 337459.555378039], [2793308.77145153, 337458.533765425], [2793299.4834787, 337458.840520883], [2793289.11093218, 337460.566610771], [2793243.03336437, 337471.823525195], [2793227.93667118, 337475.97930775], [2793216.13681408, 337479.755603094], [2793203.52382194, 337484.641444305], [2793192.42135864, 337489.666084009], [2793181.31884013, 337495.714681756], [2793168.7840966, 337504.323127534], [2793156.50336154, 337514.540573331], [2793143.31558904, 337528.514882993], [2793131.31795361, 337543.59485787], [2793114.40314654, 337568.438783307], [2793032.94348996, 337692.221145819], [2792996.56769702, 337746.44114924], [2792974.89275643, 337778.253726275], [2792966.337972, 337788.561575134], [2792965.87780997, 337789.021737158], [2792957.79036098, 337796.200885894], [2792948.67253052, 337802.192948986], [2792948.09269254, 337802.488391192], [2792935.15515279, 337808.77016131], [2792925.51329019, 337812.180797671], [2792913.07957064, 337814.9695884], [2792912.43681529, 337815.071390846], [2792900.57993257, 337815.853112847], [2792892.83275434, 337815.256481458], [2792892.18999899, 337815.154679012], [2792881.92542646, 337812.417539558], [2792879.07396295, 337812.213979223], [2792877.44446576, 337812.527352285], [2792875.28386939, 337813.534668077], [2792872.02406522, 337816.762389446], [2792869.8269773, 337821.356047901], [2792867.72701843, 337829.642759777], [2792854.59902072, 337899.35080626], [2792853.10553424, 337914.964950297], [2792853.67869446, 337928.796759329], [2792852.91981357, 337935.644725911], [2792852.81801113, 337936.287481259], [2792850.90024616, 337942.224888858], [2792850.60480396, 337942.804726835], [2792846.8563546, 337950.092424338], [2792765.4140981, 338072.648412956], [2792716.8297161, 338144.412228056], [2792705.15267796, 338161.091925011], [2792687.23681332, 338184.806035897], [2792650.49115596, 338229.005510069], [2792639.17322439, 338241.32408454], [2792638.71306237, 338241.784246564], [2792631.88463137, 338246.711975847], [2792631.30479339, 338247.007418053], [2792624.46709053, 338250.116473424], [2792619.37791386, 338251.146770311], [2792618.73515852, 338251.248572757], [2792611.79001952, 338251.848894545], [2792607.88129727, 338253.114534855], [2792605.06648227, 338255.164408377], [2792602.28803563, 338258.570067106], [2792600.30198763, 338262.371088957], [2792598.62615761, 338267.290680557], [2792591.2573153, 338299.359587685], [2792585.11663759, 338321.451628331], [2792579.64696896, 338336.247184695], [2792572.3257004, 338351.55260003], [2792572.0302582, 338352.132438006], [2792557.61517388, 338376.504437868], [2792536.46513539, 338410.78663982], [2792491.05987886, 338481.891533096], [2792450.92623103, 338547.013611531], [2792432.06039751, 338575.670332066], [2792427.43774345, 338583.82096684], [2792424.73094772, 338590.057060462], [2792422.7781227, 338596.359038178], [2792421.50938216, 338602.52608409], [2792418.31620243, 338632.660369886], [2792418.21439999, 338633.303125234], [2792416.42952282, 338643.637234726], [2792412.86132093, 338653.865448185], [2792412.56587873, 338654.445286161], [2792404.15381485, 338669.960387585], [2792402.87142579, 338674.243725792], [2792402.540771, 338678.682212379], [2792403.67918437, 338684.62781231], [2792406.34981174, 338690.015556856], [2792410.19814338, 338694.891745797], [2792419.20534038, 338703.847890042], [2792419.66550241, 338704.308052065], [2792423.20915372, 338709.052435011], [2792425.19679124, 338712.742527436], [2792425.49223345, 338713.322365412], [2792427.30913776, 338718.325246926], [2792428.20240553, 338723.401750071], [2792428.30420797, 338724.044505419], [2792428.39512579, 338729.335115821], [2792427.68701982, 338734.560788532], [2792427.58521738, 338735.20354388], [2792425.11601452, 338743.569853734], [2792420.50987638, 338753.058275258], [2792420.21443418, 338753.638113235], [2792377.18078296, 338821.083783324], [2792374.02062998, 338827.537213765], [2792372.63384947, 338833.676097404], [2792372.77879117, 338837.728705952], [2792373.80562367, 338841.6986426], [2792375.81671901, 338845.764456138], [2792379.55135845, 338850.486652391], [2792387.83297911, 338857.682651507], [2792408.59343949, 338871.447919159], [2792409.05360151, 338871.908081183], [2792414.73782439, 338877.74085246], [2792416.75974226, 338881.067609059], [2792417.05518447, 338881.647447035], [2792418.63758676, 338885.696404758], [2792420.65959645, 338896.830498676], [2792420.7613989, 338897.473254024], [2792420.53912072, 338910.932195051], [2792415.72855907, 338981.626600385], [2792413.95852739, 339016.617147755], [2792411.65864688, 339044.380439391], [2792411.55684443, 339045.023194739], [2792409.62032987, 339055.187278153], [2792406.01643585, 339065.835295937], [2792401.06272073, 339076.159968504], [2792400.76727852, 339076.73980648], [2792394.84523505, 339085.680715247], [2792388.856545, 339092.494951368], [2792388.39638298, 339092.955113392], [2792382.79517879, 339098.205239012], [2792374.75281018, 339104.266620725], [2792367.96737999, 339108.216057652], [2792367.38754201, 339108.511499857], [2792360.18056519, 339111.673076358], [2792351.31542202, 339114.450213429], [2792342.18446572, 339116.384919013], [2792341.54171037, 339116.486721459], [2792333.86958991, 339117.403031366], [2792320.64034737, 339117.161100684], [2792319.99759202, 339117.059298238], [2792301.78752018, 339113.96021852], [2792241.5834484, 339097.18015838], [2792227.66612896, 339092.759817037], [2792214.7414311, 339087.681255853], [2792201.9516702, 339081.595739449], [2792201.37183222, 339081.300297244], [2792192.35398053, 339076.238960758], [2792079.65440932, 339005.18209796], [2792061.13337245, 338992.002585254], [2792057.20912892, 338988.233987057], [2792056.7489669, 338987.773825034], [2792052.8652857, 338983.10999085], [2792048.98267591, 338975.842643593], [2792048.6872337, 338975.262805617], [2792047.38203538, 338971.188841247], [2792046.4299641, 338965.832429632], [2792046.32816165, 338965.189674284], [2792046.2661665, 338960.066523711], [2792046.94315192, 338954.841336169], [2792047.04495437, 338954.19858082], [2792049.51301552, 338945.915619767], [2792054.21360257, 338936.203315434], [2792054.50904478, 338935.623477457], [2792078.98618772, 338896.999467331], [2792080.25062186, 338893.448979862], [2792080.7643246, 338889.948333437], [2792080.55388497, 338885.95723295], [2792079.61292528, 338882.152012946], [2792077.32963523, 338876.872062369], [2792073.89482217, 338870.87791454], [2792056.34753155, 338843.101251272], [2792015.24143595, 338775.636259824], [2791985.68214642, 338728.125186097], [2791976.78757509, 338715.424660026], [2791971.72211274, 338709.566844075], [2791965.56973378, 338704.270505893], [2791958.83876505, 338700.396942228], [2791953.20566913, 338698.506337809], [2791949.41751345, 338697.852775094], [2791944.32123537, 338697.627069874], [2791938.92981822, 338698.187450096], [2791918.74111918, 338703.201687904], [2791913.96301636, 338705.241881537], [2791909.47105784, 338708.275052692], [2791905.78402011, 338711.944110224], [2791901.22260128, 338718.178724353], [2791852.2059128, 338795.596731342], [2791840.27243974, 338813.143522271], [2791836.89968596, 338819.00463879], [2791831.42588988, 338830.954844481], [2791831.13044767, 338831.534682458], [2791828.74831605, 338835.201083782], [2791828.28815403, 338835.661245806], [2791823.84513241, 338839.273887227], [2791823.26529443, 338839.569329433], [2791820.913716, 338840.577111705], [2791817.30635835, 338841.177994361], [2791816.663603, 338841.279796807], [2791812.91406182, 338840.98325358], [2791812.27130647, 338840.881451134], [2791809.35801389, 338840.035662323], [2791808.77817591, 338839.740220117], [2791802.11689667, 338835.769643851], [2791773.05914965, 338808.163623504], [2791689.20580537, 338725.746137273], [2791651.75380736, 338689.950705851], [2791605.16493296, 338643.578301966], [2791576.41145311, 338616.310626963], [2791575.95129109, 338615.85046494], [2791564.24545677, 338604.067139696], [2791553.06865095, 338591.674462581], [2791546.03540499, 338582.858771454], [2791540.19770398, 338574.391851284], [2791520.66247878, 338540.489002894], [2791484.65951066, 338473.529716376], [2791484.36406846, 338472.9498784], [2791478.3318706, 338460.086401398], [2791473.88946243, 338448.138652035], [2791470.3744812, 338435.89363802], [2791467.59255597, 338421.445681478], [2791467.49075353, 338420.802926129], [2791463.59618651, 338388.765066058], [2791461.88242808, 338369.936696791], [2791459.49021567, 338325.46075541], [2791458.55894065, 338290.099891399], [2791458.67748527, 338267.290176752], [2791460.39389441, 338234.339889403], [2791463.72901009, 338212.772703657], [2791463.83081254, 338212.129948309], [2791469.29693871, 338189.943379225], [2791475.88922421, 338168.722474184], [2791479.79969339, 338158.245827937], [2791484.0362796, 338148.752476032], [2791485.0249164, 338145.144774765], [2791484.98720209, 338141.867746055], [2791483.67148571, 338138.329084286], [2791477.77732384, 338132.940892624], [2791477.31716182, 338132.4807306], [2791477.02171961, 338131.900892624], [2791475.30854547, 338128.522064717], [2791475.20674303, 338127.879309369], [2791474.92705891, 338122.921580814], [2791475.02886136, 338122.278825466], [2791476.4121329, 338114.710133753], [2791488.25708996, 338073.708378919], [2791495.12813784, 338052.350825164], [2791504.96784957, 338024.61946234], [2791519.75720351, 337987.067854903], [2791535.70700968, 337952.803906573], [2791536.00245189, 337952.224068596], [2791543.40128774, 337938.150845153], [2791551.63497487, 337923.834725771], [2791564.44730466, 337904.872003617], [2791598.15974332, 337859.738478182], [2791617.19490429, 337832.50956821], [2791637.52103334, 337800.258238841], [2791655.8725689, 337768.430705142], [2791661.53913617, 337757.621639315], [2791674.2803143, 337728.370891125], [2791689.77010203, 337688.925089191], [2791701.69218589, 337656.937065527], [2791708.1964745, 337643.21716749], [2791708.49191671, 337642.637329514], [2791715.38536048, 337632.30760815], [2791722.18722336, 337624.441357352], [2791722.64738538, 337623.981195329], [2791731.38431232, 337616.500900261], [2791739.50587302, 337611.560409854], [2791740.08571099, 337611.264967648], [2791746.58161069, 337608.403779098], [2791754.67597688, 337605.730039804], [2791762.91176959, 337604.01016856], [2791763.55452494, 337603.908366114], [2791771.01101246, 337603.157510623], [2791779.50289024, 337603.17577523], [2791788.35429913, 337604.06588311], [2791788.99705447, 337604.167685556], [2791796.54894918, 337605.713249688], [2791804.39622657, 337608.214521365], [2791815.62131251, 337613.834479003], [2791816.20115048, 337614.129921209], [2791828.2207707, 337622.86677932], [2791872.78444271, 337663.257144524], [2791896.5321155, 337684.449171417], [2791898.10856686, 337685.423080632], [2791902.04567958, 337686.404878931], [2791906.71719806, 337685.737321219], [2791910.22812769, 337684.321268267], [2791918.3926492, 337679.618186768], [2791918.97248718, 337679.322744562], [2791924.93080832, 337677.687381945], [2791925.57356367, 337677.585579499], [2791932.89289716, 337677.925262387], [2791933.53565251, 337678.027064833], [2791942.5552507, 337680.318654702], [2791969.45980128, 337689.709473485], [2791991.10526719, 337698.868922747], [2791991.68510516, 337699.164364953], [2792012.51132006, 337709.853522718], [2792039.21710285, 337725.567345329], [2792055.25331288, 337734.284536688], [2792063.90411605, 337737.749253943], [2792064.48395402, 337738.044696149], [2792064.94411605, 337738.504858173], [2792065.23955825, 337739.084696149], [2792065.3413607, 337739.727451497], [2792065.23955825, 337740.370206846], [2792064.94411605, 337740.950044822], [2792064.48395402, 337741.410206846], [2792063.90411605, 337741.705649051], [2792063.2613607, 337741.807451497], [2792062.61860535, 337741.705649051], [2792053.82974279, 337738.185637882], [2792053.24990481, 337737.890195677], [2792036.7719162, 337728.932856026], [2792010.06613341, 337713.219033415], [2791989.79575457, 337702.815161254], [2791968.17429059, 337693.665868592], [2791941.26974, 337684.27504981], [2791932.59673344, 337682.071517727], [2791925.8060918, 337681.756370894], [2791920.38588445, 337683.244039022], [2791912.31677897, 337687.892157182], [2791911.736941, 337688.187599388], [2791907.96449075, 337689.709130681], [2791907.3217354, 337689.810933127], [2791901.89659454, 337690.586183111], [2791901.25383919, 337690.484380665], [2791896.65266859, 337689.33698617], [2791896.07283061, 337689.041543964], [2791894.08692885, 337687.814682114], [2791870.33925606, 337666.622655221], [2791825.77558406, 337626.232290017], [2791813.77868575, 337617.511948081], [2791803.11071587, 337612.170916473], [2791795.26343848, 337609.669644796], [2791788.06857503, 337608.197150365], [2791779.50289024, 337607.33577523], [2791771.01101246, 337607.317510623], [2791763.85437928, 337608.038171298], [2791755.96148757, 337609.686434911], [2791747.86712138, 337612.360174206], [2791741.71248561, 337615.07104941], [2791733.82949897, 337619.866410958], [2791725.3323483, 337627.141416763], [2791718.75087118, 337634.7527948], [2791711.92840166, 337644.976162323], [2791705.64858099, 337658.222576223], [2791693.72649714, 337690.210599888], [2791678.23670941, 337729.656401821], [2791665.45360629, 337759.003399925], [2791665.15816408, 337759.583237902], [2791659.2380796, 337770.875891791], [2791640.88654404, 337802.703425491], [2791620.56041499, 337834.95475486], [2791601.52525402, 337862.183664832], [2791567.81281536, 337907.317190267], [2791555.00048557, 337926.279912421], [2791546.76679844, 337940.596031803], [2791539.59076026, 337954.245474857], [2791523.71359862, 337988.3533656], [2791508.92424468, 338025.904973036], [2791499.08453295, 338053.636335861], [2791492.21348507, 338074.993889616], [2791480.368528, 338115.99564445], [2791479.09075472, 338122.987093232], [2791479.33868813, 338127.382003499], [2791480.648035, 338129.964378304], [2791486.67555262, 338135.474478113], [2791487.13571464, 338135.934640136], [2791487.43115685, 338136.514478113], [2791489.04101784, 338140.844251304], [2791489.14282028, 338141.487006652], [2791489.18791244, 338145.405102902], [2791489.08610999, 338146.04785825], [2791487.99267471, 338150.037986728], [2791483.7560885, 338159.531338634], [2791479.84561932, 338170.00798488], [2791473.25333382, 338191.228889921], [2791467.79367432, 338213.389211283], [2791464.55389441, 338234.339889403], [2791462.83748527, 338267.290176752], [2791462.71894065, 338290.099891399], [2791463.65021567, 338325.46075541], [2791466.04242808, 338369.936696791], [2791467.75618651, 338388.765066058], [2791471.61315004, 338420.493588706], [2791474.33087631, 338434.608127324], [2791477.84585754, 338446.853141338], [2791482.2882657, 338458.800890701], [2791488.20908463, 338471.426855536], [2791524.02798947, 338538.043816245], [2791543.56321468, 338571.946664634], [2791549.40091568, 338580.413584804], [2791556.43416164, 338589.229275932], [2791567.61096747, 338601.621953046], [2791578.90889588, 338612.994672102], [2791607.61011961, 338640.21279127], [2791654.19899401, 338686.585195154], [2791691.65099202, 338722.380626576], [2791775.5043363, 338804.798112807], [2791804.56208332, 338832.404133154], [2791810.80764931, 338836.126916003], [2791813.31552739, 338836.855004637], [2791816.6421822, 338837.118102681], [2791819.6282053, 338836.620716597], [2791821.52203516, 338835.809105071], [2791825.50126209, 338832.573577257], [2791827.66376091, 338829.245218551], [2791833.09242862, 338817.393535581], [2791833.38787083, 338816.813697605], [2791836.90692905, 338810.698335621], [2791848.8404021, 338793.151544692], [2791897.85709058, 338715.733537704], [2791902.42454675, 338709.490671654], [2791902.88470877, 338709.030509631], [2791907.02587119, 338704.909541996], [2791911.71060704, 338701.746198975], [2791912.29044501, 338701.45075677], [2791917.45560849, 338699.245292796], [2791937.88660539, 338694.17087582], [2791938.52936074, 338694.069073374], [2791944.32123537, 338693.467069874], [2791949.48840268, 338693.695914653], [2791950.13115803, 338693.797717099], [2791954.49117983, 338694.549942701], [2791960.28372403, 338696.494061853], [2791960.86356201, 338696.789504059], [2791968.01492043, 338700.904995197], [2791974.41083434, 338706.410982925], [2791974.87099636, 338706.871144949], [2791980.15308579, 338712.979473376], [2791989.04765712, 338725.679999447], [2792018.60694665, 338773.191073175], [2792059.71304225, 338840.656064622], [2792077.26033287, 338868.43272789], [2792080.87732296, 338874.744795812], [2792081.17276517, 338875.324633789], [2792083.56932038, 338880.86650225], [2792084.59659698, 338885.020785858], [2792084.69839942, 338885.663541207], [2792084.9243246, 338889.948333437], [2792084.32154381, 338894.056005546], [2792084.21974136, 338894.698760894], [2792082.85019177, 338898.544408941], [2792082.55474956, 338899.124246918], [2792057.93723458, 338937.969758831], [2792053.46941063, 338947.201130463], [2792051.03412795, 338955.374084985], [2792050.4261665, 338960.066523711], [2792050.48725259, 338965.114551326], [2792051.33843048, 338969.903330551], [2792052.62215058, 338973.91025413], [2792056.2307964, 338980.6648042], [2792060.03860246, 338985.237521463], [2792063.5785591, 338988.637074557], [2792082.09959597, 339001.816587264], [2792194.79916718, 339072.873450061], [2792203.58823567, 339077.806380273], [2792216.0269418, 339083.724860746], [2792228.95163966, 339088.803421929], [2792242.86895909, 339093.223763272], [2792303.07303087, 339110.003823413], [2792320.69028125, 339113.002013854], [2792333.86958991, 339113.243031366], [2792341.16975704, 339112.37114523], [2792350.02991132, 339110.493818321], [2792358.8950545, 339107.71668125], [2792365.80871793, 339104.683776274], [2792372.30762353, 339100.901110028], [2792380.34999214, 339094.839728315], [2792385.63486593, 339089.886105786], [2792391.47972435, 339083.235528598], [2792397.33922048, 339074.389051779], [2792402.06004074, 339064.549785241], [2792405.66393476, 339053.901767457], [2792407.51453879, 339044.188598189], [2792409.79852739, 339016.617147755], [2792411.56855907, 338981.626600385], [2792416.37912072, 338910.932195051], [2792416.60015473, 338897.548588411], [2792414.68119165, 338886.981915455], [2792413.20140993, 338883.195537202], [2792411.37231369, 338880.18603911], [2792406.11513182, 338874.79146889], [2792385.38779246, 338861.048162204], [2792376.7985224, 338853.584842846], [2792376.33836037, 338853.124680823], [2792372.42815823, 338848.180497525], [2792372.13271602, 338847.600659549], [2792369.84922856, 338842.984153297], [2792368.73093504, 338838.660610336], [2792368.62913259, 338838.017854988], [2792368.46791792, 338833.510249847], [2792368.56972037, 338832.867494499], [2792370.06423487, 338826.251703068], [2792373.47035698, 338819.295972698], [2792373.76579918, 338818.716134722], [2792416.7905509, 338751.284412612], [2792421.15961942, 338742.284343037], [2792423.60163336, 338734.010156377], [2792424.23512579, 338729.335115821], [2792424.14543074, 338724.1156594], [2792423.35274265, 338719.610757622], [2792421.57078055, 338714.704090151], [2792419.84364302, 338711.497621661], [2792416.30756249, 338706.763374782], [2792407.30235696, 338697.80921072], [2792406.84219493, 338697.349048696], [2792402.96272421, 338692.433403689], [2792402.66728201, 338691.853565713], [2792399.72278926, 338685.913323007], [2792398.47661664, 338679.404927985], [2792398.37481419, 338678.762172637], [2792398.74144826, 338673.840724457], [2792398.8432507, 338673.197969109], [2792400.22077158, 338668.596878849], [2792400.51621379, 338668.017040873], [2792408.93909873, 338652.48198123], [2792412.47312771, 338642.35172403], [2792414.17082654, 338632.522361015], [2792417.38170464, 338602.221054323], [2792417.48350709, 338601.578298975], [2792418.82172759, 338595.073527482], [2792420.77455261, 338588.771549765], [2792423.5903167, 338582.284407695], [2792423.8857589, 338581.704569719], [2792428.69488681, 338573.225145417], [2792447.56072033, 338544.568424881], [2792487.69436817, 338479.446346447], [2792533.0996247, 338408.34145317], [2792554.24966318, 338374.059251218], [2792568.5702127, 338349.847084081], [2792575.69057386, 338334.961673999], [2792581.16024248, 338320.166117635], [2792587.30092019, 338298.074076988], [2792594.6697625, 338266.00516986], [2792596.35968825, 338261.044198605], [2792596.65513046, 338260.464360629], [2792598.92252494, 338256.124880457], [2792601.95233276, 338252.411117763], [2792602.41249479, 338251.950955739], [2792605.7023795, 338249.555115306], [2792606.28221748, 338249.259673101], [2792610.69933485, 338247.829414968], [2792611.3420902, 338247.727612522], [2792618.49102208, 338247.109675347], [2792623.18157984, 338246.160078317], [2792629.5585429, 338243.260518089], [2792636.15694881, 338238.498786143], [2792647.12564527, 338226.560323419], [2792683.87130263, 338182.360849248], [2792701.78716726, 338158.646738362], [2792713.46420541, 338141.967041406], [2792762.04858741, 338070.203226306], [2792843.4908439, 337947.647237688], [2792846.94857596, 337940.924749827], [2792848.81507462, 337935.146062897], [2792849.51869446, 337928.796759329], [2792848.94553424, 337914.964950297], [2792850.45888426, 337899.143136396], [2792850.56068671, 337898.500381047], [2792863.77062332, 337828.357249081], [2792865.87058219, 337820.070537204], [2792868.33281896, 337814.922507093], [2792868.62826117, 337814.342669117], [2792869.08842319, 337813.882507093], [2792872.88660733, 337810.121704461], [2792873.46644531, 337809.826262256], [2792876.15895507, 337808.570957177], [2792878.34850934, 337808.149878004], [2792878.99126469, 337808.048075558], [2792882.2818236, 337808.282982044], [2792882.92457895, 337808.38478449], [2792893.19972187, 337811.124742631], [2792900.57993257, 337811.693112847], [2792912.1693105, 337810.929027385], [2792924.2277795, 337808.224402563], [2792933.86964209, 337804.813766202], [2792946.30835434, 337798.774199759], [2792955.34517433, 337792.835375198], [2792963.13537279, 337785.920092829], [2792971.52724573, 337775.808539625], [2792993.20218632, 337743.995962591], [2793029.57797927, 337689.77595917], [2793111.03763584, 337565.993596657], [2793127.95244291, 337541.14967122], [2793139.95007834, 337526.069696344], [2793153.47745716, 337511.735525776], [2793153.93761918, 337511.275363752], [2793166.33890995, 337500.957616837], [2793178.87365348, 337492.349171059], [2793190.33426293, 337486.105487121], [2793190.9141009, 337485.810044916], [2793202.23831124, 337480.685049197], [2793214.85130339, 337475.799207986], [2793226.65116048, 337472.022912642], [2793241.74785368, 337467.867130087], [2793287.82542149, 337456.610215663], [2793298.8020516, 337454.783600547], [2793299.44480695, 337454.681798101], [2793308.77145153, 337454.373765425], [2793316.69754515, 337455.476487544], [2793317.3403005, 337455.578289991], [2793326.71727631, 337458.825214868], [2793327.29711428, 337459.120657074], [2793354.79252695, 337475.655181917], [2793380.35903389, 337489.917571926], [2793391.57923844, 337494.950569084], [2793404.1136527, 337499.186433396], [2793418.34888617, 337502.743546212], [2793438.20912885, 337506.87196357], [2793456.95289657, 337510.359628895], [2793471.28543083, 337512.409018905], [2793485.23964322, 337513.724159214], [2793495.20539438, 337514.067543182], [2793502.67452874, 337513.489690953], [2793508.62012657, 337511.959630651], [2793512.31470327, 337510.320746216], [2793517.30560716, 337506.909006503], [2793520.45587966, 337503.819536216], [2793523.77050262, 337499.589190474], [2793559.13810152, 337442.252902246], [2793576.39986277, 337416.770389182], [2793585.02732316, 337405.513089395], [2793594.2171848, 337396.220040322], [2793594.67734682, 337395.759878298], [2793630.84415392, 337366.698689986], [2793649.77748103, 337350.445569133], [2793660.56491003, 337339.537998826], [2793671.77957256, 337325.568667177], [2793679.54954957, 337314.048319872], [2793709.16581192, 337266.80297728], [2793786.35071324, 337140.626547956], [2793830.47287823, 337072.036881578], [2793906.90608181, 336949.659606785], [2793995.50053387, 336809.101355814], [2794012.43039609, 336783.1409113], [2794075.95732623, 336681.341826341], [2794081.19331383, 336670.968034952], [2794086.57358955, 336656.033588907], [2794099.70926256, 336610.578469798], [2794111.75917261, 336565.698634822], [2794116.51774753, 336551.344064109], [2794119.78436758, 336543.296020407], [2794124.07376896, 336534.673022158], [2794124.36921117, 336534.093184181], [2794145.29130386, 336498.666549951], [2794262.25735435, 336312.731706058], [2794411.30245991, 336072.36928991], [2794457.70165523, 335999.196739547], [2794527.59261689, 335886.88158287], [2794612.90988795, 335751.080422549], [2794625.1041757, 335730.526381872], [2794633.59755389, 335711.396281933], [2794633.89299609, 335710.816443956], [2794636.28556395, 335706.368715025], [2794651.0907817, 335688.247557492], [2794671.21226461, 335658.187127772], [2794854.27238953, 335364.862279285], [2794922.23398308, 335257.258479986], [2794968.04256122, 335182.404801988], [2795080.15041112, 335005.302193144], [2795132.47509754, 334921.128159506], [2795142.50719336, 334905.888616876], [2795158.25425457, 334883.946510363], [2795174.39480257, 334857.365391485], [2795183.75183005, 334840.561891407], [2795186.47906204, 334834.535674652], [2795188.13918077, 334829.283295837], [2795188.80989956, 334824.93927199], [2795188.85653071, 334821.123751761], [2795187.04055418, 334810.000695225], [2795186.93875174, 334809.357939876], [2795186.68515654, 334799.925070394], [2795186.78695899, 334799.282315046], [2795188.31705003, 334789.927659694], [2795191.23114918, 334783.079077442], [2795191.52659138, 334782.499239465], [2795195.96727796, 334776.733079688], [2795196.42743998, 334776.272917665], [2795206.63608519, 334767.381304878], [2795211.9641175, 334762.014900113], [2795217.39555608, 334755.673587206], [2795222.40606115, 334748.515213193], [2795441.41241272, 334398.824450927], [2795448.24732137, 334386.428033044], [2795454.94677571, 334370.640250596], [2795460.81282374, 334359.044258672], [2795461.10826594, 334358.464420696], [2795468.36742716, 334346.185421936], [2795484.39762819, 334321.198744515], [2795509.57350514, 334278.164203851], [2795518.9590541, 334265.575927757], [2795526.32250689, 334257.355809058], [2795526.78266891, 334256.895647034], [2795535.49688186, 334248.916738279], [2795552.12088679, 334235.773616903], [2795559.71788344, 334228.481651449], [2795591.43372097, 334187.278374896], [2795603.09124381, 334170.10157211], [2795714.99436058, 333993.347938064], [2795720.16131553, 333986.024800317], [2795730.26935312, 333973.173099828], [2795733.28086194, 333965.940058606], [2795734.01681153, 333959.301411651], [2795733.18767119, 333952.900370103], [2795725.73742218, 333913.225824117], [2795725.63561974, 333912.583068769], [2795724.69525494, 333904.00936056], [2795724.58628529, 333897.824134068], [2795725.30186207, 333889.718026765], [2795725.40366452, 333889.075271417], [2795726.87932898, 333881.678590621], [2795729.08965667, 333874.626378086], [2795732.25562452, 333867.335096493], [2795732.55106672, 333866.755258516], [2795743.11868547, 333848.249938555], [2795868.25534784, 333649.195571129], [2795940.7093882, 333532.877457771], [2795953.55041302, 333512.830745005], [2795953.27616111, 333512.292495322], [2795953.17573555, 333511.75860136], [2795953.17435866, 333511.649739973], [2795953.27616111, 333511.006984625], [2795953.57160332, 333510.427146649], [2795995.90702778, 333443.543719448], [2796003.08937586, 333429.934049807], [2796004.58455681, 333424.325201857], [2796004.4584191, 333418.892871262], [2796002.66370712, 333413.698627175], [2795998.35270397, 333407.378239388], [2795986.06650598, 333393.069210256], [2795962.65197068, 333367.849872298], [2795881.29311848, 333282.848438287], [2795593.21414662, 332985.658418362], [2795548.35700656, 332940.165986038], [2795443.21190627, 332830.437188422], [2795327.3966012, 332710.868880331], [2795319.7902966, 332703.558150796], [2795314.09202361, 332699.066354286], [2795309.29733327, 332696.131360575], [2795303.60227121, 332694.037650296], [2795299.09266945, 332693.55543236], [2795294.17135098, 332694.363594061], [2795290.60537878, 332695.956368136], [2795287.3581859, 332698.366540266], [2795285.05930494, 332700.785613839], [2795279.14627357, 332708.631213638], [2795278.68611154, 332709.091375662], [2795272.49432406, 332714.666987967], [2795271.91448608, 332714.962430173], [2795265.28879938, 332718.182521836], [2795264.64604403, 332718.284324282], [2795258.11356408, 332718.986181212], [2795257.47080874, 332718.884378766], [2795253.20292726, 332718.132448903], [2795248.18367164, 332715.97200305], [2795247.60383366, 332715.676560845], [2795218.23546561, 332696.676948258], [2795211.24924058, 332692.836751704], [2795207.22531306, 332691.176634063], [2795200.75569508, 332689.459672009], [2795193.67985068, 332688.91984887], [2795187.43834586, 332689.69294779], [2795181.30232463, 332691.760313378], [2795174.96388197, 332695.811339659], [2795171.59133062, 332699.269201259], [2795168.24545273, 332703.592677958], [2795133.93063574, 332758.628296957], [2795111.79426575, 332791.793845466], [2795108.36375165, 332795.529022355], [2795107.90358963, 332795.989184379], [2795103.77181116, 332799.100188003], [2795103.19197318, 332799.395630208], [2795099.32381681, 332801.16607186], [2795098.68106146, 332801.267874306], [2795093.93295762, 332801.992867244], [2795093.29020227, 332801.891064798], [2795087.94813834, 332800.92943183], [2795082.32134331, 332798.089567222], [2795081.74150533, 332797.794125016], [2794993.88304749, 332743.401104524], [2794920.94242097, 332697.053645094], [2794906.29322367, 332688.398567033], [2794898.41732099, 332684.527262045], [2794887.57073719, 332680.783551667], [2794878.29128793, 332679.306954974], [2794868.5360246, 332679.522573719], [2794850.65405817, 332682.295167576], [2794842.49254294, 332682.865060669], [2794834.77608124, 332682.294059079], [2794834.13332589, 332682.192256633], [2794819.97749141, 332679.732793494], [2794810.62098253, 332679.673036292], [2794806.56149386, 332680.300865669], [2794800.89443956, 332682.016756747], [2794777.62017037, 332692.809955792], [2794746.96423269, 332703.371810167], [2794738.59454428, 332706.959530047], [2794731.00555978, 332711.602761511], [2794722.68400435, 332718.323761961], [2794717.40198205, 332723.701009135], [2794710.86864956, 332731.902960824], [2794680.88147085, 332777.955765494], [2794635.75547067, 332848.727487668], [2794567.956312, 332956.465177613], [2794541.66392418, 332997.359306877], [2794531.57788798, 333014.277001998], [2794520.9285842, 333034.377214561], [2794506.99274502, 333058.943006611], [2794438.674953, 333168.998375706], [2794387.35726315, 333243.025703299], [2794326.45502071, 333338.204052148], [2794312.55471074, 333357.509162589], [2794292.15117157, 333382.611464247], [2794285.00870349, 333392.904930021], [2794276.68051107, 333408.263662477], [2794263.11883028, 333437.162129134], [2794255.32360495, 333455.395172022], [2794255.02816275, 333455.975009999], [2794248.97750574, 333467.570483738], [2794243.95634272, 333475.539828365], [2794239.10560229, 333482.084763604], [2794227.03915791, 333497.411224318], [2794217.82784805, 333508.211241414], [2794217.36768603, 333508.671403437], [2794209.21072302, 333516.434935464], [2794202.35662676, 333520.771131205], [2794201.77678878, 333521.066573411], [2794197.91253184, 333522.530134784], [2794193.03809506, 333523.533960879], [2794192.39533972, 333523.635763325], [2794184.45772869, 333523.481613668], [2794183.81497334, 333523.379811222], [2794179.39965284, 333522.094368246], [2794173.2506046, 333519.192816286], [2794172.67076663, 333518.89737408], [2794129.87668274, 333493.100008633], [2794121.55802448, 333488.714584367], [2794115.71206359, 333486.273664772], [2794108.04666089, 333484.42487557], [2794100.3336161, 333484.276867822], [2794094.63789445, 333485.382760476], [2794087.92372833, 333488.203951505], [2794084.31920906, 333490.494003622], [2794079.72925097, 333494.488327237], [2794073.08418592, 333502.651029657], [2794069.45485305, 333509.248501282], [2794061.54741955, 333525.908567587], [2794061.25197734, 333526.488405564], [2794052.97509031, 333541.385249165], [2794032.16380963, 333574.626431804], [2794025.65627264, 333583.389648567], [2794021.35593492, 333587.702970586], [2794020.8957729, 333588.16313261], [2794015.27157657, 333592.570983512], [2793990.06816387, 333607.707935669], [2793975.41121273, 333618.497632293], [2793964.90156797, 333628.015800611], [2793954.72927021, 333638.206303965], [2793947.64342094, 333646.346937083], [2793940.83699948, 333654.246644109], [2793940.90736993, 333654.690945594], [2793940.80556748, 333655.333700943], [2793940.51012527, 333655.913538919], [2793940.41647057, 333656.052421851], [2793939.95630855, 333656.512583875], [2793939.37647057, 333656.80802608], [2793937.3458284, 333657.339360524], [2793920.47157655, 333681.385158277], [2793911.03251999, 333695.765234995], [2793886.39272756, 333737.690475613], [2793847.78062294, 333797.187365242], [2793750.01727105, 333955.108939656], [2793737.1789806, 333973.16919597], [2793723.20972286, 333990.68366296], [2793713.66067161, 334001.509483895], [2793692.87155676, 334023.026573617], [2793683.99964657, 334033.831534964], [2793677.53618349, 334043.995094951], [2793667.92199854, 334062.570611771], [2793654.17105747, 334084.874401938], [2793635.0260819, 334117.857703772], [2793608.54952629, 334159.091004657], [2793597.31525226, 334174.288931318], [2793578.29016573, 334195.07248767], [2793572.19826989, 334202.498418876], [2793553.20494394, 334230.726650453], [2793520.41062326, 334285.287427704], [2793419.70062756, 334445.614078317], [2793399.59734521, 334476.599935498], [2793360.17207294, 334534.943448355], [2793343.8886853, 334560.491537761], [2793317.7147799, 334599.743464403], [2793301.47680027, 334626.66244502], [2793227.97460994, 334744.032383], [2793140.80636748, 334884.492790762], [2793100.71739231, 334947.000473377], [2793032.13113969, 335057.744865101], [2793019.64860083, 335077.01536785], [2793014.11112617, 335084.53236559], [2793009.05728898, 335090.179287175], [2793008.59712696, 335090.639449198], [2793002.69111198, 335095.493153175], [2792996.21221594, 335099.360580234], [2792995.63237796, 335099.65602244], [2792986.95062744, 335102.572715357], [2792986.30787209, 335102.674517803], [2792967.18396595, 335105.05192987], [2792955.4741986, 335107.394828035], [2792945.8872539, 335111.136933667], [2792937.17197512, 335116.188711815], [2792928.30354689, 335123.06792176], [2792919.89820021, 335131.688024999], [2792911.95364249, 335142.198308317], [2792906.25299134, 335152.406944099], [2792903.64069162, 335158.697731033], [2792901.46215861, 335165.750990179], [2792899.59687146, 335174.342830748], [2792898.32981987, 335183.064049235], [2792890.36414947, 335301.462852268], [2792881.17224125, 335386.709635219], [2792878.47722646, 335405.903249286], [2792878.37542401, 335406.546004634], [2792878.07998181, 335407.125842611], [2792877.61981978, 335407.586004634], [2792877.03998181, 335407.88144684], [2792876.39722646, 335407.983249286], [2792875.75447111, 335407.88144684], [2792875.17463313, 335407.586004634], [2792874.71447111, 335407.125842611], [2792874.41902891, 335406.546004634], [2792874.31722646, 335405.903249286], [2792877.01224125, 335386.709635219], [2792886.20414947, 335301.462852268], [2792894.16981987, 335183.064049235], [2792895.51321869, 335173.817326614], [2792895.61502113, 335173.174571265], [2792897.5057635, 335164.465479482], [2792899.68429651, 335157.412220337], [2792902.37882538, 335150.923413995], [2792902.67426758, 335150.343576019], [2792908.58813179, 335139.753121667], [2792916.53268952, 335129.242838349], [2792925.35114207, 335120.199074384], [2792925.8113041, 335119.738912361], [2792934.72678847, 335112.823201118], [2792943.80713533, 335107.559812651], [2792944.38697331, 335107.264370446], [2792954.1886879, 335103.438432927], [2792966.18747633, 335101.03770723], [2792966.83023167, 335100.935904783], [2792985.76858236, 335098.581560274], [2792994.15267391, 335095.764867906], [2793000.24592533, 335092.127642478], [2793005.96921223, 335087.424108795], [2793010.74561547, 335082.087178941], [2793016.28309014, 335074.5701812], [2793028.76562899, 335055.299678452], [2793097.35188162, 334944.555286728], [2793137.44085678, 334882.047604112], [2793224.60909924, 334741.587196351], [2793298.11128958, 334624.21725837], [2793314.34926921, 334597.298277753], [2793340.52317461, 334558.046351111], [2793356.80656224, 334532.498261706], [2793396.23183451, 334474.154748849], [2793416.33511686, 334443.168891667], [2793517.04511257, 334282.842241055], [2793549.83943325, 334228.281463804], [2793568.83275919, 334200.053232226], [2793574.92465504, 334192.62730102], [2793593.94974156, 334171.843744668], [2793605.1840156, 334156.645818008], [2793631.6605712, 334115.412517122], [2793650.80554677, 334082.429215289], [2793664.55648784, 334060.125425122], [2793674.1706728, 334041.549908301], [2793680.63413587, 334031.386348314], [2793689.50604607, 334020.581386967], [2793710.29516091, 333999.064297245], [2793719.84421216, 333988.238476311], [2793733.8134699, 333970.72400932], [2793746.65176036, 333952.663753006], [2793844.41511224, 333794.742178592], [2793883.02721686, 333735.245288963], [2793907.66700929, 333693.320048346], [2793917.10606585, 333678.939971627], [2793934.39591344, 333654.301950224], [2793934.85607547, 333653.8417882], [2793935.43591344, 333653.546345994], [2793936.01056486, 333653.395983663], [2793936.094946, 333652.86322213], [2793936.3903882, 333652.283384154], [2793936.85055023, 333651.82322213], [2793937.4303882, 333651.527779925], [2793937.75104947, 333651.476992169], [2793944.27791025, 333643.901750434], [2793951.36375952, 333635.761117316], [2793961.98765207, 333625.118210938], [2793962.44781409, 333624.658048915], [2793972.96602609, 333615.132121596], [2793987.62297722, 333604.342424972], [2794012.82638992, 333589.205472815], [2794018.44425034, 333584.802587556], [2794022.29076195, 333580.944461918], [2794028.79829893, 333572.181245154], [2794049.60957962, 333538.940062516], [2794057.74765571, 333524.293052542], [2794065.6464422, 333507.651204525], [2794065.9418844, 333507.071366549], [2794069.71867523, 333500.205843007], [2794076.53046931, 333491.838333028], [2794076.99063134, 333491.378171005], [2794081.87402241, 333487.128492925], [2794085.71932582, 333484.685463896], [2794086.2991638, 333484.39002169], [2794093.35238375, 333481.426365368], [2794099.58307507, 333480.216601939], [2794100.22583042, 333480.114799493], [2794108.28639964, 333480.269475984], [2794108.92915499, 333480.37127843], [2794116.99757429, 333482.317269664], [2794122.93689874, 333484.797172237], [2794123.51673672, 333485.092614443], [2794132.32186939, 333489.734497936], [2794174.94922473, 333515.431355164], [2794180.68516353, 333518.137973138], [2794184.77175381, 333519.327712086], [2794192.25971243, 333519.473129421], [2794196.62702114, 333518.573739676], [2794200.21011109, 333517.216668414], [2794206.76553637, 333513.069424767], [2794214.56289997, 333505.648147762], [2794223.67364721, 333494.966037668], [2794235.74009159, 333479.639576954], [2794240.59083202, 333473.094641716], [2794245.61199504, 333465.125297088], [2794251.39951633, 333454.034096409], [2794259.16243517, 333435.876618437], [2794272.84614955, 333406.71811148], [2794273.14159176, 333406.138273503], [2794281.64319279, 333390.459743372], [2794288.78566087, 333380.166277597], [2794309.18920004, 333355.063975939], [2794323.08951001, 333335.758865499], [2794383.99175245, 333240.580516649], [2794435.3094423, 333166.553189056], [2794503.62723432, 333056.497819961], [2794517.56307351, 333031.932027912], [2794528.21237728, 333011.831815348], [2794538.29841349, 332994.914120227], [2794564.59080131, 332954.019990963], [2794632.38995997, 332846.282301018], [2794677.51596016, 332775.510578845], [2794707.50313886, 332729.457774174], [2794714.03647136, 332721.255822486], [2794719.73922046, 332715.4502636], [2794720.19938248, 332714.990101576], [2794728.56037313, 332708.237250815], [2794736.40533798, 332703.437400765], [2794736.98517596, 332703.141958559], [2794745.67872199, 332699.415415059], [2794776.33465968, 332688.853560685], [2794799.60892886, 332678.06036164], [2794805.2921563, 332676.3395736], [2794805.93491165, 332676.237771153], [2794810.62098253, 332675.513036292], [2794820.03647466, 332675.573170202], [2794820.67923001, 332675.674972648], [2794834.87504603, 332678.141382261], [2794842.49254294, 332678.705060669], [2794850.65405817, 332678.135167576], [2794868.5360246, 332675.362573718], [2794878.2939161, 332675.146896884], [2794878.93667145, 332675.24869933], [2794888.85624789, 332676.82715656], [2794899.70283168, 332680.570866938], [2794908.05352256, 332684.675548337], [2794908.63336053, 332684.970990543], [2794923.38760761, 332693.688134398], [2794996.32823414, 332740.035593827], [2795084.16225201, 332794.413483577], [2795089.23364903, 332796.973036722], [2795093.97473942, 332797.826487537], [2795098.05030413, 332797.204185302], [2795101.42841114, 332795.658037531], [2795105.33672634, 332792.715289548], [2795108.42875506, 332789.348658816], [2795130.56512504, 332756.183110307], [2795164.87994203, 332701.147491308], [2795168.22581992, 332696.824014609], [2795172.02839151, 332692.925255204], [2795172.48855354, 332692.46509318], [2795179.1883175, 332688.183139185], [2795179.76815547, 332687.887696979], [2795186.25697588, 332685.7014653], [2795186.89973122, 332685.599662854], [2795193.67985068, 332684.75984887], [2795201.11940914, 332685.327420112], [2795201.76216448, 332685.429222558], [2795208.51082376, 332687.220238955], [2795212.70455789, 332688.950412271], [2795213.28439587, 332689.245854476], [2795220.68065225, 332693.311437562], [2795249.8371978, 332712.174013401], [2795254.48843795, 332714.176053796], [2795258.15390043, 332714.82184743], [2795264.08978511, 332714.184089361], [2795270.08204642, 332711.271843196], [2795275.88817065, 332706.043514906], [2795281.69379425, 332698.340427189], [2795284.37524119, 332695.518785894], [2795284.83540321, 332695.058623871], [2795288.28351946, 332692.499319888], [2795288.86335743, 332692.203877682], [2795292.88584029, 332690.407198954], [2795298.43608922, 332689.495756492], [2795299.07884457, 332689.393954046], [2795304.11817142, 332689.932816217], [2795304.76092677, 332690.034618663], [2795310.82618504, 332692.264426423], [2795311.40602301, 332692.559868629], [2795316.53721026, 332695.700843589], [2795322.23548325, 332700.192640099], [2795330.05103125, 332707.704482], [2795330.51119328, 332708.164644023], [2795446.57741696, 332827.992001773], [2795551.72251726, 332937.720799388], [2795596.57965732, 332983.213231713], [2795884.65862918, 333280.403251638], [2795966.01748137, 333365.404685648], [2795989.43201668, 333390.624023606], [2796001.71821466, 333404.933052738], [2796006.22194337, 333411.535996635], [2796006.51738558, 333412.115834611], [2796008.50795103, 333417.87691658], [2796008.60975348, 333418.519671928], [2796008.75012873, 333424.565165524]]
the second piece
[[2792878.47722646, 335405.903249286], [2792878.37542401, 335405.260493938], [2792878.07998181, 335404.680655961], [2792877.61981978, 335404.220493938], [2792877.03998181, 335403.925051732], [2792876.39722646, 335403.823249286], [2792875.75447111, 335403.925051732], [2792875.17463313, 335404.220493938], [2792874.71447111, 335404.680655961], [2792874.41902891, 335405.260493938], [2792871.41200058, 335422.239829784], [2792869.28439753, 335430.217646554], [2792864.99468962, 335441.36097348], [2792838.12109105, 335500.392963363], [2792760.22658816, 335663.391853845], [2792742.74289642, 335701.857277801], [2792735.69637894, 335715.895835532], [2792730.06985878, 335725.160472696], [2792724.78056211, 335731.410727888], [2792717.02386841, 335737.21500365], [2792698.37663892, 335747.259319247], [2792691.30302954, 335752.043824152], [2792690.84286751, 335752.503986175], [2792684.26964756, 335759.140360324], [2792677.93222091, 335769.166910332], [2792669.92977013, 335784.49099117], [2792669.63432793, 335785.070829146], [2792650.30847308, 335825.753024319], [2792624.04956329, 335883.043870486], [2792597.25212429, 335933.786661783], [2792596.95668208, 335934.36649976], [2792587.14374945, 335954.398165545], [2792530.484703, 336084.635561813], [2792523.48454772, 336099.881339589], [2792518.97694219, 336108.372710461], [2792510.686051, 336122.210559298], [2792488.00775268, 336157.703524369], [2792459.74098708, 336199.957052399], [2792442.22436671, 336231.118853959], [2792408.24008865, 336295.666938257], [2792407.94464644, 336296.246776234], [2792391.26493721, 336329.489437132], [2792378.9298036, 336357.159587114], [2792366.0648376, 336390.449519037], [2792352.13130993, 336433.240863633], [2792343.20678243, 336466.35486873], [2792340.15577652, 336482.04683144], [2792340.05397407, 336482.689586788], [2792339.5284275, 336490.51994629], [2792339.86292329, 336498.499740057], [2792339.96472573, 336499.142495405], [2792341.09020471, 336505.286017758], [2792344.50222229, 336515.821863252], [2792357.88051409, 336552.059720046], [2792369.89112043, 336581.759139204], [2792370.18656264, 336582.33897718], [2792372.74932826, 336586.792045428], [2792375.59802365, 336590.409280063], [2792376.05818567, 336590.869442086], [2792389.47642871, 336604.14009715], [2792392.06655519, 336607.708203881], [2792394.17978658, 336611.638163658], [2792395.5420903, 336615.52842842], [2792396.21545492, 336619.890458086], [2792396.02742611, 336623.686945111], [2792394.89534326, 336627.992915675], [2792393.19952212, 336631.249156214], [2792391.06395881, 336633.891704582], [2792385.85192201, 336637.77355853], [2792382.62754305, 336639.056518086], [2792380.06706632, 336639.56544026], [2792376.46124411, 336639.656378421], [2792373.63918457, 336639.252017165], [2792368.76067918, 336637.699427341], [2792365.17999115, 336635.87247997], [2792346.37241999, 336621.092398382], [2792337.55118394, 336615.136064558], [2792329.8192972, 336610.705207629], [2792329.23945923, 336610.409765424], [2792323.57349264, 336608.186201422], [2792318.7853915, 336607.204461498], [2792318.14263615, 336607.102659052], [2792309.86288317, 336607.310989431], [2792309.22012782, 336607.412791878], [2792303.29054227, 336609.131608084], [2792302.71070429, 336609.42705029], [2792297.38418835, 336612.301758021], [2792284.21818005, 336622.134671618], [2792274.05441188, 336630.576149772], [2792265.12279202, 336638.808839317], [2792264.66262999, 336639.269001341], [2792260.54506007, 336643.948746344], [2792257.44036825, 336648.780771501], [2792257.14492604, 336649.360609478], [2792255.23875141, 336654.29173925], [2792255.13694896, 336654.934494598], [2792254.12546793, 336662.283471236], [2792254.96304852, 336676.958522863], [2792254.33713223, 336690.636566771], [2792252.51311525, 336704.304061043], [2792246.9649564, 336735.60826614], [2792246.86315396, 336736.251021488], [2792244.94618332, 336757.413725799], [2792244.1151427, 336795.635324464], [2792244.73887205, 336802.611087329], [2792244.8406745, 336803.253842677], [2792246.79776353, 336809.435612216], [2792247.09320574, 336810.015450192], [2792250.99189661, 336815.855898732], [2792251.45205864, 336816.316060755], [2792258.82415884, 336822.477484854], [2792317.50930018, 336860.409052563], [2792369.15721129, 336892.432879193], [2792379.14143677, 336898.963224877], [2792383.55926884, 336902.437899082], [2792387.05144771, 336906.047682156], [2792389.08620163, 336908.867175475], [2792390.85721432, 336912.431032364], [2792391.84188017, 336916.401199312], [2792391.84981264, 336920.416972572], [2792391.0066167, 336924.30078234], [2792387.6509938, 336931.429777123], [2792370.20283495, 336961.194112139], [2792348.84064911, 336994.941345878], [2792325.76198147, 337033.341007346], [2792304.54955465, 337067.454992339], [2792288.42452599, 337090.489861178], [2792284.23662263, 337094.891108618], [2792278.85805635, 337098.664668595], [2792275.89645402, 337099.870076474], [2792273.10321901, 337100.366532599], [2792267.9097566, 337099.801319906], [2792263.33219622, 337097.879936084], [2792246.96917137, 337089.13189796], [2792218.79570766, 337072.72826939], [2792189.41699329, 337054.210315258], [2792154.55782253, 337033.331064168], [2792110.00081629, 337005.226552667], [2792101.23066, 337000.166729447], [2792100.65082202, 336999.871287242], [2792094.83386439, 336997.395159069], [2792088.33175162, 336995.609017885], [2792087.68899627, 336995.507215439], [2792081.54366939, 336994.817570496], [2792074.67734117, 336995.126805491], [2792074.03458582, 336995.228607937], [2792065.67371994, 336997.114817912], [2792058.92562543, 337000.391754114], [2792058.34578746, 337000.687196319], [2792052.37758504, 337005.70956685], [2792051.91742301, 337006.169728874], [2792046.63835353, 337012.655330643], [2792030.44188135, 337036.55826752], [2791988.38111544, 337102.718710436], [2791977.20032719, 337121.504305688], [2791976.90488499, 337122.084143665], [2791970.34796234, 337135.160086643], [2791965.44223198, 337146.436235955], [2791956.55219056, 337169.195112972], [2791949.60795483, 337188.871077975], [2791946.25726303, 337201.370017874], [2791946.15546058, 337202.012773223], [2791945.24906686, 337210.873553225], [2791946.1054303, 337218.972652562], [2791946.20723275, 337219.61540791], [2791948.61889251, 337226.333693702], [2791948.91433472, 337226.913531679], [2791953.02135474, 337233.315676378], [2791956.7892479, 337237.335867594], [2791957.24940992, 337237.796029617], [2791961.45278514, 337241.344874504], [2791998.74546893, 337267.15088741], [2792114.46377479, 337339.827341158], [2792135.19719747, 337353.146615009], [2792141.44974029, 337357.72756697], [2792144.61211128, 337360.750125136], [2792147.24589271, 337364.115402442], [2792149.06667945, 337367.597883057], [2792149.91015867, 337370.451261502], [2792150.06618474, 337376.15220876], [2792147.26527798, 337387.303729045], [2792147.16347553, 337387.946484393], [2792146.76746937, 337395.273720174], [2792146.86927181, 337395.916475522], [2792148.3769485, 337403.659532979], [2792149.81538659, 337406.839538405], [2792150.1108288, 337407.419376381], [2792152.22669078, 337410.551097371], [2792152.6868528, 337411.011259395], [2792156.09369636, 337414.383175772], [2792159.81465125, 337417.05861286], [2792217.02951797, 337452.00281614], [2792223.02661378, 337457.456701343], [2792224.95006347, 337460.450665317], [2792225.83417337, 337462.804911733], [2792226.20558696, 337465.497431655], [2792225.85474243, 337469.352864937], [2792222.3214736, 337481.656078345], [2792217.66828863, 337492.981367339], [2792210.46260184, 337506.622839845], [2792180.16923029, 337556.580347139], [2792150.8406642, 337603.051413261], [2792122.72475981, 337645.871727094], [2792117.88538614, 337654.237858339], [2792117.58994393, 337654.817696315], [2792115.52828796, 337659.998007728], [2792114.51847456, 337664.576328249], [2792114.41667212, 337665.219083597], [2792114.58003374, 337679.85884682], [2792114.08579848, 337684.204652849], [2792111.53584444, 337692.695755778], [2792107.84285104, 337700.175305057], [2792094.86654737, 337721.159873508], [2792088.91103095, 337728.700275498], [2792085.68415558, 337731.835500847], [2792081.00227247, 337735.216588423], [2792075.5533489, 337737.551498413], [2792069.56109483, 337738.395031712], [2792063.2613607, 337737.647451497], [2792062.61860535, 337737.749253943], [2792062.03876737, 337738.044696149], [2792061.57860535, 337738.504858173], [2792061.28316314, 337739.084696149], [2792061.1813607, 337739.727451497], [2792061.28316314, 337740.370206846], [2792061.57860535, 337740.950044822], [2792062.03876737, 337741.410206846], [2792062.61860535, 337741.705649051], [2792063.2613607, 337741.807451497], [2792069.56109483, 337742.555031712], [2792076.15675809, 337741.62655613], [2792076.79951344, 337741.524753684], [2792082.70764899, 337738.993067466], [2792083.28748696, 337738.69762526], [2792088.12934223, 337735.201011544], [2792091.77200421, 337731.661808794], [2792092.23216623, 337731.20164677], [2792098.23205806, 337723.605060157], [2792111.25376096, 337702.547074563], [2792111.54920317, 337701.967236587], [2792115.49223955, 337693.981266474], [2792118.08839322, 337685.336323173], [2792118.19019567, 337684.693567824], [2792118.74003374, 337679.85884682], [2792118.57859672, 337665.391558314], [2792119.48468307, 337661.283518425], [2792121.4582084, 337656.324652377], [2792126.09027051, 337648.316913744], [2792154.2061749, 337605.496599911], [2792183.53474098, 337559.025533788], [2792213.82811254, 337509.068026494], [2792221.29129162, 337494.939081498], [2792221.58673383, 337494.359243522], [2792226.2778687, 337482.941589042], [2792229.87453952, 337470.417603264], [2792229.97634197, 337469.774847916], [2792230.36558696, 337465.497431655], [2792229.91313814, 337462.217456252], [2792229.8113357, 337461.574700904], [2792228.79801936, 337458.876397918], [2792228.50257715, 337458.296559942], [2792226.32771633, 337454.91125958], [2792225.86755431, 337454.451097556], [2792219.47470462, 337448.637305444], [2792162.2598379, 337413.693102163], [2792158.53888301, 337411.017665075], [2792155.58258093, 337408.091671188], [2792153.5766742, 337405.122696719], [2792152.33334361, 337402.374022283], [2792150.93254256, 337395.179851847], [2792151.30712457, 337388.249023505], [2792154.13024213, 337377.009073236], [2792154.23204457, 337376.366317887], [2792154.06115955, 337370.122447479], [2792153.9593571, 337369.479692131], [2792153.0130299, 337366.278392613], [2792152.71758769, 337365.698554637], [2792150.6114034, 337361.670215792], [2792147.91443027, 337358.224196172], [2792147.45426825, 337357.764034148], [2792143.89492694, 337354.362056274], [2792137.64238412, 337349.781104313], [2792116.90896144, 337336.461830461], [2792001.19065558, 337263.785376713], [2791963.89797179, 337237.979363808], [2791959.83297037, 337234.547345786], [2791956.38686544, 337230.870489729], [2791952.47805742, 337224.777323781], [2791950.21159788, 337218.463529804], [2791949.40906686, 337210.873553225], [2791950.2719569, 337202.438059235], [2791953.56434994, 337190.156588672], [2791960.50858567, 337170.480623669], [2791969.39862709, 337147.721746652], [2791974.30435745, 337136.445597339], [2791980.59557381, 337123.899531012], [2791991.74662614, 337105.163897086], [2792033.80739205, 337039.003454169], [2792050.00386422, 337015.100517293], [2792055.09450893, 337008.846404817], [2792060.75201059, 337004.085495656], [2792066.95923063, 337001.07121302], [2792074.91660924, 336999.276029708], [2792081.54366939, 336998.977570496], [2792087.22885363, 336999.615577007], [2792093.54835369, 337001.351554177], [2792099.10690287, 337003.717684563], [2792107.55562964, 337008.592063364], [2792152.11263588, 337036.696574865], [2792186.97180664, 337057.575825954], [2792216.35052101, 337076.093780087], [2792244.52398472, 337092.497408657], [2792261.34017814, 337101.487720807], [2792261.92001612, 337101.783163012], [2792266.72668893, 337103.80071442], [2792267.36944428, 337103.902516866], [2792273.14662178, 337104.531256191], [2792273.78937713, 337104.429453745], [2792277.18196472, 337103.826471582], [2792280.52162238, 337102.467190624], [2792281.10146035, 337102.171748419], [2792286.7489109, 337098.209541342], [2792287.20907293, 337097.749379318], [2792291.79003669, 337092.935047827], [2792307.91506535, 337069.900178988], [2792329.12749217, 337035.786193996], [2792352.20615981, 336997.386532527], [2792373.56834564, 336963.639298788], [2792391.13075305, 336933.680070302], [2792391.42619526, 336933.100232326], [2792394.96301181, 336925.586293037], [2792395.9083505, 336921.232007767], [2792396.01015295, 336920.589252419], [2792396.00141764, 336916.167045914], [2792395.89961519, 336915.524290565], [2792394.81360943, 336911.145521667], [2792392.77059373, 336907.03430575], [2792392.47515152, 336906.454467773], [2792390.41695841, 336903.602495507], [2792386.52731492, 336899.581862624], [2792386.0671529, 336899.1217006], [2792381.58662342, 336895.59771418], [2792371.60239794, 336889.067368496], [2792319.95448683, 336857.043541867], [2792261.26934549, 336819.111974158], [2792254.24330162, 336813.239775619], [2792250.67150806, 336807.889036845], [2792248.85884907, 336802.16347202], [2792248.2751427, 336795.635324464], [2792249.10618332, 336757.413725799], [2792251.01048885, 336736.390840007], [2792256.53437831, 336705.223569333], [2792256.63618075, 336704.580813985], [2792258.49713223, 336690.636566771], [2792259.12304852, 336676.958522863], [2792258.28546793, 336662.283471236], [2792259.21585693, 336655.523673673], [2792260.98485765, 336650.947402447], [2792263.91057076, 336646.393932993], [2792267.86048745, 336641.904731061], [2792276.49959853, 336633.941660469], [2792286.6633667, 336625.500182315], [2792299.829375, 336615.667268717], [2792304.64608138, 336613.06770397], [2792310.18215292, 336611.46295615], [2792318.01237288, 336611.265936661], [2792322.28798195, 336612.14259653], [2792327.74997751, 336614.28611371], [2792335.10599729, 336618.501575255], [2792343.92723334, 336624.457909078], [2792362.7348045, 336639.237990667], [2792366.89322529, 336641.359710257], [2792367.47306327, 336641.655152463], [2792372.40914024, 336643.226064507], [2792373.05189559, 336643.327866953], [2792376.46124411, 336643.816378421], [2792380.21661069, 336643.721668779], [2792380.85936603, 336643.619866333], [2792383.91305375, 336643.012913194], [2792387.53067582, 336641.573484745], [2792388.11051379, 336641.278042539], [2792393.73090693, 336637.092050358], [2792394.19106896, 336636.631888334], [2792396.56503282, 336633.694342864], [2792398.54963652, 336629.883594863], [2792398.84507872, 336629.303756886], [2792400.07002989, 336624.644553978], [2792400.17183234, 336624.00179863], [2792400.37545492, 336619.890458086], [2792399.60490285, 336614.898851873], [2792399.5031004, 336614.256096524], [2792398.1056519, 336610.265470515], [2792397.81020969, 336609.685632538], [2792395.43206588, 336605.263017232], [2792392.82891414, 336601.676967154], [2792392.36875212, 336601.21680513], [2792378.94550867, 336587.941204659], [2792376.11483896, 336584.346858778], [2792373.75709098, 336580.250029727], [2792361.8369092, 336550.77420935], [2792348.45861739, 336514.536352555], [2792345.04659982, 336504.000507062], [2792344.01819125, 336498.386851778], [2792343.6884275, 336490.51994629], [2792344.20175995, 336482.871570624], [2792347.16317754, 336467.640379427], [2792356.08770504, 336434.52637433], [2792370.02123271, 336391.735029734], [2792382.88619871, 336358.44509781], [2792395.22133232, 336330.774947828], [2792411.70147199, 336297.930029061], [2792445.58987741, 336233.564040609], [2792463.10649778, 336202.402239049], [2792491.37326338, 336160.148711019], [2792514.0515617, 336124.655745947], [2792522.34245289, 336110.81789711], [2792527.06632661, 336101.919122922], [2792527.36176881, 336101.339284946], [2792534.44109811, 336085.92107251], [2792591.10014456, 335955.683676242], [2792600.77505322, 335935.9337662], [2792627.63973922, 335885.063638088], [2792627.93518142, 335884.483800112], [2792654.26486818, 335827.038535016], [2792673.51662714, 335786.512316566], [2792681.29773161, 335771.612096981], [2792687.63515825, 335761.585546974], [2792693.76148414, 335755.40036056], [2792700.82182557, 335750.624829944], [2792719.46905506, 335740.580514347], [2792727.41865279, 335734.631889949], [2792727.87881481, 335734.171727926], [2792733.43536947, 335727.605659346], [2792739.08723871, 335718.299282355], [2792739.38268091, 335717.719444378], [2792746.69929153, 335703.142788498], [2792764.18298327, 335664.677364541], [2792842.07748616, 335501.678474059], [2792868.95108472, 335442.646484176], [2792873.24079264, 335431.503157251], [2792875.36839569, 335423.525340481], [2792878.37542401, 335406.546004634]]

Performance benchmarks

Are there any performance benchmarks vs other libs available?

JsClipper, the javascript port of Angus Johnsons Clipper (based on Vatti´s algorithm) come to mind for example

Dissolve GeoJSON : Please have a talk with w8r/martinez

In here we are trying to "dissolve" a huge mass of geojson Polygons / MultiPolygons.

We followed the documentation, and did this :

  const polyboolPolygons = polygons.map(polybool.polygonFromGeoJSON)

  const unionPolyboolPolygon = polyboolPolygons.reduce(
    (polyboolPolygonAcc, polyboolPolygon) => (
      (!polyboolPolygonAcc && polyboolPolygon) ||
      polybool.union(polyboolPolygonAcc, polyboolPolygon)
    ),
    null
  )

  const unionPolygon = polybool.polygonToGeoJSON(unionPolyboolPolygon)

This works perfectly, but it takes like 20 seconds to process the whole stuff...

On the other side, w8r/martinez process it in less than 400ms... but produces aberrations, like this :

(The base "larger" polygon has many holes, and you can see some are respected, others are curiously understood as other polygons, witch comes "over" the first)

I cannot really provide any dataset, because this one is huge, and I could not reproduce on a smaller one.

Sooo, is there a chance we can engage in a discussion between the 2 repos, to come up with a solution fully working, in less than 400ms? 😄

(Note: I duplicated the issue there)

union result is wrong

Hello, I am using polybooljs for my project.
During trying to get union data of the polys from following data, at last, I am getting empty regions:
{"regions":[],"inverted":false}

const poly1 = {"regions":[[[-175780,257560],[-175760,257540],[-175720,257560]],[[-175340,257720],[-175540,257620],[-175700,257680],[-175660,257780],[-175680,257860],[-175760,257840],[-175780,257700],[-175933.6923076923,257728.46153846153],[-175920,257660],[-175840,257660],[-175820,257560],[-175900,257560],[-175940,257460],[-176060,257400],[-176074.8872180451,257401.35338345866],[-176400,257260],[-176400,258100],[-176200,258200],[-176100,258240],[-176135.45454545456,258098.18181818182],[-176087.54716981133,257988.679245283],[-175940,258040],[-175820,257960],[-175660,257940],[-175500,257760],[-175380,257760]],[[-175600,258300],[-175600,258060],[-175660,258020],[-175640,257960],[-175540,257840],[-175220,257820],[-175320,257920],[-175320,257925],[-175280,257900],[-175140,257900],[-175140,258300]]],"inverted":false};
const poly2 = {"regions":[[[-175900,257560],[-176180,258200],[-175980,258300],[-175140,258300],[-175140,257800],[-175780,257540]]],"inverted":false};

Polygon Union returning 2 different result with a small change in location of an independent point

Hi,
Have a look at the red polygon's bottom rightmost point. By changing the location its position by few pixels the result is changed. Adding the images showing this case.
1st image - result is a single polygon which is union of both the polygon.
2nd image - returning the 2 polygons as is.

Zero length segments created

Hi,

OK so I've been having issues where I was getting zero length segments. They were created by either difference or intersect, not sure which, the path of creating them was a bit obscure (several hundred polygons some with thousands of vertices being operated on).

None of the initial polygons had a zero length segment, I checked that, but they ended up with some

So, I added the following. It SEEMS to be working and by the looks of it should be safe, but I'd like someone who knows more of the inner workings to verify there are no side effects before I create a PR.

--- js/polybool.js.crash        2021-09-21 08:31:22.649552763 +0100
+++ js/polybool.js      2021-09-21 07:18:43.756997472 +0100
@@ -882,6 +882,15 @@
 
                        if (ev.isStart){
 
+                           if (ev.pt[0]==ev.other.pt[0] &&
+                               ev.pt[1]==ev.other.pt[1])
+                           {
+                               //Identical, drop it
+                               ev.other.remove();
+                               ev.remove();
+                               continue;
+                           }
+
                                if (buildLog)
                                        buildLog.segmentNew(ev.seg, ev.primary);

Suggestion: Area

If at all possible, I'd like to make a suggestion that it would be really cool to add a new feature to calculate the area from a Polygon object :)

polygon.area() or something like that.

python port

Hi!
here is python port

Cut polygon by line

is this library supports cutting polygon with a line ?, Like this :

Distinguishing exterior rings from holes

How can I distinguish exterior rings from holes in the results?

As an idea, the library could use a GeoJson alike format of polygons+multipolygons inputs/outputs to handle this case.

Incorrect union edge case

Hi,

I'm working on an application with places of complex boundaries and allow users to union them when desired. I have tried about 5 JS polygon libraries and I have to say yours is the best. They all error out on different edge cases but polybooljs seems to handle most cases well.

I have encountered a few edge cases where your polygon union I believe does not give accurate results.

Here is an example:

polygon 1 coords

[[[-79.28426250055173,43.68075543492089],[-79.28335754511745,43.67858119554888],[-79.28272426128387,43.67753878734541],[-79.28426250055173,43.68075543492089]]]

polygon 2 coords

[[[-79.2839527130127,43.67786274564595],[-79.28335754511743,43.67858119554888],[-79.2829332351944,43.67755625060114],[-79.2839527130127,43.67786274564595]]]

polybooljs union result of the above 2 polygons

[[],[[-79.28272426128387,43.67753878734541],[-79.28335754511737,43.67858119554873],[-79.2829332351944,43.67755625060114],[-79.2839527130127,43.67786274564595],[-79.28335754511743,43.67858119554888],[-79.28426250055173,43.68075543492089]]]

I am able to plot both my polygons on geojson.io but not the generated union polygon.

I would really appreciate if you could look into this and provide some guidance.

Thanks

Speed improvement

I've been testing polybooljs on large polygons, and found that it was not scaling too well. The problem is that finding the point of insertion in a linked list means going through the list one link at a time, and doing a comparison each time—at a O(n) cost for each segment. I figured we could change that by using a sorted flat list (or array) instead, and finding the insertion point by bisection, resulting in a O(log n) insertion cost.

I've implemented that solution here: https://github.com/Fil/polybooljs/commits/sorted-array

Test here https://observablehq.com/d/a7fc92f18bc1365a

Feature Request: a way to cleanup polygons with zero-length segments

I'm having a hard time finding an epsilon that fits my data. How hard would it be to implement something that simply removes zero-length segments from the polygon?

Union completely ignoring some polygons

I have about a dozen of polygons that I am taking union of (tried both union method and the core api), but the two of them are completely ignored.

I have been stuck on this whole for a whole day, and spent another hour in compiling this example with reproducible error for easy debugging

https://codesandbox.io/s/polybooljs-forked-6vto7

In this example poly1 and poly2 (green and magenta) are not present in the union

About porting the libary to antoher languages

I have successfully ported thee Libary to flutter, it's an initial version so except for more improvements to test cases/ documentation,
Here is https://github.com/mohammedX6/poly_bool_dart

Not an issue, just a thanks.

Thanks for writing this library. I needed to union a lot of geojson geometries together and it made no sense to import the entire jsts library for one utility. With yours coming in at roughly 21kb compared to over 400kb for jsts, its a huge improvement. So far haven't encountered any polygon <-> geojson problems but I'll report back if something happens.

GeoJSON comments

Please leave comments here about the experimental GeoJSON support.

Polygon subtraction creates degenerate result polygon

With the below polygons, subtracting S from T creates a degenerate result polygon: Instead of splitting the result into two polygons at vertex 3, it creates a single polygon with vertex 3 sitting on the edge connecting vertex 0 and 1.

I'm not sure if this is intended behavior? With other vertex-on-edge scenarios, result polygons always get split up correctly, so I think this is probably a bug.

var polybooljs = require("polybooljs")

const T = {
    inverted: false,
    regions: [[
        [ 3.1827730120236866, -14.647299060696893 ],
        [ 3.292779172743269, -14.709442780204576 ],
        [ 3.2790977409099513, -15.096879410975502 ]
    ]]
};
const S = {
    inverted: false,
    regions: [[
        [ 3.3984917402267456, -14.277922392125454 ],
        [ 3.3984917402267456, -14.919993494289331 ],
        [ 3.2411990917407074, -14.919993494289326 ]
    ]]
};
polybooljs.difference(T,S) // {   regions: [[
                           //         [ 3.1827730120236866, -14.647299060696893 ],
                           //         [ 3.2790977409099513, -15.096879410975502 ],
                           //         [ 3.2853440594539682, -14.919993494289328 ],
                           //         [ 3.2411990917407074, -14.919993494289326 ],
                           //         [ 3.292779172743269, -14.709442780204576]
                           //     ]],
                           //     inverted: false    }

Here is a graphical representation of T and S:

PolyBool.combine modifies its arguments

If you consider 3 polygons p1, p2 and p3. The following operations produce unespected result:

var s1 = PolyBool.segments(p1);
var s2 = PolyBool.segments(p2);
var s3 = PolyBool.segments(p3);
var comb1 = PolyBool.combine(s1, s2); //this modifies s1 and s2
var res1 = PolyBool.polygon(Polybool.selectUnion(comb1));
var comb2 = PolyBool.combine(s1, s3); //bad since s1 has been modified
var res2 = PolyBool.polygon(Polybool.selectUnion(comb2));

It appears that the result of a PolyBool.segments call can only be used once. Do you think that this could be fixed? (If not, i suggest to mention this in the documentation.)

getting intersection points

How I can modify the library in a way to get intersection points ? btw the demo link is broken.

Hello, the performance of this library is very low, and the calculation is very slow. When can we have an optimized version?

How to separate poly to several polys

After some bool operations, I may get a poly which actual is a combination of several separated polys, like this:

this blue poly difference the red poly and get the green poly.

How could I separate the green poly to two polys? Is there a simple solution to this question, or I need to solve it by other algorithm?

TypeScript type declaration file

If you want I can write a TypeScript type declaration file for this package so that TS developers can utilise the type-checking feature of the language as they use this package. Let me know if you are interested.

polybool java

Dear Sean, Thank you for sharing such great library.

As I am currently working on Android. that's why I decided to transpile the library to java
I just wanted to let you know that such fork is here:

https://github.com/the3deers/polybool-java

Kind regards

Consider adding line segments

I was trying to use PolyBool to do a boolean operation on a line and couldnt quite get it to work. Here's what I was going for, notice how the second shape only has two points. This is for an art project, and suggestions would be greatly appreciated!
`
const shape1 = {
regions: [[
[100,100],
[200,100],
[200,200],
[100,200],
[100,100]
]],
inverted: false
}

const shape2 = {
    regions: [[
        [50,50],
        [300,300]
    ]],
    inverted: false
}


const t = PolyBool.difference(shape1, shape2);

Dist is not a single file

Tried copying one of the dist files and noticed that they point back to the lib folder. You end up needing all the files.

I made a demo game based on polybooljs, looking for performance improvements.

http://adamwong246.github.io/blog/44-Duskers-like-V2/duskersV2.html
https://github.com/adamwong246/SpaceTrash/tree/fov/src/apps/experiments/rotFovReact

I am looking for ANY improvements I can make to performance, specifically this line

Holes (again)

I've spent a while trying to modify the code to try and change it to add information about whether a poly is an inner bound, ie a hole. So for example:

{"regions":[
[[250,250],[250,150],[150,150],[150,250]],
[[300,300],[300,100],[100,100],[100,300]]],
"inverted":false}

A basic square in a square, where the inner is the hole boundary.

I can calculate this myself using the data, find out how many polys a point is inside, but it struck me that, somewhere in your calculations, you HAVE this information, and it will be a LOT more efficient to just use what's already pre-calculated. So I've been trying to modify it so that the return looks like

{"regions":[
[[250,250],[250,150],[150,150],[150,250]],
[[300,300],[300,100],[100,100],[100,300]]],
"inverted":false,
"metadata":[{"innerbound": true},
{"innerbound": false}]
}

Where the metadata is in the same order as the regions. I suppose making the polys each a class, even possibly with a hierarchy could be done, but this seemed to be least invasive, and backwards compatible.

I've watched your segments tutorial and it makes sense, but when it comes to modifying the code for this, I just can't wrap my head around the segmentchainer to do this. Any suggestions?

Polygon union of rectangles produces inconsistent result

let rects = [
	[ // rect 1
		[10,10],
		[20,10],
		[20,20],
		[10,20],
	],[ // rect 2
		[20,20],
		[30,20],
		[30,30],
		[20,30],
	],[ // rect 3
		[10,30],
		[20,30],
		[20,40],
		[10,40],
	],
];

let poly = PolyBool.union({
	regions: rects,
	inverted: false,
}, {
	regions: [],
	inverted: false,
});

Why rect 1 and rect 2 is not merged, but rect 2 and rect 3 is merged?

Is there any way to disable this corner to corner union?

Sorry for my broken english.

Failure case

Fails poly1's self-intersection phase

 PolyBool.union(
  [ [[100, 100], [200, 200], [300, 100]], [[200, 100], [300, 200], [400, 100]] ],
  false,
  [ [[50, 50], [200, 50], [300, 300]] ],
  false
)

Support different fill rules (even/odd supported, add positive-only, etc)

Currently, the library is specifically coded to work with even/odd fill rule. It would be nice if there was an option for other fill rules.

Support for polygon with holes?

I'm wondering if this library can support polygon with holes? I'm not sure what the inverted property of a polygon is supposed to mean. My guess was that it is used to handle what is commonly called polygon holes. However when taking the union of these 4 "border" rectangles

using

var PolyBool = require('polybooljs');

let polygons = [
  {"regions":[[[0,0],[100,0],[100,10],[0,10]]],"inverted":false},
  {"regions":[[[90,0],[100,0],[100,100],[90,100]]],"inverted":false},
  {"regions":[[[0,90],[100,90],[100,100],[0,100]]],"inverted":false},
  {"regions":[[[0,0],[10,0],[10,100],[0,100]]],"inverted":false},
]

// Using the naive multi polygon join. The approach via segments seems to give the same results.
var union = polygons[0];
for (var i = 1; i < polygons.length; i++) {
  union = PolyBool.union(union, polygons[i]);
}

console.log(JSON.stringify(union));

This should produce a single polygon (the outer ring) with one hole (the inner ring). However, I'm getting a polygon with two regions, and there is no way to differentiate what is exterior / interior from the output:

{"regions":[[[90,90],[90,10],[10,10],[10,90]],[[100,100],[100,0],[0,0],[0,100]]],"inverted":false}

Graphically:

Is there a way to properly determine polygon holes?

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.