Testing @mourner’s polylabel with D3.
Orange dot = centroid ; white dot = normal polylabel; green dot = elliptic polylabel.
In this variant from Polylabel with D3 we set different scales for x and y, so as to find the “largest ellipse” to accomodate “horizontal” text labels (the ellipse ratio would match the text bbox ratio).
Built with blockbuilder.org, base map by @mbostock.
<!DOCTYPE html>
<meta charset="utf-8">
<style>
.stroke {
fill: none;
stroke: #000;
stroke-width: 3px;
}
.fill {
fill: #fff;
}
.graticule {
fill: none;
stroke: #777;
stroke-width: 0.5px;
stroke-opacity: 0.5;
}
.land {
fill: #ccc;
}
.boundary {
fill: none;
stroke: #555;
stroke-width: 0.5px;
}
</style>
<svg width="960" height="484"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://d3js.org/d3-geo-projection.v2.min.js"></script>
<script src="https://d3js.org/topojson.v1.min.js"></script>
<script src="polylabel.js"></script>
<script>
var svg = d3.select("svg"),
width = +svg.attr("width"),
height = +svg.attr("height");
var projection = d3.geoRobinson()
.rotate([-10.5,0])
.translate([width / 2, height / 2])
.precision(0.1);
var graticule = d3.geoGraticule();
var path = d3.geoPath()
.projection(projection);
var defs = svg.append("defs");
defs.append("path")
.datum({type: "Sphere"})
.attr("id", "sphere")
.attr("d", path);
defs.append("clipPath")
.attr("id", "clip")
.append("use")
.attr("xlink:href", "#sphere");
svg.append("use")
.attr("class", "stroke")
.attr("xlink:href", "#sphere");
svg.append("use")
.attr("class", "fill")
.attr("xlink:href", "#sphere");
svg.append("path")
.datum(graticule)
.attr("class", "graticule")
.attr("clip-path", "url(#clip)")
.attr("d", path);
var lines = svg.append("g"),
circles = svg.append("g");
console.clear()
d3.json("https://unpkg.com/visionscarto-world-atlas@0.0.6/world/110m.json", function(error, world) {
if (error) throw error;
if (true)
svg.insert("path", ".graticule")
.datum(topojson.feature(world, world.objects.countries))
.attr("class", "land")
.attr("clip-path", "url(#clip)")
.attr("d", path);
if (true)
svg.insert("path", ".graticule")
.datum(topojson.mesh(world, world.objects.countries, function(a, b) { return a !== b; }))
.attr("class", "boundary")
.attr("clip-path", "url(#clip)")
.attr("d", path);
var w = topojson.feature(world, world.objects.countries);
w.features.forEach(function(d, i){
// get the larget sub-polygon's coordinates
var coord = d.geometry.coordinates;
if (d.geometry.type == 'MultiPolygon') {
var u = d3.scan(
coord.map(function(p){
return -d3.polygonArea(p[0]);
})
);
coord = coord[u];
}
var o = projection(d3.geoCentroid(d));
var n = polylabel([coord[0].map(projection)]);
// Find the best *ellipse* with x/y ratio = alpha
var alpha = 4;
var m = polylabel([coord[0].map(projection).map(function(d){
d[0] /= alpha;
return d;
})]);
m[0] *= alpha;
lines.append('line')
.attr('x1', o[0])
.attr('y1', o[1])
.attr('x2', n[0])
.attr('y2', n[1])
.attr('stroke', 'green')
.attr('stroke-width', 1);
lines.append('line')
.attr('x1', o[0])
.attr('y1', o[1])
.attr('x2', m[0])
.attr('y2', m[1])
.attr('stroke', 'green')
.attr('stroke-width', 1);
circles.append('circle')
.attr('cx', o[0])
.attr('cy', o[1])
.attr('r', 2)
.attr('stroke', 'orange')
.attr('fill', 'yellow')
.attr('stroke-width', 1);
circles.append('circle')
.attr('cx', n[0])
.attr('cy', n[1])
.attr('r', 2)
.attr('stroke', 'green')
.attr('fill', 'white')
.attr('stroke-width', 1);
circles.append('circle')
.attr('cx', m[0])
.attr('cy', m[1])
.attr('r', 3)
.attr('stroke', 'green')
.attr('fill', 'green');
});
});
</script>
(function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.polylabel = f()}})(function(){var define,module,exports;return (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
'use strict';
var Queue = require('tinyqueue');
module.exports = polylabel;
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;
// a priority queue of cells in order of their "potential" (max distance to polygon)
var cellQueue = new Queue(null, 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);
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);
}
return [bestCell.x, bestCell.y];
}
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 (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;
}
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;
}
},{"tinyqueue":2}],2:[function(require,module,exports){
'use strict';
module.exports = TinyQueue;
function TinyQueue(data, compare) {
if (!(this instanceof TinyQueue)) return new TinyQueue(data, compare);
this.data = data || [];
this.length = this.data.length;
this.compare = compare || defaultCompare;
if (data) for (var i = Math.floor(this.length / 2); i >= 0; i--) this._down(i);
}
function defaultCompare(a, b) {
return a < b ? -1 : a > b ? 1 : 0;
}
TinyQueue.prototype = {
push: function (item) {
this.data.push(item);
this.length++;
this._up(this.length - 1);
},
pop: function () {
var top = this.data[0];
this.data[0] = this.data[this.length - 1];
this.length--;
this.data.pop();
this._down(0);
return top;
},
peek: function () {
return this.data[0];
},
_up: function (pos) {
var data = this.data,
compare = this.compare;
while (pos > 0) {
var parent = Math.floor((pos - 1) / 2);
if (compare(data[pos], data[parent]) < 0) {
swap(data, parent, pos);
pos = parent;
} else break;
}
},
_down: function (pos) {
var data = this.data,
compare = this.compare,
len = this.length;
while (true) {
var left = 2 * pos + 1,
right = left + 1,
min = pos;
if (left < len && compare(data[left], data[min]) < 0) min = left;
if (right < len && compare(data[right], data[min]) < 0) min = right;
if (min === pos) return;
swap(data, min, pos);
pos = min;
}
}
};
function swap(data, i, j) {
var tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
},{}]},{},[1])(1)
});