30:T675,class TinyQueue { constructor(data = [], compare = defaultCompare) { this.data = data; this.length = this.data.length; this.compare = compare; if (this.length > 0) { for (let i = (this.length >> 1) - 1; i >= 0; i--) this._down(i); } } push(item) { this.data.push(item); this._up(this.length++); } pop() { if (this.length === 0) return undefined; const top = this.data[0]; const bottom = this.data.pop(); if (--this.length > 0) { this.data[0] = bottom; this._down(0); } return top; } peek() { return this.data[0]; } _up(pos) { const {data, compare} = this; const item = data[pos]; while (pos > 0) { const parent = (pos - 1) >> 1; const current = data[parent]; if (compare(item, current) >= 0) break; data[pos] = current; pos = parent; } data[pos] = item; } _down(pos) { const {data, compare} = this; const halfLength = this.length >> 1; const item = data[pos]; while (pos < halfLength) { let bestChild = (pos << 1) + 1; // initially it is the left child const right = bestChild + 1; if (right < this.length && compare(data[right], data[bestChild]) < 0) { bestChild = right; } if (compare(data[bestChild], item) >= 0) break; data[pos] = data[bestChild]; pos = bestChild; } data[pos] = item; } } 31:Tc40,function polylabel(polygon, precision, debug) { precision = precision || 1.0; // is this a single polygon or a list of them? -- call recursively on lists if (isNaN(polygon[0][0][0])) { var bestpoint = polylabel(polygon[0], precision, debug); for (p = 1; p < polygon.length; p++) { const thispoint = polylabel(polygon[p], precision, debug); if (thispoint.distance > bestpoint.distance) { bestpoint = thispoint; } } return bestpoint; } // find the bounding box of the outer ring var minX, minY, maxX, maxY; for (var i = 0; i < polygon[0].length; i++) { var p = polygon[0][i]; if (!i || p[0] < minX) minX = p[0]; if (!i || p[1] < minY) minY = p[1]; if (!i || p[0] > maxX) maxX = p[0]; if (!i || p[1] > maxY) maxY = p[1]; } var width = maxX - minX; var height = maxY - minY; var cellSize = Math.min(width, height); var h = cellSize / 2; if (cellSize === 0) { var degeneratePoleOfInaccessibility = [minX, minY]; degeneratePoleOfInaccessibility.distance = 0; return degeneratePoleOfInaccessibility; } // a priority queue of cells in order of their "potential" (max distance to polygon) var cellQueue = new TinyQueue(undefined, compareMax); // cover polygon with initial cells for (var x = minX; x < maxX; x += cellSize) { for (var y = minY; y < maxY; y += cellSize) { cellQueue.push(new Cell(x + h, y + h, h, polygon)); } } // take centroid as the first best guess var bestCell = getCentroidCell(polygon); // special case for rectangular polygons var bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, polygon); if (bboxCell.d > bestCell.d) bestCell = bboxCell; var numProbes = cellQueue.length; while (cellQueue.length) { // pick the most promising cell from the queue var cell = cellQueue.pop(); // update the best cell if we found a better one if (cell.d > bestCell.d) { bestCell = cell; if (debug) console.log('found best %d after %d probes', Math.round(1e4 * cell.d) / 1e4, numProbes); } // do not drill down further if there's no chance of a better solution if (cell.max - bestCell.d <= precision) continue; // split the cell into four cells h = cell.h / 2; cellQueue.push(new Cell(cell.x - h, cell.y - h, h, polygon)); cellQueue.push(new Cell(cell.x + h, cell.y - h, h, polygon)); cellQueue.push(new Cell(cell.x - h, cell.y + h, h, polygon)); cellQueue.push(new Cell(cell.x + h, cell.y + h, h, polygon)); numProbes += 4; } if (debug) { console.log('num probes: ' + numProbes); console.log('best distance: ' + bestCell.d); console.log('best point: [' + bestCell.x + ', ' + bestCell.y + ']'); console.log(polygon); } var poleOfInaccessibility = [bestCell.x, bestCell.y]; poleOfInaccessibility.distance = bestCell.d; return poleOfInaccessibility; }32:[] 2e:{"title":"Copy of PolyLabel","cells":[{"id":0,"value":"md`# Copy of PolyLabel\nFrom https://github.com/mapbox/polylabel \nAdded code to deal with disconnected regions, which are lists of polygons. This is needed for some datasets such as the US County map data at https://unpkg.com/us-atlas@3/counties-albers-10m.json. \nUses TinyQueue from https://github.com/mourner/tinyqueue\n`","pinned":true,"hidden":false,"mode":"ojs"},{"id":14,"value":"$30","pinned":true,"hidden":false,"mode":"ojs"},{"id":19,"value":"function defaultCompare(a, b) {\n return a < b ? -1 : a > b ? 1 : 0;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":6,"value":"$31","pinned":true,"hidden":false,"mode":"ojs"},{"id":36,"value":"function compareMax(a, b) {\n return b.max - a.max;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":42,"value":"function Cell(x, y, h, polygon) {\n this.x = x; // cell center x\n this.y = y; // cell center y\n this.h = h; // half the cell size\n this.d = pointToPolygonDist(x, y, polygon); // distance from cell center to polygon\n this.max = this.d + this.h * Math.SQRT2; // max distance to polygon within a cell\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":43,"value":"// signed distance from point to polygon outline (negative if point is outside)\nfunction pointToPolygonDist(x, y, polygon) {\n var inside = false;\n var minDistSq = Infinity;\n\n for (var k = 0; k < polygon.length; k++) {\n var ring = polygon[k];\n\n for (var i = 0, len = ring.length, j = len - 1; i < len; j = i++) {\n var a = ring[i];\n var b = ring[j];\n\n if ((a[1] > y !== b[1] > y) &&\n (x < (b[0] - a[0]) * (y - a[1]) / (b[1] - a[1]) + a[0])) inside = !inside;\n\n minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b));\n }\n }\n\n return minDistSq === 0 ? 0 : (inside ? 1 : -1) * Math.sqrt(minDistSq);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":45,"value":"// get polygon centroid\nfunction getCentroidCell(polygon) {\n var area = 0;\n var x = 0;\n var y = 0;\n var points = polygon[0];\n\n for (var i = 0, len = points.length, j = len - 1; i < len; j = i++) {\n var a = points[i];\n var b = points[j];\n var f = a[0] * b[1] - b[0] * a[1];\n x += (a[0] + b[0]) * f;\n y += (a[1] + b[1]) * f;\n area += f * 3;\n }\n if (area === 0) return new Cell(points[0][0], points[0][1], 0, polygon);\n return new Cell(x / area, y / area, 0, polygon);\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":47,"value":"// get squared distance from a point to a segment\nfunction getSegDistSq(px, py, a, b) {\n\n var x = a[0];\n var y = a[1];\n var dx = b[0] - x;\n var dy = b[1] - y;\n\n if (dx !== 0 || dy !== 0) {\n\n var t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);\n\n if (t > 1) {\n x = b[0];\n y = b[1];\n\n } else if (t > 0) {\n x += dx * t;\n y += dy * t;\n }\n }\n\n dx = px - x;\n dy = py - y;\n\n return dx * dx + dy * dy;\n}","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}