2c:null 2d:["$","title",null,{"children":"Strategies for triangle-packing maps. | Benjamin Schmidt | Observable"}] 32:T631,md`# Strategies for triangle-packing maps. I've been thinking a lot about [webgl cartography](https://observablehq.com/collection/@bmschmidt/webgl-cartography). To do it, I need a binary format for **projected, triangulated polygons or multipolygons**. The goal here is instant webgl-based mapping; but as I'll show in a later notebook, it has some impressive advantages for other thematic cartography as well. In this notebook I won't actually draw using webgl; instead, we'll use Canvas to explore some features of triangles. The basic context here is that Webgl can only draw triangles, not complex polygons. To draw real map objects, they must be turned into collections of triangles. The [earcut](https://github.com/mapbox/earcut) library by [@mourner](https://observablehq.com/@mourner) does this in a format designed for webgl; with each polygon represented as a series of *coordinates* and *vertexes.* Earcut isn't perfect, but I haven't encountered any errors. ## Earcut triangulations. More about that in a second, but here are triangulated versions of some countries in the Mercator projection. A few things I learned here: 1. The earcut algorithm works from the outside of polygons in, simplifying out pointy bits as triangles. 2. Enclaves (as in in South Africa and Italy) produce larger triangles early in the process. 3. A single vertex may be reused many times. Especially in countries like Egypt and Iraq that have one or two straight-line sides. 4. Triangulations do not add new points; they just connect existing points. ## Earcut triangulation of ${country} `33:T7bc,md`## Tracking vertices and points efficiently This distinction between *coordinates* and vertices is important because it means that points may be shared across many different countries; and that a single country may use the same coordinates several times. The basic idea of triangles as put out by earcut is to support **instanced rendering.** That means giving the coordinates of every point in the dataset in one object, and then listing the vertices of each triangle in another. To use space efficiently, *coordinates* take up 8 bytes apiece--two 4-byte floats. Vertices are smaller. They can be encoded as a variety of different types of floats, depending how many distinct vertices there are. Basic WebGL supports 8-byte or 16-byte unsigned integer types, which puts a ceiling of ${2**16} bytes on the number of points in any mesh; but almost all webgl implementations support the \`OES_element_index_uint\` extension which allows 32-byte unsigned integers. We'll design a format assuming 32-byte indices are allowed. If you store a separate set of coordinates for each polygon, you can frequently encode them as 8 or 16-byte floats. But if you share a **single** set of coordinates, you end up needing to allocate 32-bytes per vertex if you want to address the entire space. Below is a chart that shows: * from **left to right**; the index of points. * from **bottom to top**; the absolute index of the point. If a point is used several times--for instance if it's at the border of three countries--later uses will find the earlier occurrence. As you can see, the default ordering here is alphabetical by country name. Andorra, Algeria, the Arab Republic of Egypt, etc. The places where a single polygon goes from outside to the inside show up as a series of leaning lines; places where a country reuses a point from an earlier polygon have points that go back down on the y axis. Below I'll draw the points (**not** the triangles) on a map at the same time. `34:Tc6a,md`# Reducing size with duplication, meshes, and offsets. This kind of mesh storage provides some complicated tradeoffs in storage sizes. The original geojson here is **${mb(raw_geojson.length)}**. ## Optimization 1: Use binary floats, not text. If we stored the triangulation directly as float32 pairs, the coordinate data alone has ${d3.format(",")(size_stats.n_vertices)} vertices, which would take ${mb(size_stats.n_vertices*8)} to store. That's an improvement just on its own, because json is a lousy way way to store floats! ## Optimization 2: Store coordinates and vertices separately. But we can instead the unduplicated individual coordinates first, which takes ${mb(size_stats.bytes_in_coords)} to store each of the ${size_stats.n_coords} points, and then store the vertices separately for each row. If we stored all those as uint32 arrays, that would take ${mb(size_stats.maximum_vertex_size)}, or **${mb(size_stats.maximum_vertex_size + size_stats.bytes_in_coords)}** total. ## Optimization 3: Use offsets to store vertex indices in smaller integer types. But that's using 32-byte integers for every vertex. Since most coordinates are adjacent to each other, we can pack it down further by encoding the vertex positions as an *offset* from the first position in that country. Webgl is happy to read from a buffer this way and to accept vertices with different uint types, so it still requires no calculations before passing it to a buffer. If all the points are within 255 of the lowest value (${size_stats.counts[8]} of the features here), we can store it as a 8-byte int; if there are less than ${2**16} (${size_stats.counts[16]} of the features here), we can store it as an 16-byte int. Only ${size_stats.counts[32]} features here require a full 32 bytes for their vertices. That brings us down to ${mb(size_stats.bytes_in_vertices)} to store the vertices, or **${mb(size_stats.bytes_in_vertices + size_stats.bytes_in_coords)}** for the vertices and the coordinates together. Adding the metadata in, we're at ${mb(country_feather.bytes.length)}. Different topologies will produce very different results. The majority of points in a world map like this are coastlines that exist only in a single feature's polygons. I'm especially interested in US counties and sub-county level shapes; those have considerably more shared points. ### Remaining possible optimizations To achieve truly minimal sizes, you'd want to do two things. 1. Sort the countries in a way that preserves adjacencies. In this test set, sorting just be region knocks a bit of size off; a more elaborate sorting might do better. 2. Strategically duplicate some coordinates where the topology is weird. For instance, France shares borders with Suriname and Brazil as well as with European countries. If its South American points were written into the coordinate buffer in a different location. This seems like it would probably be useful. ## Is this the highest possible compression for geodata? No! Topojson is far more efficient. But topojson requires computation to unpack arcs; the goal here is to provide a byte-perfect representation that can be shipped straight to a GPU. `35:T739,{ restart const n_points = country_feather.n_coords const y_scale = d3.scaleLinear().domain([0, n_points]).range([height*.75 -20, 0]) var ctx = document.getElementById("canvas2").getContext("2d"); var ctx2 = document.getElementById("canvas3").getContext("2d"); ctx.clearRect(0, 0, width, width) ctx2.clearRect(0, 0, width, width) ctx.moveTo(0, 0) const continents = d3.scaleOrdinal(d3.schemeDark2) const ps = [] let i = [0] for (let row of country_feather.t) { const r = new TriRow(row, country_feather) let f if (row.coord_resolution >= 8) { f = "rgba(100, 20, 20, 1)" } else { f = "rgba(20, 100, 20, 1)" } f = continents(row.REGION_WB) const name = row.NAME ps.push([i, name, f, "LABEL"]) for (let triangle_set of r.iter_triangles(true)) { for (let triangle of triangle_set) { ps.push([i++, triangle, "" + f, undefined]) } // ctx.arc(100, 75, 00, 0, 2 * Math.PI); // ctx.stroke(); } } const x_scale = d3.scaleLinear().domain([0, ps.length]).range([0, width]) const mapscale = d3.geoIdentity().scale(.1).translate([width*.33, height*.33]) // ctx.fillStyle = i = 0; for (let [x, y, f, escape] of ps) { if (escape == "LABEL") { ctx.clearRect(0, height*.75 - 20, width, 30) ctx.fillStyle = f ctx.fillText(y, x_scale(i), height*.75-5) continue } if (Math.random() < 1.) { ctx.fillStyle = f ctx.beginPath() ctx.arc(x_scale(x), y_scale(y), 1, 0, 2 * Math.PI); ctx.fill(); const [x_, y_] = mapscale(country_feather.coord(y)) // return (x_scale(ps[200000][0])) ctx2.fillStyle = f ctx2.beginPath() ctx2.arc(x_, y_, .1, 0, 2 * Math.PI); ctx2.fill(); } if (i++ % 66 == 0) { yield i } } }36:Ta25,md` ## Triangles for the GPU Pushing this kind of data to the GPU requires working with typed arrays. One goal for quick Webgl programming is never to touch or copy numbers in Javascript; instead, you pass array buffers straight through to the GPU. [Apache Arrow](https://arrow.apache.org/) provides a great format for this. Its file format--called 'feather'--can be loaded instantly as a single ArrayBuffer into javascript with no parsing. (Large geojson objects take a while to parse!) and related chunks of that--representing a single cartographic feature--can be send to the GPU. Rather than storing map data as JSON, we can store each feature as a single row in a feather dataframe. (This is the approach taken as well by libraries such as geopandas in python or \`sf\` in R.) I also add a few pre-computed columns here: 1. The feature's bounding box; 2. The feature's area in pixels; 3. The feature's centroid. With these three features, you can do lots of fun stuff in webgl that's not possible when rendering conventional maps. The vertex information occupies a column that simply stores binary data. I'm using the file suffix "trifeather" because there's [live discussion here of a full-feature geo-arrow spec](https://github.com/geopandas/geo-arrow-spec) including polygon descriptions (not triangulations) in arrow. What I'm offering is more narrow in its application, but performant. The steps performed in this notebook are: ## Steps 1. Project a feature collection from lat-long into a coordinate space. I find it useful to project into a high scale. 2. (Optionally) Clip polygons to the sphere using 'polygon-clipping.' 3. Triangulate using earcut in that coordinate space. 4. Generate the unduplicated set of coordinates as a single buffer of float32 pairs. 3. Push the triangle coordinates and the feature vertex identifiers into javascript typed arrays in the format webgl will expect (float32 for coordinates, and one of uint8, uint16, or uint32 for vertex identifiers.) 4. Infer types on all fields in the properties field of the geojson items, including coercion to dictionaries for string entries with low cardinality, which can save. 5. Convert the whole thing to an Apache Arrow feather format file. All binary entries are represented as feather's \`binary\` type, which takes a Uint8 view of whatever the actual data is. 6. Make it downloadable. All of these steps are bundled into the \`TriFeather\` class below. \`TriFeather.from_geojson\` creates a new triangulated file; or \`new TriFeather(array_buffer)\` creates an instance from a pre-loaded array. `37:T8de,country = { // This code draws the triangulated earcut versions. while (true) { const country = d3.shuffle(cycle_countries)[0] const ctx = d3.select("#canvas1").node().getContext("2d") ctx.moveTo(0, 0) ctx.clearRect(0, 0, width, height) for (let row of country_feather.t) { if ((row.NAME) == (country)) { if (row.coord_resolution === null) { continue } const manhattan = row const bounds_buffer = new Float32Array(new Uint8Array(row.bounds).buffer) const [xmin, ymin, xmax, ymax] = d3.range(4).map(i => bounds_buffer[i]) let w = (xmax-xmin)*10 let h = (ymax-ymin)*10 while (d3.max([w, h]) > width) { w *= .75 h *= .75 } d3.select("#canvas1").attr("width", w).attr("height",width*1.25) const x = d3.scaleLinear().domain([xmin, xmax]).range([0, w]) const y = d3.scaleLinear().domain([ymin, ymax]).range([0, h]) const n_vertices = row.vertices.length * 8 / row.coord_resolution; const vertices = new DataView(row.vertices.buffer, row.vertices.byteOffset, row.vertices.byteLength) // const verts = new B(new Uint8Array(row.vertices).buffer) ctx.fillStyle = "blue"; const stride = row.coord_resolution/8 let getter = i => vertices[`getUint${row.coord_resolution}`](i*stride, true) + row.coord_buffer_offset const offset = row.coord_buffer_offset const project = ([x_, y_]) => { return [x(x_), y(y_)] } for (let i=0; i < n_vertices; i+=3) { ctx.fillStyle = d3.interpolateRainbow(i/n_vertices) // Draw triangles one at a time. ctx.beginPath(); const [a, b, c] = [0, 1, 2].map(j => country_feather.coord(getter(i+j))) ctx.moveTo(...project(a)) ctx.lineTo(...project(b)) ctx.lineTo(...project(c)) ctx.lineTo(...project(a)) ctx.stroke(); ctx.fill(); yield country } // //return vertices } } for (let i of d3.range(30 * 5)) { // stop at the end. yield country } } }38:T2f1a,class TriFeather { constructor(bytes) { this.bytes = bytes this.t = arrow.Table.from(bytes) } get n_coords() { this.coord_buffer; return this._n_coords; } get coord_buffer() { if (this._coord_buffer) { return this._coord_buffer } const d = this.t.get(0).vertices; this._coord_bytes = d.byteOffset this._n_coords = (d.byteLength/4/2) this._coord_buffer = new DataView(d.buffer, d.byteOffset, d.byteLength) return this._coord_buffer } static polygon_to_triangles(polygon) { // Actually perform the earcut work on a polygon. const el_pos = [] const coords = polygon.flat(2) const vertices = earcut(...Object.values(earcut.flatten(polygon))) return { coords, vertices } } static from_feature_collection(feature_collection, projection, options = {dictionary_threshold: .75, clip_to_sphere: false}) { if (projection === undefined) {throw "Must define a projection"} // feature_collections: a (parsed) geoJSON object. // projection: a d3.geoProjection instance; // eg, d3.geoMollweide().transform([10, 20]) // options: const properties = new Map() // Stores the number of bytes used for the coordinates. const coord_resolutions = [null] const coord_buffer_offset = [null] // centroids let you have fun with shapes. Store x and y separately. const centroids = [[null], [null]] const bounds = [null] // Storing areas makes it possible to weight centroids. const areas = [null] let i = -1; const path = d3.geoPath() let clip_shape; let projected = d3.geoProject(feature_collection, projection) if (options.clip_to_sphere) { clip_shape = d3.geoProject({"type": "Sphere"}, projection) for (let feature of projected.features) { const new_coords = clip.intersection(feature.coordinates, clip_shape.coordinates) if (projected.type == "Polygon" && typeof(new_coords[0][0][0] != "numeric")) { projected.type = "MultiPolygon" } feature.coordinates = new_coords } } const {indices, points} = this.lookup_map_and_coord_buffer(projected) const coord_indices = indices; const coord_codes = points; // Stash the vertices in the first item of the array. const vertices = [new Uint8Array(coord_codes.buffer)] properties.set("id", ["Dummy feather row"]) i = 0; for (let feature of projected.features) { // start at one; the first slot is reserved for caching the full // feature list i++; properties.get("id")[i] = feature.id || `Feature_no_${i}` for (let [k, v] of Object.entries(feature.properties)) { if (!properties.get(k)) {properties.set(k, [])} properties.get(k)[i] = v } const projected = feature.geometry const [x, y] = path.centroid(projected) const bbox = new Float32Array(path.bounds(projected).flat()) centroids[0][i] = x; centroids[1][i] = y areas[i] = path.area(projected) bounds[i] = bbox let loc_coordinates; if (projected === null) { console.warn("Error on", projected) coord_resolutions[i] = null vertices[i] = null continue } else if (projected.type == "Polygon") { loc_coordinates = [projected.coordinates] } else if (projected.type == "MultiPolygon") { loc_coordinates = projected.coordinates } else { throw "All elements must be polygons or multipolgyons." } let all_coords = [] let all_vertices = [] for (let polygon of loc_coordinates) { const { coords, vertices } = TriFeather.polygon_to_triangles(polygon); // Allow coordinate lookups by treating them as a single 64-bit int. const bigint_coords = new BigInt64Array(new Float32Array(coords.flat(3)).buffer); // Reduce to the indices of the master lookup table. const lookup_points = vertices.map(vx => coord_indices.get(bigint_coords[vx])) all_vertices.push(...lookup_points) } const [start, end] = d3.extent(all_vertices) const diff = end - start coord_buffer_offset[i] = (start) // Normalize the vertices around the lowest element. // Allows some vertices to be stored at a lower resolution. for (let j=0; j 200/array.length) {continue} // Only check a subsample for speed. Try // to get about 200 instances for each row. if (el === undefined || el === null) { continue } if (typeof(el) === "string") { strings += 1 seen.add(el) } else if (typeof(el) === "number") { if (el % 1 > 0) { floats += 1 } else if (isFinite(el)) { max_int = Math.max(Math.abs(el), max_int) } else { } } else { throw `No behavior defined for type ${typeof(el)}` } } if ( strings > 0 ) { // moderate overlap if (seen.length < strings.length * .75) { return new arrow.Dictionary(new arrow.Utf8(), new arrow.Int32()) } else { return new arrow.Utf8() } } if (floats > 0) { return new arrow.Float32() } if (Math.abs(max_int) < 2**8) { return new arrow.Int8() } if (Math.abs(max_int) < 2**16) { return new arrow.Int16() } if (Math.abs(max_int) < 2**32) { return new arrow.Int32() } else { return new arrow.Int64() } } coord(ix) { // NB this manually specifies little-endian, although // Arrow can potentially support big-endian frames under // certain (future?) circumstances. return [ this.coord_buffer.getFloat32(ix*4*2, true), this.coord_buffer.getFloat32(ix*2*4 + 4, true) ] } static pack_binary(els) { const { Builder, Binary } = arrow; const binaryBuilder = Builder.new({ type: new Binary(), nullValues: [null, undefined], highWaterMark: 2**16 }); for (let el of els) { binaryBuilder.append(el) } return binaryBuilder.finish().toVector() } bind_to_regl(regl) { this.regl = regl this.element_handler = new Map(); // Elements can't share buffers (?) so just use a map. this.regl_coord_buffer = regl.buffer( {data: this.t.get(0).vertices, type: "float", usage: "static"}) this.prepare_features_for_regl() } prepare_features_for_regl() { this.features = [] const {t, features, regl, element_handler, regl_coord_buffer} = this; // Start at 1, not zero, to avoid the dummy. for (let ix = 1; ix this.coord(i)[0])), y: d3.extent(d3.range(this.n_coords).map(i => this.coord(i)[1])), } return this._bbox } *[Symbol.iterator]() { for (let feature of this.features) { yield feature } } static lookup_map_and_coord_buffer (geojson) { const all_coordinates = new Float32Array(geojson.features.filter(d => d.geometry).map(d => d.geometry.coordinates).flat(4)) const feature_collection = geojson const codes = new BigInt64Array(all_coordinates.buffer) const indices = new Map() for (let code of codes) { if (!indices.has(code)) { indices.set(code, indices.size) } } const points = new BigInt64Array(indices.size) for (let [k, v] of indices.entries()) { points[v] = k } return {indices, points} } }39:[] 30:{"id":"c8efa5987d47ea5e","slug":"pre-triangulated-feather","title":"Strategies for triangle-packing maps.","thumbnail":"48c04a997fbeddb7d251ca01625f84dccf6a688cb25a45346b3af3751c2ebcfe","access_level":"public","create_time":"$D2020-11-25T19:57:29.008Z","update_time":"$D2020-12-25T18:29:35.916Z","view_time":null,"first_public_time":"$D2020-11-30T16:16:08.056Z","has_unpublished_edits":null,"fork":{"id":"0d3c1fd47eca5bfc","slug":"a-binary-file-format-for-projected-triangulated-shapefile","title":"A binary file format for projected, triangulated, shapefiles with metadata.","owner":{"id":"18bbeceb36c8f564","login":"bmschmidt","name":"Benjamin Schmidt"}},"stars":15,"starred":false,"owner":{"type":"team","id":"18bbeceb36c8f564","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":"starter_2024","bio":"Digital Humanist. Manhattan-based."},"version":4141,"publish_version":4141,"role":null,"authored":false,"authors":[{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null,"bio":"Digital Humanist. Manhattan-based."}],"members":[{"type":"individual","id":"33354ca265b21f01","login":"bmschmidt","name":"Benjamin Schmidt","avatar_url":"https://avatars-next.observableusercontent.com/addc2adb5ec95cc72a64820e4a08488bad5d48d95a895eef85a45b136ed66792","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":4,"collection":{"id":"dd0419b5d6424c58","slug":"webgl-cartography","title":"WebGL cartography","owner":{"id":"18bbeceb36c8f564","login":"bmschmidt","name":"Benjamin Schmidt"}},"type":"notebook","body":{"titling":"auto","title":"Strategies for triangle-packing maps.","cells":[{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2858,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4056,"value":"md`Data source is [Natural Earth](https://www.naturalearthdata.com/), converted to geojson by [Marty Nafford on github.](https://github.com/martynafford/natural-earth-geojson/blob/master/10m/cultural/ne_10m_admin_0_sovereignty.json)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3627,"value":"viewof cycle_countries = checkbox({title: \"Cycle Countries\", options: [\"India\", \"South Africa\", \"Mexico\", \"Denmark\", \"Greece\", \"Japan\", \"Iraq\", \"Kenya\", \"Italy\", \"Iran\", \"Egypt\"], value: [\"South Africa\", \"Japan\", \"Italy\", \"Egypt\"], \"description\": \"These are some countries that have interesting and recognizable shapes within a relatively constrained bounding box. Edit this cell if you want to see different countris than those listed here.\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3761,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3898,"value":"md`### Coordinate indices (y) against plot order (x)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3643,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3925,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4008,"value":"viewof sort_features = radio({title: \"Sort features by region?\", options: [\"Yes\", \"No\"], value: \"No\", \"description\": \"This makes little difference in the test data here\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3967,"value":"size_stats = {\n const bytes_in_coords = country_feather.t.get(0).vertices.length\n let bytes_in_vertices = 0\n let n_vertices = 0\n const n_points_in_geojson = geojson.features.map(d => d.geometry.coordinates).flat(10)/2\n const n_coords = bytes_in_coords / 8\n let counts = {8: 0, 16: 0, 32: 0}\n for (let row of country_feather.t) {\n const {coord_resolution, vertices} = row\n if (coord_resolution === null) {\n continue \n } else {\n counts[coord_resolution] += 1\n n_vertices += vertices.length * 8 / coord_resolution\n bytes_in_vertices += vertices.length\n }\n }\n const maximum_vertex_size = 4*n_vertices;\n return {counts, n_points_in_geojson, n_coords, bytes_in_vertices, n_vertices, bytes_in_coords, maximum_vertex_size}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3647,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3610,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3921,"value":"md`## A view of the data\n\nHere's a view of the data using Arquero.\n\nOne thing I don't like about this format is that I don't have a good place to stash the binary coordinate data. Currently I just throw it into the first row of the feather frame. Probably it should live as a metadata entry on the feather table; but the feather js library has essentially no documentation and I can't figure out how to create a metadata field on a table.\n\nNote all the binary arrays here. The 'bounds' field, for instance, shows up as 16 Uint8 entries; to actually read the coordinates, you need to access the underlying array as a Float32 type and read the four entries. The vertices is especially complicated, because the data type is references in the 'coord_resolution' field. The \\`coord_resolution\\` field here describes how many bytes each entry takes.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3916,"value":"aq.fromArrow(country_feather.t).view()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4137,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3914,"value":"import {aq, op} from '@uwdata/arquero'","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3950,"value":"mb = function(string) {\n if (string < 1024 * 1024) {\n return d3.format(\",.3\")(string/1024) + \"KB\"\n }\n return d3.format(\",.3\")(string/1024/1024) + \"MB\"\n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3814,"value":"md`# Determining unique coordinates.\n\nTo store a list of the coordinates, we need some structure to identify which points we have already seen. Since these are pairs of floats, you can't use them as keys to a javscript map. But we can simply take a 64-byte view of the coordinate pairs and use *those* as the keys for a lookup; essentially, pretending each coordinate pair is a single item without any copies.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2165,"value":"function lookup_map_and_coord_buffer (geojson) {\n const all_coordinates = new Float32Array(geojson.features.filter(d => d.geometry).map(d => d.geometry.coordinates).flat(4)) \n const feature_collection = geojson\n const codes = new BigInt64Array(all_coordinates.buffer)\n const indices = new Map()\n for (let code of codes) {\n if (!indices.has(code)) {\n indices.set(code, indices.size) \n }\n }\n const points = new BigInt64Array(indices.size)\n for (let [k, v] of indices.entries()) {\n points[v] = k\n }\n return {indices, points}\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1688,"value":"download_button(country_feather)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2676,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2754,"value":"height = width * .66","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1992,"value":"md`# Canvas plot\n\nSanity check--slowly draw out the triangles using Canvas.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2048,"value":"viewof clip_to_sphere = radio({\"title\": \"Clip to the sphere?\", options: [\"yes\", \"no\"], value: \"no\", description: \"Clip all polygons to the sphere using clip-polygon? Not necessary for most projections, but will be for some more interrupted ones.\"})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2038,"value":"import { radio, checkbox } from '@jashkenas/inputs'","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1694,"value":"md`# Data Converter\n\nYou can convert any geojson file into this format and download it using the button below; just change the source.\n\nYou can also live-transform by importing the feature_collection_to_feather_frame function below.\n`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2515,"value":"filename = url.split(\"/\").reverse()[0].replace(\".json\", \"\").replace(\".geojson\", \"\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2506,"value":"url = 'https://raw.githubusercontent.com/martynafford/natural-earth-geojson/master/50m/cultural/ne_50m_admin_0_countries_lakes.json'//'https://cors-anywhere.herokuapp.com/eric.clst.org/assets/wiki/uploads/Stuff/gz_2010_us_050_00_500k.json'//'https://raw.githubusercontent.com/martynafford/natural-earth-geojson/master/110m/cultural/ne_110m_admin_0_countries_lakes.json'","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1844,"value":"raw_geojson = d3.text(url)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1672,"value":"geojson = {\n const geojson = JSON.parse(raw_geojson)\n // For the mapping I'm doing of the world with distortion,\n // it is preferable to remove exclaves like Alaska, the portions of Russia past -180 longitude,\n // and French Guinea\n if (sort_features == \"Yes\") {\n geojson.features.sort((a, b) => (a.properties.REGION_WB > b.properties.REGION_WB ? -1 : 1))\n }\n return geojson\n geojson.features = geojson.features.filter(d => d.properties.SOVEREIGNT !== \"Antarctica\")\n for (let feature of geojson.features) {\n if (false) {//feature.properties.GEOUNIT.match(/United States of America|United Kingdom|France|Russia/)) { \n console.log(feature.properties.GEOUNIT)\n reduce_to_largest_elements(feature) \n }\n }\n return geojson \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1809,"value":"function reduce_to_largest_elements(feature, n = 1) {\n const coords = feature.geometry.coordinates.sort((a, b) => +b[0].length - +a[0].length)\n feature.geometry.coordinates = feature.geometry.coordinates.slice(0, n)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1759,"value":"//projection = d3.geoGingery().scale(300).lobes(6).rotate([98, -40, 0])//d3.geoInterruptedMollweide().scale(5000)//d3.geoMercator().scale(2).translate([-0, 0])//d3.geoInterruptedHomolosine().translate([0, 0]).scale(.2)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1680,"value":"country_feather = TriFeather.from_feature_collection(geojson, projection, {clip_to_sphere: clip_to_sphere == \"yes\"})\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1081,"value":"arrow = require('apache-arrow@2.0.0')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2420,"value":"download_button(country_feather)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3894,"value":"country_feather.coord(100)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4114,"value":"country_feather.bytes.byteLength","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1375,"value":"function download_button(feather) {return html`\n

${filename} (${mb(feather.bytes.length)})

\n ${DOM.download(new Blob([feather.bytes.buffer], {type: \"application/octet-stream\"}), `${filename}.gleofeather`, `Download ${feather.t.length} row file)`)}`}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4118,"value":"country_feather.t.serialize()","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1086,"value":"md`# Functions to turn geoJSON into feather frames.`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2011,"value":"clip = require('polygon-clipping')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2616,"value":"projection = d3.geoMercator().scale(1000)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3539,"value":"class TriRow {\n constructor(row, parent) {\n this.row = row\n this.t = parent\n }\n\n \n *iter_triangles(indices = false) {\n const {row, t} = this\n const n_vertices = row.vertices.length * 8 / row.coord_resolution;\n const vertices = new DataView(row.vertices.buffer, row.vertices.byteOffset, row.vertices.byteLength)\n const stride = row.coord_resolution/8\n if (row.coord_resolution === null) {\n return \n }\n let getter = i => vertices[`getUint${row.coord_resolution}`](i*stride, true) + row.coord_buffer_offset\n const offset = row.coord_buffer_offset\n for (let i=0; i < n_vertices; i+=3) {\n // Draw triangles one at a time.\n if (indices) {\n yield [0, 1, 2].map(j => getter(i+j))\n } else {\n yield [0, 1, 2].map(j => t.coord(getter(i+j)))\n }\n }\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2549,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4094,"value":"{\n return {\n x: d3.extent(d3.range(this.n_coords).map(i => this.coord(i)[0])),\n y: d3.extent(d3.range(this.n_coords).map(i => this.coord(i)[1])),\n }\n \n \n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4104,"value":"d3.extent([[1,2], [3,4], [5, 6, 7]])","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4099,"value":"country_feather.n_coords","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"earcut = require(\"earcut\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"d3 = require(\"d3-geo-projection\", \"d3-fetch\", \"d3-geo\", \"d3-array\", \"d3\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2135,"value":"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1"}} 31:"$30:body"