28:null 29:["$","title",null,{"children":"Polylabel & centroid | Fil | Observable"}] 2e:T43d,{ const context = DOM.context2d(800, 110), path = d3.geoPath().context(context); context.beginPath(); path({ type: "Polygon", coordinates: polygon }); context.fillStyle = "#eee"; context.fill(); context.stroke(); context.strokeStyle = "red"; context.beginPath(); path({ type: "LineString", coordinates: [label2, label3] }); context.stroke(); context.beginPath(); path.pointRadius(label.distance)({ type: "Point", coordinates: label }); context.stroke(); context.beginPath(); context.strokeStyle = "green"; path.pointRadius(label.distance)({ type: "Point", coordinates: label2 }); context.stroke(); context.beginPath(); context.fillStyle = "red"; path.pointRadius(5)({ type: "Point", coordinates: label }); context.fill(); context.beginPath(); context.fillStyle = "green"; path.pointRadius(5)({ type: "Point", coordinates: label2 }); context.fill(); context.beginPath(); context.fillStyle = "steelblue"; path.pointRadius(5)({ type: "Point", coordinates: label2.centroid }); context.fill(); return context.canvas; }2f:T1257,polylabel = { return function polylabel(polygon, precision, debug) { precision = precision || 1.0; // 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 Queue(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); } var poleOfInaccessibility = [bestCell.x, bestCell.y]; poleOfInaccessibility.distance = bestCell.d; return poleOfInaccessibility; }; function compareMax(a, b) { return b.max - a.max; } function Cell(x, y, h, polygon) { this.x = x; // cell center x this.y = y; // cell center y this.h = h; // half the cell size this.d = pointToPolygonDist(x, y, polygon); // distance from cell center to polygon this.max = this.d + this.h * Math.SQRT2; // max distance to polygon within a cell } // signed distance from point to polygon outline (negative if point is outside) function pointToPolygonDist(x, y, polygon) { var inside = false; var minDistSq = Infinity; for (var k = 0; k < polygon.length; k++) { var ring = polygon[k]; for (var i = 0, len = ring.length, j = len - 1; i < len; j = i++) { var a = ring[i]; var b = ring[j]; if ( a[1] > y !== b[1] > y && x < ((b[0] - a[0]) * (y - a[1])) / (b[1] - a[1]) + a[0] ) inside = !inside; minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b)); } } return minDistSq === 0 ? 0 : (inside ? 1 : -1) * Math.sqrt(minDistSq); } // get polygon centroid function getCentroidCell(polygon) { var area = 0; var x = 0; var y = 0; var points = polygon[0]; for (var i = 0, len = points.length, j = len - 1; i < len; j = i++) { var a = points[i]; var b = points[j]; var f = a[0] * b[1] - b[0] * a[1]; x += (a[0] + b[0]) * f; y += (a[1] + b[1]) * f; area += f * 3; } if (area === 0) return new Cell(points[0][0], points[0][1], 0, polygon); return new Cell(x / area, y / area, 0, polygon); } // get squared distance from a point to a segment function getSegDistSq(px, py, a, b) { var x = a[0]; var y = a[1]; var dx = b[0] - x; var dy = b[1] - y; if (dx !== 0 || dy !== 0) { var t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy); if (t > 1) { x = b[0]; y = b[1]; } else if (t > 0) { x += dx * t; y += dy * t; } } dx = px - x; dy = py - y; return dx * dx + dy * dy; } }30:T1595,polylabelCentroid = { return function polylabel(polygon, precision, debug, centroidWeight) { precision = precision || 1.0; centroidWeight = centroidWeight || 0; // 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 Queue(undefined, compareMax); var centroidCell = getCentroidCell(polygon); // take centroid as the first best guess var bestCell = centroidCell; // 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, centroidCell)); } } // the fitness function to be maximized function fitness(cell) { return cell.d - cell.distanceToCentroid * centroidWeight; } // special case for rectangular polygons var bboxCell = new Cell( minX + width / 2, minY + height / 2, 0, polygon, centroidCell ); if (fitness(bboxCell) > fitness(bestCell)) 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 (fitness(cell) > fitness(bestCell)) { 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, centroidCell) ); cellQueue.push( new Cell(cell.x + h, cell.y - h, h, polygon, centroidCell) ); cellQueue.push( new Cell(cell.x - h, cell.y + h, h, polygon, centroidCell) ); cellQueue.push( new Cell(cell.x + h, cell.y + h, h, polygon, centroidCell) ); numProbes += 4; } if (debug) { console.log('num probes: ' + numProbes); console.log('best distance: ' + bestCell.d); } var poleOfInaccessibility = [bestCell.x, bestCell.y]; poleOfInaccessibility.distance = bestCell.d; poleOfInaccessibility.centroid = [centroidCell.x, centroidCell.y]; return poleOfInaccessibility; }; function compareMax(a, b) { return b.max - a.max; } function Cell(x, y, h, polygon, centroidCell) { this.x = x; // cell center x this.y = y; // cell center y this.h = h; // half the cell size this.d = pointToPolygonDist(x, y, polygon); // distance from cell center to polygon this.distanceToCentroid = centroidCell ? pointToPointDist(this, centroidCell) : 0; this.max = this.d + this.h * Math.SQRT2; // max distance to polygon within a cell } // distance between two cells function pointToPointDist(cellA, cellB) { var dx = cellB.x - cellA.x; var dy = cellB.y - cellA.y; return Math.sqrt(dx * dx + dy * dy); } // signed distance from point to polygon outline (negative if point is outside) function pointToPolygonDist(x, y, polygon) { var inside = false; var minDistSq = Infinity; for (var k = 0; k < polygon.length; k++) { var ring = polygon[k]; for (var i = 0, len = ring.length, j = len - 1; i < len; j = i++) { var a = ring[i]; var b = ring[j]; if ( a[1] > y !== b[1] > y && x < ((b[0] - a[0]) * (y - a[1])) / (b[1] - a[1]) + a[0] ) inside = !inside; minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b)); } } return minDistSq === 0 ? 0 : (inside ? 1 : -1) * Math.sqrt(minDistSq); } // get polygon centroid function getCentroidCell(polygon) { var area = 0; var x = 0; var y = 0; var points = polygon[0]; for (var i = 0, len = points.length, j = len - 1; i < len; j = i++) { var a = points[i]; var b = points[j]; var f = a[0] * b[1] - b[0] * a[1]; x += (a[0] + b[0]) * f; y += (a[1] + b[1]) * f; area += f * 3; } if (area === 0) return new Cell(points[0][0], points[0][1], 0, polygon); return new Cell(x / area, y / area, 0, polygon); } // get squared distance from a point to a segment function getSegDistSq(px, py, a, b) { var x = a[0]; var y = a[1]; var dx = b[0] - x; var dy = b[1] - y; if (dx !== 0 || dy !== 0) { var t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy); if (t > 1) { x = b[0]; y = b[1]; } else if (t > 0) { x += dx * t; y += dy * t; } } dx = px - x; dy = py - y; return dx * dx + dy * dy; } }31:[] 2c:{"id":"de13dcd035b7ebbd","slug":null,"title":"Polylabel & centroid","thumbnail":"6d511e93b7a29c1eb7202065eb508d942c390ac3008ef36b90adde26fef082ce","access_level":"unlisted","create_time":"$D2019-07-29T12:25:42.269Z","update_time":"$D2020-06-18T12:31:48.564Z","view_time":null,"first_public_time":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"da2a32154638c457","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":"starter_2024"},"version":120,"publish_version":120,"role":null,"authored":false,"authors":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null}],"members":[{"type":"individual","id":"45a379fcfcb14253","login":"fil","name":"Fil","avatar_url":"https://avatars-next.observableusercontent.com/d5b1777907117a2bdf2a07eb98600d7a9beb21639fde42b9753e95c88c7731a6","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Polylabel & centroid","cells":[{"id":0,"value":"md`# Polylabel & centroid\n\nRef. https://github.com/mapbox/polylabel issue [#63](https://github.com/mapbox/polylabel/pull/63).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":91,"value":"md`\n- red: polylabel locus\n- blue: centroid\n- green: polylabel \"gravitated towards centroid\"\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":30,"value":"$2e","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"Queue = require(\"tinyqueue\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":23,"value":"polygon = [\n [\n [10, 10],\n [300, 10],\n [410, 10],\n [700, 10],\n [700, 100],\n [410, 100],\n [410, 20],\n [250, 90],\n [10, 90],\n [10, 10]\n ]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":21,"value":"label = polylabel(polygon)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":64,"value":"label2 = polylabelCentroid(polygon, 1, false, 0.1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":114,"value":"label3 = polylabelCentroid(polygon, 1, false, -0.1)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":13,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":62,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":27,"value":"d3 = require(\"d3-geo\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2d:"$2c:body"