Changeset 96999 in spip-zone


Ignore:
Timestamp:
May 6, 2016, 9:37:50 AM (5 years ago)
Author:
kent1@…
Message:

Mise à jour de topojson.js

Location:
_plugins_/d3js/trunk/javascript
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • _plugins_/d3js/trunk/javascript/topojson.js

    r96616 r96999  
    1 !function() {
    2   var topojson = {
    3     version: "1.6.19",
    4     mesh: function(topology) { return object(topology, meshArcs.apply(this, arguments)); },
    5     meshArcs: meshArcs,
    6     merge: function(topology) { return object(topology, mergeArcs.apply(this, arguments)); },
    7     mergeArcs: mergeArcs,
    8     feature: featureOrCollection,
    9     neighbors: neighbors,
    10     presimplify: presimplify
    11   };
    12 
    13   function stitchArcs(topology, arcs) {
    14     var stitchedArcs = {},
    15         fragmentByStart = {},
    16         fragmentByEnd = {},
    17         fragments = [],
    18         emptyIndex = -1;
    19 
    20     // Stitch empty arcs first, since they may be subsumed by other arcs.
    21     arcs.forEach(function(i, j) {
    22       var arc = topology.arcs[i < 0 ? ~i : i], t;
    23       if (arc.length < 3 && !arc[1][0] && !arc[1][1]) {
    24         t = arcs[++emptyIndex], arcs[emptyIndex] = i, arcs[j] = t;
    25       }
    26     });
    27 
    28     arcs.forEach(function(i) {
    29       var e = ends(i),
    30           start = e[0],
    31           end = e[1],
    32           f, g;
    33 
    34       if (f = fragmentByEnd[start]) {
    35         delete fragmentByEnd[f.end];
    36         f.push(i);
    37         f.end = end;
    38         if (g = fragmentByStart[end]) {
    39           delete fragmentByStart[g.start];
    40           var fg = g === f ? f : f.concat(g);
    41           fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg;
    42         } else {
    43           fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
    44         }
    45       } else if (f = fragmentByStart[end]) {
    46         delete fragmentByStart[f.start];
    47         f.unshift(i);
    48         f.start = start;
    49         if (g = fragmentByEnd[start]) {
    50           delete fragmentByEnd[g.end];
    51           var gf = g === f ? f : g.concat(f);
    52           fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf;
    53         } else {
    54           fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
    55         }
    56       } else {
    57         f = [i];
    58         fragmentByStart[f.start = start] = fragmentByEnd[f.end = end] = f;
    59       }
    60     });
    61 
    62     function ends(i) {
    63       var arc = topology.arcs[i < 0 ? ~i : i], p0 = arc[0], p1;
    64       if (topology.transform) p1 = [0, 0], arc.forEach(function(dp) { p1[0] += dp[0], p1[1] += dp[1]; });
    65       else p1 = arc[arc.length - 1];
    66       return i < 0 ? [p1, p0] : [p0, p1];
    67     }
    68 
    69     function flush(fragmentByEnd, fragmentByStart) {
    70       for (var k in fragmentByEnd) {
    71         var f = fragmentByEnd[k];
    72         delete fragmentByStart[f.start];
    73         delete f.start;
    74         delete f.end;
    75         f.forEach(function(i) { stitchedArcs[i < 0 ? ~i : i] = 1; });
    76         fragments.push(f);
    77       }
    78     }
    79 
    80     flush(fragmentByEnd, fragmentByStart);
    81     flush(fragmentByStart, fragmentByEnd);
    82     arcs.forEach(function(i) { if (!stitchedArcs[i < 0 ? ~i : i]) fragments.push([i]); });
    83 
    84     return fragments;
    85   }
    86 
    87   function meshArcs(topology, o, filter) {
    88     var arcs = [];
    89 
    90     if (arguments.length > 1) {
    91       var geomsByArc = [],
    92           geom;
    93 
    94       function arc(i) {
    95         var j = i < 0 ? ~i : i;
    96         (geomsByArc[j] || (geomsByArc[j] = [])).push({i: i, g: geom});
    97       }
    98 
    99       function line(arcs) {
    100         arcs.forEach(arc);
    101       }
    102 
    103       function polygon(arcs) {
    104         arcs.forEach(line);
    105       }
    106 
    107       function geometry(o) {
    108         if (o.type === "GeometryCollection") o.geometries.forEach(geometry);
    109         else if (o.type in geometryType) geom = o, geometryType[o.type](o.arcs);
    110       }
    111 
    112       var geometryType = {
    113         LineString: line,
    114         MultiLineString: polygon,
    115         Polygon: polygon,
    116         MultiPolygon: function(arcs) { arcs.forEach(polygon); }
    117       };
    118 
    119       geometry(o);
    120 
    121       geomsByArc.forEach(arguments.length < 3
    122           ? function(geoms) { arcs.push(geoms[0].i); }
    123           : function(geoms) { if (filter(geoms[0].g, geoms[geoms.length - 1].g)) arcs.push(geoms[0].i); });
    124     } else {
    125       for (var i = 0, n = topology.arcs.length; i < n; ++i) arcs.push(i);
    126     }
    127 
    128     return {type: "MultiLineString", arcs: stitchArcs(topology, arcs)};
    129   }
    130 
    131   function mergeArcs(topology, objects) {
    132     var polygonsByArc = {},
    133         polygons = [],
    134         components = [];
    135 
    136     objects.forEach(function(o) {
    137       if (o.type === "Polygon") register(o.arcs);
    138       else if (o.type === "MultiPolygon") o.arcs.forEach(register);
    139     });
    140 
    141     function register(polygon) {
    142       polygon.forEach(function(ring) {
    143         ring.forEach(function(arc) {
    144           (polygonsByArc[arc = arc < 0 ? ~arc : arc] || (polygonsByArc[arc] = [])).push(polygon);
    145         });
    146       });
    147       polygons.push(polygon);
    148     }
    149 
    150     function exterior(ring) {
    151       return cartesianRingArea(object(topology, {type: "Polygon", arcs: [ring]}).coordinates[0]) > 0; // TODO allow spherical?
    152     }
    153 
    154     polygons.forEach(function(polygon) {
    155       if (!polygon._) {
    156         var component = [],
    157             neighbors = [polygon];
    158         polygon._ = 1;
    159         components.push(component);
    160         while (polygon = neighbors.pop()) {
    161           component.push(polygon);
    162           polygon.forEach(function(ring) {
    163             ring.forEach(function(arc) {
    164               polygonsByArc[arc < 0 ? ~arc : arc].forEach(function(polygon) {
    165                 if (!polygon._) {
    166                   polygon._ = 1;
    167                   neighbors.push(polygon);
    168                 }
    169               });
    170             });
    171           });
    172         }
    173       }
    174     });
    175 
    176     polygons.forEach(function(polygon) {
    177       delete polygon._;
    178     });
    179 
    180     return {
    181       type: "MultiPolygon",
    182       arcs: components.map(function(polygons) {
    183         var arcs = [];
    184 
    185         // Extract the exterior (unique) arcs.
    186         polygons.forEach(function(polygon) {
    187           polygon.forEach(function(ring) {
    188             ring.forEach(function(arc) {
    189               if (polygonsByArc[arc < 0 ? ~arc : arc].length < 2) {
    190                 arcs.push(arc);
    191               }
    192             });
    193           });
    194         });
    195 
    196         // Stitch the arcs into one or more rings.
    197         arcs = stitchArcs(topology, arcs);
    198 
    199         // If more than one ring is returned,
    200         // at most one of these rings can be the exterior;
    201         // this exterior ring has the same winding order
    202         // as any exterior ring in the original polygons.
    203         if ((n = arcs.length) > 1) {
    204           var sgn = exterior(polygons[0][0]);
    205           for (var i = 0, t; i < n; ++i) {
    206             if (sgn === exterior(arcs[i])) {
    207               t = arcs[0], arcs[0] = arcs[i], arcs[i] = t;
    208               break;
    209             }
    210           }
    211         }
    212 
    213         return arcs;
    214       })
    215     };
    216   }
    217 
    218   function featureOrCollection(topology, o) {
    219     return o.type === "GeometryCollection" ? {
    220       type: "FeatureCollection",
    221       features: o.geometries.map(function(o) { return feature(topology, o); })
    222     } : feature(topology, o);
    223   }
    224 
    225   function feature(topology, o) {
    226     var f = {
    227       type: "Feature",
    228       id: o.id,
    229       properties: o.properties || {},
    230       geometry: object(topology, o)
    231     };
    232     if (o.id == null) delete f.id;
    233     return f;
    234   }
    235 
    236   function object(topology, o) {
    237     var absolute = transformAbsolute(topology.transform),
    238         arcs = topology.arcs;
    239 
    240     function arc(i, points) {
    241       if (points.length) points.pop();
    242       for (var a = arcs[i < 0 ? ~i : i], k = 0, n = a.length, p; k < n; ++k) {
    243         points.push(p = a[k].slice());
    244         absolute(p, k);
    245       }
    246       if (i < 0) reverse(points, n);
    247     }
    248 
    249     function point(p) {
    250       p = p.slice();
    251       absolute(p, 0);
    252       return p;
    253     }
    254 
    255     function line(arcs) {
    256       var points = [];
    257       for (var i = 0, n = arcs.length; i < n; ++i) arc(arcs[i], points);
    258       if (points.length < 2) points.push(points[0].slice());
    259       return points;
    260     }
    261 
    262     function ring(arcs) {
    263       var points = line(arcs);
    264       while (points.length < 4) points.push(points[0].slice());
    265       return points;
    266     }
    267 
    268     function polygon(arcs) {
    269       return arcs.map(ring);
    270     }
    271 
    272     function geometry(o) {
    273       var t = o.type;
    274       return t === "GeometryCollection" ? {type: t, geometries: o.geometries.map(geometry)}
    275           : t in geometryType ? {type: t, coordinates: geometryType[t](o)}
    276           : null;
    277     }
    278 
    279     var geometryType = {
    280       Point: function(o) { return point(o.coordinates); },
    281       MultiPoint: function(o) { return o.coordinates.map(point); },
    282       LineString: function(o) { return line(o.arcs); },
    283       MultiLineString: function(o) { return o.arcs.map(line); },
    284       Polygon: function(o) { return polygon(o.arcs); },
    285       MultiPolygon: function(o) { return o.arcs.map(polygon); }
    286     };
    287 
    288     return geometry(o);
    289   }
    290 
    291   function reverse(array, n) {
    292     var t, j = array.length, i = j - n; while (i < --j) t = array[i], array[i++] = array[j], array[j] = t;
    293   }
    294 
    295   function bisect(a, x) {
    296     var lo = 0, hi = a.length;
    297     while (lo < hi) {
    298       var mid = lo + hi >>> 1;
    299       if (a[mid] < x) lo = mid + 1;
    300       else hi = mid;
    301     }
    302     return lo;
    303   }
    304 
    305   function neighbors(objects) {
    306     var indexesByArc = {}, // arc index -> array of object indexes
    307         neighbors = objects.map(function() { return []; });
    308 
    309     function line(arcs, i) {
    310       arcs.forEach(function(a) {
    311         if (a < 0) a = ~a;
    312         var o = indexesByArc[a];
    313         if (o) o.push(i);
    314         else indexesByArc[a] = [i];
    315       });
    316     }
    317 
    318     function polygon(arcs, i) {
    319       arcs.forEach(function(arc) { line(arc, i); });
    320     }
    321 
    322     function geometry(o, i) {
    323       if (o.type === "GeometryCollection") o.geometries.forEach(function(o) { geometry(o, i); });
    324       else if (o.type in geometryType) geometryType[o.type](o.arcs, i);
    325     }
    326 
    327     var geometryType = {
    328       LineString: line,
    329       MultiLineString: polygon,
    330       Polygon: polygon,
    331       MultiPolygon: function(arcs, i) { arcs.forEach(function(arc) { polygon(arc, i); }); }
    332     };
    333 
    334     objects.forEach(geometry);
    335 
    336     for (var i in indexesByArc) {
    337       for (var indexes = indexesByArc[i], m = indexes.length, j = 0; j < m; ++j) {
    338         for (var k = j + 1; k < m; ++k) {
    339           var ij = indexes[j], ik = indexes[k], n;
    340           if ((n = neighbors[ij])[i = bisect(n, ik)] !== ik) n.splice(i, 0, ik);
    341           if ((n = neighbors[ik])[i = bisect(n, ij)] !== ij) n.splice(i, 0, ij);
    342         }
    343       }
    344     }
    345 
    346     return neighbors;
    347   }
    348 
    349   function presimplify(topology, triangleArea) {
    350     var absolute = transformAbsolute(topology.transform),
    351         relative = transformRelative(topology.transform),
    352         heap = minAreaHeap();
    353 
    354     if (!triangleArea) triangleArea = cartesianTriangleArea;
    355 
    356     topology.arcs.forEach(function(arc) {
    357       var triangles = [],
    358           maxArea = 0,
    359           triangle;
    360 
    361       // To store each point’s effective area, we create a new array rather than
    362       // extending the passed-in point to workaround a Chrome/V8 bug (getting
    363       // stuck in smi mode). For midpoints, the initial effective area of
    364       // Infinity will be computed in the next step.
    365       for (var i = 0, n = arc.length, p; i < n; ++i) {
    366         p = arc[i];
    367         absolute(arc[i] = [p[0], p[1], Infinity], i);
    368       }
    369 
    370       for (var i = 1, n = arc.length - 1; i < n; ++i) {
    371         triangle = arc.slice(i - 1, i + 2);
    372         triangle[1][2] = triangleArea(triangle);
    373         triangles.push(triangle);
    374         heap.push(triangle);
    375       }
    376 
    377       for (var i = 0, n = triangles.length; i < n; ++i) {
    378         triangle = triangles[i];
    379         triangle.previous = triangles[i - 1];
    380         triangle.next = triangles[i + 1];
    381       }
    382 
    383       while (triangle = heap.pop()) {
    384         var previous = triangle.previous,
    385             next = triangle.next;
    386 
    387         // If the area of the current point is less than that of the previous point
    388         // to be eliminated, use the latter's area instead. This ensures that the
    389         // current point cannot be eliminated without eliminating previously-
    390         // eliminated points.
    391         if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
    392         else maxArea = triangle[1][2];
    393 
    394         if (previous) {
    395           previous.next = next;
    396           previous[2] = triangle[2];
    397           update(previous);
    398         }
    399 
    400         if (next) {
    401           next.previous = previous;
    402           next[0] = triangle[0];
    403           update(next);
    404         }
    405       }
    406 
    407       arc.forEach(relative);
    408     });
    409 
    410     function update(triangle) {
    411       heap.remove(triangle);
    412       triangle[1][2] = triangleArea(triangle);
    413       heap.push(triangle);
    414     }
    415 
    416     return topology;
    417   };
    418 
    419   function cartesianRingArea(ring) {
    420     var i = -1,
    421         n = ring.length,
    422         a,
    423         b = ring[n - 1],
    424         area = 0;
    425 
    426     while (++i < n) {
    427       a = b;
    428       b = ring[i];
    429       area += a[0] * b[1] - a[1] * b[0];
    430     }
    431 
    432     return area * .5;
    433   }
    434 
    435   function cartesianTriangleArea(triangle) {
    436     var a = triangle[0], b = triangle[1], c = triangle[2];
    437     return Math.abs((a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1]));
    438   }
    439 
    440   function compareArea(a, b) {
    441     return a[1][2] - b[1][2];
    442   }
    443 
    444   function minAreaHeap() {
    445     var heap = {},
    446         array = [],
    447         size = 0;
    448 
    449     heap.push = function(object) {
    450       up(array[object._ = size] = object, size++);
    451       return size;
    452     };
    453 
    454     heap.pop = function() {
    455       if (size <= 0) return;
    456       var removed = array[0], object;
    457       if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0);
    458       return removed;
    459     };
    460 
    461     heap.remove = function(removed) {
    462       var i = removed._, object;
    463       if (array[i] !== removed) return; // invalid request
    464       if (i !== --size) object = array[size], (compareArea(object, removed) < 0 ? up : down)(array[object._ = i] = object, i);
    465       return i;
    466     };
    467 
    468     function up(object, i) {
    469       while (i > 0) {
    470         var j = ((i + 1) >> 1) - 1,
    471             parent = array[j];
    472         if (compareArea(object, parent) >= 0) break;
    473         array[parent._ = i] = parent;
    474         array[object._ = i = j] = object;
    475       }
    476     }
    477 
    478     function down(object, i) {
    479       while (true) {
    480         var r = (i + 1) << 1,
    481             l = r - 1,
    482             j = i,
    483             child = array[j];
    484         if (l < size && compareArea(array[l], child) < 0) child = array[j = l];
    485         if (r < size && compareArea(array[r], child) < 0) child = array[j = r];
    486         if (j === i) break;
    487         array[child._ = i] = child;
    488         array[object._ = i = j] = object;
    489       }
    490     }
    491 
    492     return heap;
    493   }
     1(function (global, factory) {
     2  typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
     3  typeof define === 'function' && define.amd ? define(['exports'], factory) :
     4  (factory((global.topojson = global.topojson || {})));
     5}(this, function (exports) { 'use strict';
     6
     7  function noop() {}
    4948
    4959  function transformAbsolute(transform) {
    … …  
    51832    return function(point, i) {
    51933      if (!i) x0 = y0 = 0;
    520       var x1 = (point[0] - dx) / kx | 0,
    521           y1 = (point[1] - dy) / ky | 0;
     34      var x1 = Math.round((point[0] - dx) / kx),
     35          y1 = Math.round((point[1] - dy) / ky);
    52236      point[0] = x1 - x0;
    52337      point[1] = y1 - y0;
    … …  
    52741  }
    52842
    529   function noop() {}
    530 
    531   if (typeof define === "function" && define.amd) define(topojson);
    532   else if (typeof module === "object" && module.exports) module.exports = topojson;
    533   else this.topojson = topojson;
    534 }();
     43  function reverse(array, n) {
     44    var t, j = array.length, i = j - n;
     45    while (i < --j) t = array[i], array[i++] = array[j], array[j] = t;
     46  }
     47
     48  function bisect(a, x) {
     49    var lo = 0, hi = a.length;
     50    while (lo < hi) {
     51      var mid = lo + hi >>> 1;
     52      if (a[mid] < x) lo = mid + 1;
     53      else hi = mid;
     54    }
     55    return lo;
     56  }
     57
     58  function feature(topology, o) {
     59    return o.type === "GeometryCollection" ? {
     60      type: "FeatureCollection",
     61      features: o.geometries.map(function(o) { return feature$1(topology, o); })
     62    } : feature$1(topology, o);
     63  }
     64
     65  function feature$1(topology, o) {
     66    var f = {
     67      type: "Feature",
     68      id: o.id,
     69      properties: o.properties || {},
     70      geometry: object(topology, o)
     71    };
     72    if (o.id == null) delete f.id;
     73    return f;
     74  }
     75
     76  function object(topology, o) {
     77    var absolute = transformAbsolute(topology.transform),
     78        arcs = topology.arcs;
     79
     80    function arc(i, points) {
     81      if (points.length) points.pop();
     82      for (var a = arcs[i < 0 ? ~i : i], k = 0, n = a.length, p; k < n; ++k) {
     83        points.push(p = a[k].slice());
     84        absolute(p, k);
     85      }
     86      if (i < 0) reverse(points, n);
     87    }
     88
     89    function point(p) {
     90      p = p.slice();
     91      absolute(p, 0);
     92      return p;
     93    }
     94
     95    function line(arcs) {
     96      var points = [];
     97      for (var i = 0, n = arcs.length; i < n; ++i) arc(arcs[i], points);
     98      if (points.length < 2) points.push(points[0].slice());
     99      return points;
     100    }
     101
     102    function ring(arcs) {
     103      var points = line(arcs);
     104      while (points.length < 4) points.push(points[0].slice());
     105      return points;
     106    }
     107
     108    function polygon(arcs) {
     109      return arcs.map(ring);
     110    }
     111
     112    function geometry(o) {
     113      var t = o.type;
     114      return t === "GeometryCollection" ? {type: t, geometries: o.geometries.map(geometry)}
     115          : t in geometryType ? {type: t, coordinates: geometryType[t](o)}
     116          : null;
     117    }
     118
     119    var geometryType = {
     120      Point: function(o) { return point(o.coordinates); },
     121      MultiPoint: function(o) { return o.coordinates.map(point); },
     122      LineString: function(o) { return line(o.arcs); },
     123      MultiLineString: function(o) { return o.arcs.map(line); },
     124      Polygon: function(o) { return polygon(o.arcs); },
     125      MultiPolygon: function(o) { return o.arcs.map(polygon); }
     126    };
     127
     128    return geometry(o);
     129  }
     130
     131  function stitchArcs(topology, arcs) {
     132    var stitchedArcs = {},
     133        fragmentByStart = {},
     134        fragmentByEnd = {},
     135        fragments = [],
     136        emptyIndex = -1;
     137
     138    // Stitch empty arcs first, since they may be subsumed by other arcs.
     139    arcs.forEach(function(i, j) {
     140      var arc = topology.arcs[i < 0 ? ~i : i], t;
     141      if (arc.length < 3 && !arc[1][0] && !arc[1][1]) {
     142        t = arcs[++emptyIndex], arcs[emptyIndex] = i, arcs[j] = t;
     143      }
     144    });
     145
     146    arcs.forEach(function(i) {
     147      var e = ends(i),
     148          start = e[0],
     149          end = e[1],
     150          f, g;
     151
     152      if (f = fragmentByEnd[start]) {
     153        delete fragmentByEnd[f.end];
     154        f.push(i);
     155        f.end = end;
     156        if (g = fragmentByStart[end]) {
     157          delete fragmentByStart[g.start];
     158          var fg = g === f ? f : f.concat(g);
     159          fragmentByStart[fg.start = f.start] = fragmentByEnd[fg.end = g.end] = fg;
     160        } else {
     161          fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
     162        }
     163      } else if (f = fragmentByStart[end]) {
     164        delete fragmentByStart[f.start];
     165        f.unshift(i);
     166        f.start = start;
     167        if (g = fragmentByEnd[start]) {
     168          delete fragmentByEnd[g.end];
     169          var gf = g === f ? f : g.concat(f);
     170          fragmentByStart[gf.start = g.start] = fragmentByEnd[gf.end = f.end] = gf;
     171        } else {
     172          fragmentByStart[f.start] = fragmentByEnd[f.end] = f;
     173        }
     174      } else {
     175        f = [i];
     176        fragmentByStart[f.start = start] = fragmentByEnd[f.end = end] = f;
     177      }
     178    });
     179
     180    function ends(i) {
     181      var arc = topology.arcs[i < 0 ? ~i : i], p0 = arc[0], p1;
     182      if (topology.transform) p1 = [0, 0], arc.forEach(function(dp) { p1[0] += dp[0], p1[1] += dp[1]; });
     183      else p1 = arc[arc.length - 1];
     184      return i < 0 ? [p1, p0] : [p0, p1];
     185    }
     186
     187    function flush(fragmentByEnd, fragmentByStart) {
     188      for (var k in fragmentByEnd) {
     189        var f = fragmentByEnd[k];
     190        delete fragmentByStart[f.start];
     191        delete f.start;
     192        delete f.end;
     193        f.forEach(function(i) { stitchedArcs[i < 0 ? ~i : i] = 1; });
     194        fragments.push(f);
     195      }
     196    }
     197
     198    flush(fragmentByEnd, fragmentByStart);
     199    flush(fragmentByStart, fragmentByEnd);
     200    arcs.forEach(function(i) { if (!stitchedArcs[i < 0 ? ~i : i]) fragments.push([i]); });
     201
     202    return fragments;
     203  }
     204
     205  function mesh(topology) {
     206    return object(topology, meshArcs.apply(this, arguments));
     207  }
     208
     209  function meshArcs(topology, o, filter) {
     210    var arcs = [];
     211
     212    function arc(i) {
     213      var j = i < 0 ? ~i : i;
     214      (geomsByArc[j] || (geomsByArc[j] = [])).push({i: i, g: geom});
     215    }
     216
     217    function line(arcs) {
     218      arcs.forEach(arc);
     219    }
     220
     221    function polygon(arcs) {
     222      arcs.forEach(line);
     223    }
     224
     225    function geometry(o) {
     226      if (o.type === "GeometryCollection") o.geometries.forEach(geometry);
     227      else if (o.type in geometryType) geom = o, geometryType[o.type](o.arcs);
     228    }
     229
     230    if (arguments.length > 1) {
     231      var geomsByArc = [],
     232          geom;
     233
     234      var geometryType = {
     235        LineString: line,
     236        MultiLineString: polygon,
     237        Polygon: polygon,
     238        MultiPolygon: function(arcs) { arcs.forEach(polygon); }
     239      };
     240
     241      geometry(o);
     242
     243      geomsByArc.forEach(arguments.length < 3
     244          ? function(geoms) { arcs.push(geoms[0].i); }
     245          : function(geoms) { if (filter(geoms[0].g, geoms[geoms.length - 1].g)) arcs.push(geoms[0].i); });
     246    } else {
     247      for (var i = 0, n = topology.arcs.length; i < n; ++i) arcs.push(i);
     248    }
     249
     250    return {type: "MultiLineString", arcs: stitchArcs(topology, arcs)};
     251  }
     252
     253  function cartesianTriangleArea(triangle) {
     254    var a = triangle[0], b = triangle[1], c = triangle[2];
     255    return Math.abs((a[0] - c[0]) * (b[1] - a[1]) - (a[0] - b[0]) * (c[1] - a[1]));
     256  }
     257
     258  function ring(ring) {
     259    var i = -1,
     260        n = ring.length,
     261        a,
     262        b = ring[n - 1],
     263        area = 0;
     264
     265    while (++i < n) {
     266      a = b;
     267      b = ring[i];
     268      area += a[0] * b[1] - a[1] * b[0];
     269    }
     270
     271    return area / 2;
     272  }
     273
     274  function merge(topology) {
     275    return object(topology, mergeArcs.apply(this, arguments));
     276  }
     277
     278  function mergeArcs(topology, objects) {
     279    var polygonsByArc = {},
     280        polygons = [],
     281        components = [];
     282
     283    objects.forEach(function(o) {
     284      if (o.type === "Polygon") register(o.arcs);
     285      else if (o.type === "MultiPolygon") o.arcs.forEach(register);
     286    });
     287
     288    function register(polygon) {
     289      polygon.forEach(function(ring$$) {
     290        ring$$.forEach(function(arc) {
     291          (polygonsByArc[arc = arc < 0 ? ~arc : arc] || (polygonsByArc[arc] = [])).push(polygon);
     292        });
     293      });
     294      polygons.push(polygon);
     295    }
     296
     297    function area(ring$$) {
     298      return Math.abs(ring(object(topology, {type: "Polygon", arcs: [ring$$]}).coordinates[0]));
     299    }
     300
     301    polygons.forEach(function(polygon) {
     302      if (!polygon._) {
     303        var component = [],
     304            neighbors = [polygon];
     305        polygon._ = 1;
     306        components.push(component);
     307        while (polygon = neighbors.pop()) {
     308          component.push(polygon);
     309          polygon.forEach(function(ring$$) {
     310            ring$$.forEach(function(arc) {
     311              polygonsByArc[arc < 0 ? ~arc : arc].forEach(function(polygon) {
     312                if (!polygon._) {
     313                  polygon._ = 1;
     314                  neighbors.push(polygon);
     315                }
     316              });
     317            });
     318          });
     319        }
     320      }
     321    });
     322
     323    polygons.forEach(function(polygon) {
     324      delete polygon._;
     325    });
     326
     327    return {
     328      type: "MultiPolygon",
     329      arcs: components.map(function(polygons) {
     330        var arcs = [], n;
     331
     332        // Extract the exterior (unique) arcs.
     333        polygons.forEach(function(polygon) {
     334          polygon.forEach(function(ring$$) {
     335            ring$$.forEach(function(arc) {
     336              if (polygonsByArc[arc < 0 ? ~arc : arc].length < 2) {
     337                arcs.push(arc);
     338              }
     339            });
     340          });
     341        });
     342
     343        // Stitch the arcs into one or more rings.
     344        arcs = stitchArcs(topology, arcs);
     345
     346        // If more than one ring is returned,
     347        // at most one of these rings can be the exterior;
     348        // choose the one with the greatest absolute area.
     349        if ((n = arcs.length) > 1) {
     350          for (var i = 1, k = area(arcs[0]), ki, t; i < n; ++i) {
     351            if ((ki = area(arcs[i])) > k) {
     352              t = arcs[0], arcs[0] = arcs[i], arcs[i] = t, k = ki;
     353            }
     354          }
     355        }
     356
     357        return arcs;
     358      })
     359    };
     360  }
     361
     362  function neighbors(objects) {
     363    var indexesByArc = {}, // arc index -> array of object indexes
     364        neighbors = objects.map(function() { return []; });
     365
     366    function line(arcs, i) {
     367      arcs.forEach(function(a) {
     368        if (a < 0) a = ~a;
     369        var o = indexesByArc[a];
     370        if (o) o.push(i);
     371        else indexesByArc[a] = [i];
     372      });
     373    }
     374
     375    function polygon(arcs, i) {
     376      arcs.forEach(function(arc) { line(arc, i); });
     377    }
     378
     379    function geometry(o, i) {
     380      if (o.type === "GeometryCollection") o.geometries.forEach(function(o) { geometry(o, i); });
     381      else if (o.type in geometryType) geometryType[o.type](o.arcs, i);
     382    }
     383
     384    var geometryType = {
     385      LineString: line,
     386      MultiLineString: polygon,
     387      Polygon: polygon,
     388      MultiPolygon: function(arcs, i) { arcs.forEach(function(arc) { polygon(arc, i); }); }
     389    };
     390
     391    objects.forEach(geometry);
     392
     393    for (var i in indexesByArc) {
     394      for (var indexes = indexesByArc[i], m = indexes.length, j = 0; j < m; ++j) {
     395        for (var k = j + 1; k < m; ++k) {
     396          var ij = indexes[j], ik = indexes[k], n;
     397          if ((n = neighbors[ij])[i = bisect(n, ik)] !== ik) n.splice(i, 0, ik);
     398          if ((n = neighbors[ik])[i = bisect(n, ij)] !== ij) n.splice(i, 0, ij);
     399        }
     400      }
     401    }
     402
     403    return neighbors;
     404  }
     405
     406  function compareArea(a, b) {
     407    return a[1][2] - b[1][2];
     408  }
     409
     410  function minAreaHeap() {
     411    var heap = {},
     412        array = [],
     413        size = 0;
     414
     415    heap.push = function(object) {
     416      up(array[object._ = size] = object, size++);
     417      return size;
     418    };
     419
     420    heap.pop = function() {
     421      if (size <= 0) return;
     422      var removed = array[0], object;
     423      if (--size > 0) object = array[size], down(array[object._ = 0] = object, 0);
     424      return removed;
     425    };
     426
     427    heap.remove = function(removed) {
     428      var i = removed._, object;
     429      if (array[i] !== removed) return; // invalid request
     430      if (i !== --size) object = array[size], (compareArea(object, removed) < 0 ? up : down)(array[object._ = i] = object, i);
     431      return i;
     432    };
     433
     434    function up(object, i) {
     435      while (i > 0) {
     436        var j = ((i + 1) >> 1) - 1,
     437            parent = array[j];
     438        if (compareArea(object, parent) >= 0) break;
     439        array[parent._ = i] = parent;
     440        array[object._ = i = j] = object;
     441      }
     442    }
     443
     444    function down(object, i) {
     445      while (true) {
     446        var r = (i + 1) << 1,
     447            l = r - 1,
     448            j = i,
     449            child = array[j];
     450        if (l < size && compareArea(array[l], child) < 0) child = array[j = l];
     451        if (r < size && compareArea(array[r], child) < 0) child = array[j = r];
     452        if (j === i) break;
     453        array[child._ = i] = child;
     454        array[object._ = i = j] = object;
     455      }
     456    }
     457
     458    return heap;
     459  }
     460
     461  function presimplify(topology, triangleArea) {
     462    var absolute = transformAbsolute(topology.transform),
     463        relative = transformRelative(topology.transform),
     464        heap = minAreaHeap();
     465
     466    if (!triangleArea) triangleArea = cartesianTriangleArea;
     467
     468    topology.arcs.forEach(function(arc) {
     469      var triangles = [],
     470          maxArea = 0,
     471          triangle,
     472          i,
     473          n,
     474          p;
     475
     476      // To store each point’s effective area, we create a new array rather than
     477      // extending the passed-in point to workaround a Chrome/V8 bug (getting
     478      // stuck in smi mode). For midpoints, the initial effective area of
     479      // Infinity will be computed in the next step.
     480      for (i = 0, n = arc.length; i < n; ++i) {
     481        p = arc[i];
     482        absolute(arc[i] = [p[0], p[1], Infinity], i);
     483      }
     484
     485      for (i = 1, n = arc.length - 1; i < n; ++i) {
     486        triangle = arc.slice(i - 1, i + 2);
     487        triangle[1][2] = triangleArea(triangle);
     488        triangles.push(triangle);
     489        heap.push(triangle);
     490      }
     491
     492      for (i = 0, n = triangles.length; i < n; ++i) {
     493        triangle = triangles[i];
     494        triangle.previous = triangles[i - 1];
     495        triangle.next = triangles[i + 1];
     496      }
     497
     498      while (triangle = heap.pop()) {
     499        var previous = triangle.previous,
     500            next = triangle.next;
     501
     502        // If the area of the current point is less than that of the previous point
     503        // to be eliminated, use the latter's area instead. This ensures that the
     504        // current point cannot be eliminated without eliminating previously-
     505        // eliminated points.
     506        if (triangle[1][2] < maxArea) triangle[1][2] = maxArea;
     507        else maxArea = triangle[1][2];
     508
     509        if (previous) {
     510          previous.next = next;
     511          previous[2] = triangle[2];
     512          update(previous);
     513        }
     514
     515        if (next) {
     516          next.previous = previous;
     517          next[0] = triangle[0];
     518          update(next);
     519        }
     520      }
     521
     522      arc.forEach(relative);
     523    });
     524
     525    function update(triangle) {
     526      heap.remove(triangle);
     527      triangle[1][2] = triangleArea(triangle);
     528      heap.push(triangle);
     529    }
     530
     531    return topology;
     532  }
     533
     534  var version = "1.6.26";
     535
     536  exports.version = version;
     537  exports.mesh = mesh;
     538  exports.meshArcs = meshArcs;
     539  exports.merge = merge;
     540  exports.mergeArcs = mergeArcs;
     541  exports.feature = feature;
     542  exports.neighbors = neighbors;
     543  exports.presimplify = presimplify;
     544
     545}));

  • _plugins_/d3js/trunk/javascript/topojson.min.js

    r96616 r96999  
    1 !function(){function t(n,t){function r(t){var r,e=n.arcs[0>t?~t:t],o=e[0];return n.transform?(r=[0,0],e.forEach(function(n){r[0]+=n[0],r[1]+=n[1]})):r=e[e.length-1],0>t?[r,o]:[o,r]}function e(n,t){for(var r in n){var e=n[r];delete t[e.start],delete e.start,delete e.end,e.forEach(function(n){o[0>n?~n:n]=1}),f.push(e)}}var o={},i={},u={},f=[],c=-1;return t.forEach(function(r,e){var o,i=n.arcs[0>r?~r:r];i.length<3&&!i[1][0]&&!i[1][1]&&(o=t[++c],t[c]=r,t[e]=o)}),t.forEach(function(n){var t,e,o=r(n),f=o[0],c=o[1];if(t=u[f])if(delete u[t.end],t.push(n),t.end=c,e=i[c]){delete i[e.start];var a=e===t?t:t.concat(e);i[a.start=t.start]=u[a.end=e.end]=a}else i[t.start]=u[t.end]=t;else if(t=i[c])if(delete i[t.start],t.unshift(n),t.start=f,e=u[f]){delete u[e.end];var s=e===t?t:e.concat(t);i[s.start=e.start]=u[s.end=t.end]=s}else i[t.start]=u[t.end]=t;else t=[n],i[t.start=f]=u[t.end=c]=t}),e(u,i),e(i,u),t.forEach(function(n){o[0>n?~n:n]||f.push([n])}),f}function r(n,r,e){function o(n){var t=0>n?~n:n;(s[t]||(s[t]=[])).push({i:n,g:a})}function i(n){n.forEach(o)}function u(n){n.forEach(i)}function f(n){"GeometryCollection"===n.type?n.geometries.forEach(f):n.type in l&&(a=n,l[n.type](n.arcs))}var c=[];if(arguments.length>1){var a,s=[],l={LineString:i,MultiLineString:u,Polygon:u,MultiPolygon:function(n){n.forEach(u)}};f(r),s.forEach(arguments.length<3?function(n){c.push(n[0].i)}:function(n){e(n[0].g,n[n.length-1].g)&&c.push(n[0].i)})}else for(var h=0,p=n.arcs.length;p>h;++h)c.push(h);return{type:"MultiLineString",arcs:t(n,c)}}function e(r,e){function o(n){n.forEach(function(t){t.forEach(function(t){(f[t=0>t?~t:t]||(f[t]=[])).push(n)})}),c.push(n)}function i(n){return l(u(r,{type:"Polygon",arcs:[n]}).coordinates[0])>0}var f={},c=[],a=[];return e.forEach(function(n){"Polygon"===n.type?o(n.arcs):"MultiPolygon"===n.type&&n.arcs.forEach(o)}),c.forEach(function(n){if(!n._){var t=[],r=[n];for(n._=1,a.push(t);n=r.pop();)t.push(n),n.forEach(function(n){n.forEach(function(n){f[0>n?~n:n].forEach(function(n){n._||(n._=1,r.push(n))})})})}}),c.forEach(function(n){delete n._}),{type:"MultiPolygon",arcs:a.map(function(e){var o=[];if(e.forEach(function(n){n.forEach(function(n){n.forEach(function(n){f[0>n?~n:n].length<2&&o.push(n)})})}),o=t(r,o),(n=o.length)>1)for(var u,c=i(e[0][0]),a=0;n>a;++a)if(c===i(o[a])){u=o[0],o[0]=o[a],o[a]=u;break}return o})}}function o(n,t){return"GeometryCollection"===t.type?{type:"FeatureCollection",features:t.geometries.map(function(t){return i(n,t)})}:i(n,t)}function i(n,t){var r={type:"Feature",id:t.id,properties:t.properties||{},geometry:u(n,t)};return null==t.id&&delete r.id,r}function u(n,t){function r(n,t){t.length&&t.pop();for(var r,e=s[0>n?~n:n],o=0,i=e.length;i>o;++o)t.push(r=e[o].slice()),a(r,o);0>n&&f(t,i)}function e(n){return n=n.slice(),a(n,0),n}function o(n){for(var t=[],e=0,o=n.length;o>e;++e)r(n[e],t);return t.length<2&&t.push(t[0].slice()),t}function i(n){for(var t=o(n);t.length<4;)t.push(t[0].slice());return t}function u(n){return n.map(i)}function c(n){var t=n.type;return"GeometryCollection"===t?{type:t,geometries:n.geometries.map(c)}:t in l?{type:t,coordinates:l[t](n)}:null}var a=v(n.transform),s=n.arcs,l={Point:function(n){return e(n.coordinates)},MultiPoint:function(n){return n.coordinates.map(e)},LineString:function(n){return o(n.arcs)},MultiLineString:function(n){return n.arcs.map(o)},Polygon:function(n){return u(n.arcs)},MultiPolygon:function(n){return n.arcs.map(u)}};return c(t)}function f(n,t){for(var r,e=n.length,o=e-t;o<--e;)r=n[o],n[o++]=n[e],n[e]=r}function c(n,t){for(var r=0,e=n.length;e>r;){var o=r+e>>>1;n[o]<t?r=o+1:e=o}return r}function a(n){function t(n,t){n.forEach(function(n){0>n&&(n=~n);var r=o[n];r?r.push(t):o[n]=[t]})}function r(n,r){n.forEach(function(n){t(n,r)})}function e(n,t){"GeometryCollection"===n.type?n.geometries.forEach(function(n){e(n,t)}):n.type in u&&u[n.type](n.arcs,t)}var o={},i=n.map(function(){return[]}),u={LineString:t,MultiLineString:r,Polygon:r,MultiPolygon:function(n,t){n.forEach(function(n){r(n,t)})}};n.forEach(e);for(var f in o)for(var a=o[f],s=a.length,l=0;s>l;++l)for(var h=l+1;s>h;++h){var p,g=a[l],v=a[h];(p=i[g])[f=c(p,v)]!==v&&p.splice(f,0,v),(p=i[v])[f=c(p,g)]!==g&&p.splice(f,0,g)}return i}function s(n,t){function r(n){i.remove(n),n[1][2]=t(n),i.push(n)}var e=v(n.transform),o=m(n.transform),i=g();return t||(t=h),n.arcs.forEach(function(n){for(var u,f,c=[],a=0,s=0,l=n.length;l>s;++s)f=n[s],e(n[s]=[f[0],f[1],1/0],s);for(var s=1,l=n.length-1;l>s;++s)u=n.slice(s-1,s+2),u[1][2]=t(u),c.push(u),i.push(u);for(var s=0,l=c.length;l>s;++s)u=c[s],u.previous=c[s-1],u.next=c[s+1];for(;u=i.pop();){var h=u.previous,p=u.next;u[1][2]<a?u[1][2]=a:a=u[1][2],h&&(h.next=p,h[2]=u[2],r(h)),p&&(p.previous=h,p[0]=u[0],r(p))}n.forEach(o)}),n}function l(n){for(var t,r=-1,e=n.length,o=n[e-1],i=0;++r<e;)t=o,o=n[r],i+=t[0]*o[1]-t[1]*o[0];return.5*i}function h(n){var t=n[0],r=n[1],e=n[2];return Math.abs((t[0]-e[0])*(r[1]-t[1])-(t[0]-r[0])*(e[1]-t[1]))}function p(n,t){return n[1][2]-t[1][2]}function g(){function n(n,t){for(;t>0;){var r=(t+1>>1)-1,o=e[r];if(p(n,o)>=0)break;e[o._=t]=o,e[n._=t=r]=n}}function t(n,t){for(;;){var r=t+1<<1,i=r-1,u=t,f=e[u];if(o>i&&p(e[i],f)<0&&(f=e[u=i]),o>r&&p(e[r],f)<0&&(f=e[u=r]),u===t)break;e[f._=t]=f,e[n._=t=u]=n}}var r={},e=[],o=0;return r.push=function(t){return n(e[t._=o]=t,o++),o},r.pop=function(){if(!(0>=o)){var n,r=e[0];return--o>0&&(n=e[o],t(e[n._=0]=n,0)),r}},r.remove=function(r){var i,u=r._;if(e[u]===r)return u!==--o&&(i=e[o],(p(i,r)<0?n:t)(e[i._=u]=i,u)),u},r}function v(n){if(!n)return y;var t,r,e=n.scale[0],o=n.scale[1],i=n.translate[0],u=n.translate[1];return function(n,f){f||(t=r=0),n[0]=(t+=n[0])*e+i,n[1]=(r+=n[1])*o+u}}function m(n){if(!n)return y;var t,r,e=n.scale[0],o=n.scale[1],i=n.translate[0],u=n.translate[1];return function(n,f){f||(t=r=0);var c=(n[0]-i)/e|0,a=(n[1]-u)/o|0;n[0]=c-t,n[1]=a-r,t=c,r=a}}function y(){}var d={version:"1.6.19",mesh:function(n){return u(n,r.apply(this,arguments))},meshArcs:r,merge:function(n){return u(n,e.apply(this,arguments))},mergeArcs:e,feature:o,neighbors:a,presimplify:s};"function"==typeof define&&define.amd?define(d):"object"==typeof module&&module.exports?module.exports=d:this.topojson=d}();
     1!function(n,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports):"function"==typeof define&&define.amd?define(["exports"],t):t(n.topojson=n.topojson||{})}(this,function(n){"use strict";function t(){}function r(n){if(!n)return t;var r,e,o=n.scale[0],i=n.scale[1],u=n.translate[0],f=n.translate[1];return function(n,t){t||(r=e=0),n[0]=(r+=n[0])*o+u,n[1]=(e+=n[1])*i+f}}function e(n){if(!n)return t;var r,e,o=n.scale[0],i=n.scale[1],u=n.translate[0],f=n.translate[1];return function(n,t){t||(r=e=0);var c=Math.round((n[0]-u)/o),a=Math.round((n[1]-f)/i);n[0]=c-r,n[1]=a-e,r=c,e=a}}function o(n,t){for(var r,e=n.length,o=e-t;o<--e;)r=n[o],n[o++]=n[e],n[e]=r}function i(n,t){for(var r=0,e=n.length;e>r;){var o=r+e>>>1;n[o]<t?r=o+1:e=o}return r}function u(n,t){return"GeometryCollection"===t.type?{type:"FeatureCollection",features:t.geometries.map(function(t){return f(n,t)})}:f(n,t)}function f(n,t){var r={type:"Feature",id:t.id,properties:t.properties||{},geometry:c(n,t)};return null==t.id&&delete r.id,r}function c(n,t){function e(n,t){t.length&&t.pop();for(var r,e=l[0>n?~n:n],i=0,u=e.length;u>i;++i)t.push(r=e[i].slice()),s(r,i);0>n&&o(t,u)}function i(n){return n=n.slice(),s(n,0),n}function u(n){for(var t=[],r=0,o=n.length;o>r;++r)e(n[r],t);return t.length<2&&t.push(t[0].slice()),t}function f(n){for(var t=u(n);t.length<4;)t.push(t[0].slice());return t}function c(n){return n.map(f)}function a(n){var t=n.type;return"GeometryCollection"===t?{type:t,geometries:n.geometries.map(a)}:t in h?{type:t,coordinates:h[t](n)}:null}var s=r(n.transform),l=n.arcs,h={Point:function(n){return i(n.coordinates)},MultiPoint:function(n){return n.coordinates.map(i)},LineString:function(n){return u(n.arcs)},MultiLineString:function(n){return n.arcs.map(u)},Polygon:function(n){return c(n.arcs)},MultiPolygon:function(n){return n.arcs.map(c)}};return a(t)}function a(n,t){function r(t){var r,e=n.arcs[0>t?~t:t],o=e[0];return n.transform?(r=[0,0],e.forEach(function(n){r[0]+=n[0],r[1]+=n[1]})):r=e[e.length-1],0>t?[r,o]:[o,r]}function e(n,t){for(var r in n){var e=n[r];delete t[e.start],delete e.start,delete e.end,e.forEach(function(n){o[0>n?~n:n]=1}),f.push(e)}}var o={},i={},u={},f=[],c=-1;return t.forEach(function(r,e){var o,i=n.arcs[0>r?~r:r];i.length<3&&!i[1][0]&&!i[1][1]&&(o=t[++c],t[c]=r,t[e]=o)}),t.forEach(function(n){var t,e,o=r(n),f=o[0],c=o[1];if(t=u[f])if(delete u[t.end],t.push(n),t.end=c,e=i[c]){delete i[e.start];var a=e===t?t:t.concat(e);i[a.start=t.start]=u[a.end=e.end]=a}else i[t.start]=u[t.end]=t;else if(t=i[c])if(delete i[t.start],t.unshift(n),t.start=f,e=u[f]){delete u[e.end];var s=e===t?t:e.concat(t);i[s.start=e.start]=u[s.end=t.end]=s}else i[t.start]=u[t.end]=t;else t=[n],i[t.start=f]=u[t.end=c]=t}),e(u,i),e(i,u),t.forEach(function(n){o[0>n?~n:n]||f.push([n])}),f}function s(n){return c(n,l.apply(this,arguments))}function l(n,t,r){function e(n){var t=0>n?~n:n;(s[t]||(s[t]=[])).push({i:n,g:c})}function o(n){n.forEach(e)}function i(n){n.forEach(o)}function u(n){"GeometryCollection"===n.type?n.geometries.forEach(u):n.type in l&&(c=n,l[n.type](n.arcs))}var f=[];if(arguments.length>1){var c,s=[],l={LineString:o,MultiLineString:i,Polygon:i,MultiPolygon:function(n){n.forEach(i)}};u(t),s.forEach(arguments.length<3?function(n){f.push(n[0].i)}:function(n){r(n[0].g,n[n.length-1].g)&&f.push(n[0].i)})}else for(var h=0,p=n.arcs.length;p>h;++h)f.push(h);return{type:"MultiLineString",arcs:a(n,f)}}function h(n){var t=n[0],r=n[1],e=n[2];return Math.abs((t[0]-e[0])*(r[1]-t[1])-(t[0]-r[0])*(e[1]-t[1]))}function p(n){for(var t,r=-1,e=n.length,o=n[e-1],i=0;++r<e;)t=o,o=n[r],i+=t[0]*o[1]-t[1]*o[0];return i/2}function v(n){return c(n,g.apply(this,arguments))}function g(n,t){function r(n){n.forEach(function(t){t.forEach(function(t){(o[t=0>t?~t:t]||(o[t]=[])).push(n)})}),i.push(n)}function e(t){return Math.abs(p(c(n,{type:"Polygon",arcs:[t]}).coordinates[0]))}var o={},i=[],u=[];return t.forEach(function(n){"Polygon"===n.type?r(n.arcs):"MultiPolygon"===n.type&&n.arcs.forEach(r)}),i.forEach(function(n){if(!n._){var t=[],r=[n];for(n._=1,u.push(t);n=r.pop();)t.push(n),n.forEach(function(n){n.forEach(function(n){o[0>n?~n:n].forEach(function(n){n._||(n._=1,r.push(n))})})})}}),i.forEach(function(n){delete n._}),{type:"MultiPolygon",arcs:u.map(function(t){var r,i=[];if(t.forEach(function(n){n.forEach(function(n){n.forEach(function(n){o[0>n?~n:n].length<2&&i.push(n)})})}),i=a(n,i),(r=i.length)>1)for(var u,f,c=1,s=e(i[0]);r>c;++c)(u=e(i[c]))>s&&(f=i[0],i[0]=i[c],i[c]=f,s=u);return i})}}function y(n){function t(n,t){n.forEach(function(n){0>n&&(n=~n);var r=o[n];r?r.push(t):o[n]=[t]})}function r(n,r){n.forEach(function(n){t(n,r)})}function e(n,t){"GeometryCollection"===n.type?n.geometries.forEach(function(n){e(n,t)}):n.type in f&&f[n.type](n.arcs,t)}var o={},u=n.map(function(){return[]}),f={LineString:t,MultiLineString:r,Polygon:r,MultiPolygon:function(n,t){n.forEach(function(n){r(n,t)})}};n.forEach(e);for(var c in o)for(var a=o[c],s=a.length,l=0;s>l;++l)for(var h=l+1;s>h;++h){var p,v=a[l],g=a[h];(p=u[v])[c=i(p,g)]!==g&&p.splice(c,0,g),(p=u[g])[c=i(p,v)]!==v&&p.splice(c,0,v)}return u}function d(n,t){return n[1][2]-t[1][2]}function m(){function n(n,t){for(;t>0;){var r=(t+1>>1)-1,o=e[r];if(d(n,o)>=0)break;e[o._=t]=o,e[n._=t=r]=n}}function t(n,t){for(;;){var r=t+1<<1,i=r-1,u=t,f=e[u];if(o>i&&d(e[i],f)<0&&(f=e[u=i]),o>r&&d(e[r],f)<0&&(f=e[u=r]),u===t)break;e[f._=t]=f,e[n._=t=u]=n}}var r={},e=[],o=0;return r.push=function(t){return n(e[t._=o]=t,o++),o},r.pop=function(){if(!(0>=o)){var n,r=e[0];return--o>0&&(n=e[o],t(e[n._=0]=n,0)),r}},r.remove=function(r){var i,u=r._;if(e[u]===r)return u!==--o&&(i=e[o],(d(i,r)<0?n:t)(e[i._=u]=i,u)),u},r}function E(n,t){function o(n){f.remove(n),n[1][2]=t(n),f.push(n)}var i=r(n.transform),u=e(n.transform),f=m();return t||(t=h),n.arcs.forEach(function(n){var r,e,c,a,s=[],l=0;for(e=0,c=n.length;c>e;++e)a=n[e],i(n[e]=[a[0],a[1],1/0],e);for(e=1,c=n.length-1;c>e;++e)r=n.slice(e-1,e+2),r[1][2]=t(r),s.push(r),f.push(r);for(e=0,c=s.length;c>e;++e)r=s[e],r.previous=s[e-1],r.next=s[e+1];for(;r=f.pop();){var h=r.previous,p=r.next;r[1][2]<l?r[1][2]=l:l=r[1][2],h&&(h.next=p,h[2]=r[2],o(h)),p&&(p.previous=h,p[0]=r[0],o(p))}n.forEach(u)}),n}var M="1.6.26";n.version=M,n.mesh=s,n.meshArcs=l,n.merge=v,n.mergeArcs=g,n.feature=u,n.neighbors=y,n.presimplify=E});
Note: See TracChangeset for help on using the changeset viewer.