mapSpec
worldMapImage.img
pixelTopology = {
const emptyTopology = topojson.topology({type: "Sphere"});
const layers = Object.keys(mapSpec.layers).map(k => [k, { type: "GeometryCollection", geometries: [] }]);
emptyTopology.bbox = [0, 0, worldMapImage.width, worldMapImage.height];
if (topologyOptions.round) emptyTopology.bbox = emptyTopology.bbox.map(c => c * 4);
emptyTopology.objects = Object.fromEntries(layers);
emptyTopology.borders = Object.fromEntries(layers);
emptyTopology.properties = { ...topologyOptions, generated: +new Date() }
mutable pixelTopologyState = "empty";
yield emptyTopology;
const cancellationToken = getCancellationToken();
for (let downscaleFactor of downscaleFactors) {
if (cancellationToken.cancel) {
yield emptyTopology;
break;
}
const topology = await buildTopology(downscaleFactor, cancellationToken);
mutable pixelTopologyState = "working";
await pauseIfNeeded();
yield topology;
}
mutable pixelTopologyState = "done";
}
mutable pixelTopologyState = "empty"
pixelTopology.arcs.flat().length
{
const points = pixelTopology.arcs.flat();
const uniques = createPointHashSet(points.length);
points.forEach(p => uniques.add(p));
return uniques.values().length;
}
function populateMeta(topology) {
const geoPath = d3.geoPath(d3.geoIdentity());
const objectGeometries = Object.values(topology.objects).flatMap(gc => gc.geometries);
for (let geometry of objectGeometries) {
geometry.properties ??= {};
const feature = topojson.feature(topology, geometry);
geometry.properties.bbox = geoPath.bounds(feature).flat();
geometry.properties.area = Math.abs(d3.polygonArea(feature.geometry.coordinates[0]));
}
for (let [key, geometries] of Object.entries(_.groupBy(objectGeometries, g => g.properties.key))) {
geometries.forEach((g,i) => g.properties.id = (g.length == 1) ? key : `${key}-${i}`);
}
if (!topology.borders) return topology;
const borderBounds = new Map();
const borderGeometries = Object.values(topology.borders).flatMap(gc => gc.geometries);
for (let geometry of borderGeometries) {
geometry.properties ??= {};
const key = geometry.properties.key;
let bbox = borderBounds.get(key);
if (!bbox) {
const feature = topojson.feature(topology, geometry);
bbox = geoPath.bounds(feature).flat();
if (key !== undefined) borderBounds.set(key, bbox);
}
Object.assign(geometry.properties, { bbox, id: geometry.properties.key })
}
return topology;
}
pixelMapData.getGeoJson("land")
async function flattenTopology(topology) {
for (let [layerName, gc] of Object.entries(topology.objects)) {
const flat = topology.objects[layerName] = {
type: "GeometryCollection",
geometries: gc.geometries.flatMap(g => getChildrenFromMultiTopoJson(g))
};
debugger;
flat.geometries.forEach((g,i) => g.properties.id = `${layerName}-${i}`);
await pauseIfNeeded();
}
return topology;
}
pixelTopology
buildMapData(pixelTopology)
buildMapData(pixelTopology).getGeoJson("states", 2)
getChildrenFromMultiGeoJson
{
const topology = extractBorderTopology(pixelMapData.topology);
const fc = topojson.feature(topology, topology.objects.states);
return getChildrenFromMultiGeoJson(fc.features[0])
}
borders.land.geometries.filter(g => g.properties.isOutline)
async function buildTopology(downscaleFactor, cancellationToken) {
cancellationToken ??= getCancellationToken();
invalidation.then(() => cancellationToken.cancel = true);
const { bbox, polygons } = await tracePolygons(worldMapImage, colorTable, downscaleFactor, cancellationToken);
if (cancellationToken.cancel) return;
let topology = await buildTopologyFromPolygons(polygons, bbox);
if (cancellationToken.cancel) return;
await cleanArcs(topology);
if (cancellationToken.cancel) return;
await smoothTopology(topology);
if (cancellationToken.cancel) return;
await upscaleTopology(topology, downscaleFactor);
if (cancellationToken.cancel) return;
if (topologyOptions.extend) {
await extendTopology(topology);
if (cancellationToken.cancel) return;
}
await splitTopology(topology);
if (cancellationToken.cancel) return;
await cleanArcs(topology);
if (cancellationToken.cancel) return;
if (topologyOptions.round) {
const allCoords = new Set(topology.arcs.flat());
allCoords.forEach(c => { c[0] *= 4; c[1] *= 4; c[2] *= 4 });
topology.bbox = topology.bbox.map(c => c * 4);
}
topology = topojson.presimplify(topology);
if (cancellationToken.cancel) return;
if (topologyOptions.includeBorders) {
topology.borders = await extractBorderTopology(topology);
if (cancellationToken.cancel) return;
}
await populateMeta(topology);
if (cancellationToken.cancel) return;
topology.properties = { ...topologyOptions, generated: +new Date() }
return topology;
}
async function splitTopology(topology) {
const tracedGeometries = topology.objects.traced.geometries;
for (let [layerName, { prop }] of Object.entries(mapSpec.layers)) {
topology.objects[layerName] = {
type: "GeometryCollection",
geometries: []
};
const layerGeometries = topology.objects[layerName].geometries;
const mergeGroups = _.groupBy(tracedGeometries, g => g.properties[prop]);
for (let [key, tracedObjects] of Object.entries(mergeGroups)) {
const tracedColorNum = tracedObjects[0].properties.colorNum;
const key = mapSpec.provinceProps.get(tracedColorNum)[prop];
if (key !== undefined) {
const mergedObject = topojson.mergeArcs(topology, tracedObjects);
mergedObject.properties = { layer: layerName, key };
if (topologyOptions.flatten) {
layerGeometries.push(...getChildrenFromMultiTopoJson(mergedObject));
}
else {
layerGeometries.push(mergedObject);
}
}
}
await pauseIfNeeded();
}
topology = topojson.presimplify(topology);
delete topology.objects.traced;
return topology;
}
async function smoothTopology(topology) {
const getArcIndex = topology.getArcIndex = function(arcIndex) {
const isReversed = (arcIndex < 0);
arcIndex = (isReversed) ? ~arcIndex : arcIndex;
return { arcIndex, isReversed };
}
const getArc = topology.getArc = function(arcIndex) {
const { arcIndex: positiveArcIndex, isReversed } = getArcIndex(arcIndex);
const arc = topology.arcs[positiveArcIndex];
return { arc, arcIndex: positiveArcIndex, isReversed };
}
console.log(topology.bbox);
return topology;
buildJunctions(topology);
await pauseIfNeeded();
buildArcMeta(topology);
await pauseIfNeeded();
buildArcSegments(topology);
await pauseIfNeeded();
classifySegments(topology);
await pauseIfNeeded();
buildSmoothedArcs(topology);
await pauseIfNeeded();
topology.arcs = topology.smoothArcs;
/*
delete topology.smoothArcs;
delete topology.arcMeta;
delete topology.junctions;
delete topology.arcSegments;
delete topology.coordTypes;
delete topology.getArc;
delete topology.getArcIndex;
*/
debugger;
return topology;
}
{
const map = buildJunctions(pixelTopology);
return map.keys().map(k => [k, map.get(k)]);
}
function buildJunctions(topology) {
const junctionMeta = createPointHashMap(topology.arcs.length * 2);
for (let arcId = 0; arcId < topology.arcs.length; arcId++) {
const arc = topology.arcs[arcId];
for (let point of [arc[0], arc.at(-1)]) {
const usedBy = junctionMeta.maybeSet(point, new Set());
usedBy.add(arcId);
}
}
const junctionPoints = junctionMeta.keys();
const allJunctions = createPointHashSet(junctionPoints.length);
const sharedJunctions = createPointHashSet(junctionPoints.length);
const trueJunctions = createPointHashSet(junctionPoints.length);
for (let point of junctionPoints) {
allJunctions.add(point);
const usedBy = junctionMeta.get(point);
if (usedBy.size > 1) {
sharedJunctions.add(point);
}
else {
trueJunctions.add(point);
}
}
topology.junctions = allJunctions;
topology.sharedJunctions = sharedJunctions;
topology.trueJunctions = trueJunctions;
return topology;
}
function buildArcMeta(topology) {
const arcMeta = topology.arcMeta = [...new Array(topology.arcs.length)].map((e,i) => ({
usedBy: []
}));
for (let geometry of topology.objects.traced.geometries) {
let colorNum = geometry.properties.colorNum;
let rings = (geometry.type == "Polygon") ? geometry.arcs : geometry.arcs.flat();
for (let ringArcIds of rings) {
for (let arcId of ringArcIds) {
const { arcIndex } = topology.getArcIndex(arcId)
const meta = arcMeta[arcIndex];
meta.usedBy.push(colorNum);
}
}
}
for (let i = 0; i < topology.arcs.length; i++) {
const meta = arcMeta[i];
meta.isExterior = meta.usedBy.length == 1;
}
return topology;
}
function buildArcSegments(topology) {
const { COORD, SEGMENT, reverseDirections } = segmentConstants;
const arcSegments = topology.arcSegments = [];
function getArcCoords(arcIndex) {
let { arcIndex: positiveArcIndex, arc, isReversed } = topology.getArc(arcIndex);
if (isReversed) arc = arc.toReversed();
return { arcIndex: positiveArcIndex, arc };
}
function buildRingSegments(ringArcIndices) {
for (let i = 0; i < ringArcIndices.length; i++) {
const arcIndex = ringArcIndices[i];
const { arcIndex: positiveArcIndex, arc } = getArcCoords(arcIndex);
if (arcSegments[positiveArcIndex]) continue;
const { arc: prevArc } = getArcCoords(ringArcIndices[i-1] ?? ringArcIndices.at(-1));
const prevCoord = prevArc.at(-2);
const { arc: nextArc } = getArcCoords(ringArcIndices[i+1] ?? ringArcIndices[0]);
const nextCoord = nextArc[1];
arcSegments[arcIndex] = buildArcSegments(arc, prevCoord, nextCoord);
}
}
function buildArcSegments(arc, prevCoord, nextCoord) {
const segments = []
for (let coord of [...arc, nextCoord]) {
let segment = buildSegment(prevCoord, coord);
prevCoord = coord;
if (segment && segment.length > 0) segments.push(segment);
}
for (let i = 0; i < segments.length; i++) {
segments[i].prev = segments[i-1];
segments[i].next = segments[i+1];
}
segments.shift();
segments.pop();
return segments;
}
function buildSegment(fromCoord, toCoord) {
if (!fromCoord || !toCoord) return;
const axis = (fromCoord[0] != toCoord[0]) ? 0 : 1;
const delta = toCoord[axis] - fromCoord[axis];
const sign = Math.sign(delta);
const length = Math.abs(delta);
let direction;
if (axis == 0) direction = (sign == 1) ? "e" : "w";
if (axis == 1) direction = (sign == 1) ? "s" : "n";
return { fromCoord, toCoord, length, sign, axis, direction };
}
for (let geometry of topology.objects.traced.geometries) {
const arcs = (geometry.type == "Polygon") ? [geometry.arcs] : geometry.arcs;
for (let ring of arcs) {
for (let ringArcIndices of ring) {
buildRingSegments(ringArcIndices);
}
}
}
return topology;
}
pixelTopology.arcs.flat().filter(c => Bbox.isPointOnEdge(pixelTopology.bbox, c))
pixelTopology.bbox
function classifySegments(topology) {
const { COORD, SEGMENT, reverseDirections } = segmentConstants;
const arcSegments = topology.arcSegments;
const allCoords = topology.arcs.flat();
const coordTypes = topology.coordTypes = createPointHashMap(allCoords.length);
coordTypes.maybeSet = function(coord, value) {
const currentValue = coordTypes.get(coord) ?? -1;
if (value > currentValue) coordTypes.set(coord, value);
}
// Initialize coordTypes
allCoords.forEach(c => coordTypes.set(c, -1));
allCoords.filter(c => Bbox.isPointOnEdge(topology.bbox, c))
findEdges(topology).coords.forEach(c => coordTypes.set(c, COORD.JUNCTION));
topology.junctions.values().forEach(c => coordTypes.set(c, COORD.JUNCTION));
for (let arcSegment of arcSegments) {
for (let segment of arcSegment) {
let { length, fromCoord, toCoord, next, prev } = segment;
let [fromCoordType, toCoordType] = [fromCoord, toCoord].map(c => coordTypes.get(c));
// Make it safe to read and compare next/prev.direction
next ??= { direction: "dummy1" }; prev ??= { direction: "dummy2" };
// Assign default values
segment.type = SEGMENT.NORMAL;
toCoordType = COORD.NORMAL;
fromCoordType = COORD.NORMAL;
// Test for non-default cases
if (length == 1 && prev.direction == next.direction) {
segment.type = SEGMENT.STEP;
}
else if (prev.direction == reverseDirections[next.direction]) {
if (length <= 4) {
toCoordType = COORD.CORNER;
fromCoordType = COORD.CORNER;
}
if (length <= 2) {
segment.type = SEGMENT.INTRUSION;
}
}
else if (length > 1 && next.length > 1) {
toCoordType = COORD.CORNER;
}
coordTypes.maybeSet(toCoord, toCoordType);
coordTypes.maybeSet(fromCoord, fromCoordType);
}
}
topology.coordTypes = coordTypes;
return topology;
}
pointsEqual = topojsonHashUtils.pointsEqual;
async function buildTopologyFromPolygons(polygons, bbox) {
const features = [];
for (let [colorNum, ringCoords] of polygons) {
let jstsPolygon = buildJstsPolygon(ringCoords);
features.push({
type: "Feature",
geometry: jstsWriter.write(jstsPolygon),
properties: colorSwap.traceColorProps.get(colorNum)
});
}
await pauseIfNeeded();
const topology = topojson.topology({ traced: turf.featureCollection(features) });
if (bbox) topology.bbox = bbox;
return topology;
}
{
var multiPoly = turf.polygon([[[0,0],[0,10],[10,10],[10,0],[0,0]]]);
turf.rewind(multiPoly, { mutate: true, reverse: true });
return turf.booleanClockwise(multiPoly.geometry.coordinates[0]);
turf.rewind(multiPoly, { mutate: true });
turf.rewind(multiPoly, { mutate: true });
return multiPoly;
// return turf.polygonToLine(multiPoly);
// return getCleanRings([[0,0],[0,10],[10,10],[10,0],[0,0]]);
}
getCleanRings([[0,0],[0,10],[10,10],[10,0],[0,0]]);
{
return getCleanRings([[0, 0], [2, 0], [1, 1], [0, 2], [2, 2], [1, 1], [0, 0]]);
}
buildTurfPolygon([[[0,0],[0,10],[10,10],[10,0],[0,0]].toReversed()]);
{
var poly = turf.polygon([[[125, -30], [145, -30], [145, -20], [125, -20], [125, -30]], [[0,0],[0,10],[10,10],[10,0],[0,0]]]);
var line = turf.polygonToLine(poly);
return line;
}
{
const coords = [[0, 0], [2, 0], [1, 1], [0, 2], [2, 2], [1, 1]].toReversed();
const combos = [];
for (let i = 0; i < coords.length; i++) {
const left = coords.slice(i, coords.length);
const right = coords.slice(0, i);
const path = [...left, ...right, left[0]];
const ls = turf.lineString(path);
combos.push({path, ls, cw: turf.booleanClockwise(ls)});
}
return combos;
// splitOnDupCoords([[0, 0], [2, 0], [1, 1], [0, 2], [2, 2], [1, 1], [0, 0]])
}
buildTurfPolygon([[[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 1], [0, 0]]])
function splitRing(ring) {
const splitpoints = createPointHashSet(ring.length);
{
const allPoints = createPointHashSet(ring.length);
for (let coord of ring.slice(0, -1)) {
if (allPoints.has(coord)) splitpoints.add(coord);
allPoints.add(coord);
}
}
if (splitpoints.values().length == 0) return [ring];
splitpoints.add(ring[0]);
let segment = [];
const segments = [segment];
const ringSegments = [];
const lastIndex = ring.length - 1;
for (let i = 0; i < ring.length; i++) {
const coord = ring[i];
segment.push(coord);
if (splitpoints.has(coord)) {
if (segment.length > 1) {
const ringStartIdx = segments.findLastIndex(s => pointsEqual(s[0], coord));
if (ringStartIdx >= 0) ringSegments.push(segments.splice(ringStartIdx));
}
if (i == 0 || i == lastIndex) continue;
segment = [coord];
segments.push(segment);
}
}
return ringSegments.map(rs => [rs[0][0], ...rs.flatMap(s => s.slice(1))]);
}
{
var line = turf.lineString([[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 1], [0, 0]].toReversed());
var polygon = turf.polygon(line);
return turf.booleanClockwise(line);
return polygon;
}
{
const sourceCoords = [[0, 0], [2, 0], [1, 1], [2, 2], [0, 2], [1, 1], [0, 0]];
const sourceRing = turf.lineString(sourceCoords);
const sourceRingReversed = turf.lineString(sourceCoords.toReversed());
// return [ splitRing(sourceCoords), splitRing(sourceCoords.toReversed()) ];
return turf.lineToPolygon(turf.featureCollection(splitRing(sourceCoords).map(c => turf.lineString(c))));
const mp = buildTurfPolygon([sourceCoords]);
const mpRings = turf.polygonToLine(mp).features;
const mpReversed = buildTurfPolygon([sourceCoords.toReversed()]);
const mpRingsReversed = turf.polygonToLine(mpReversed).features;
var clockwiseRing = turf.lineString([[0,0],[1,1],[1,0],[0,0]]);
var counterClockwiseRing = turf.lineString([[0,0],[1,0],[1,1],[0,0]]);
return {
mpRings,
mpRingsReversed,
mpRingsCW: mpRings.map(r => turf.booleanClockwise(r)),
mpRingsReversedCW: mpRingsReversed.map(r => turf.booleanClockwise(r))
}
}
{
const shell = [[0,0], [0,10], [10,10], [10,0], [0,0]].toReversed();
const hole = [[3,3], [10,5], [3,7], [3,3]].toReversed();
const ls = turf.lineString(shell);
// return turf.booleanClockwise(ls);
return buildJstsPolygon([shell, hole]);
}
buildJstsPolygon = {
function splitRing(ring) {
const splitpoints = createPointHashSet(ring.length);
{
const allPoints = createPointHashSet(ring.length);
for (let coord of ring.slice(0, -1)) {
if (allPoints.has(coord)) splitpoints.add(coord);
allPoints.add(coord);
}
}
if (splitpoints.values().length == 0) return [ring];
splitpoints.add(ring[0]);
let segment = [];
const segments = [segment];
const ringSegments = [];
const lastIndex = ring.length - 1;
for (let i = 0; i < ring.length; i++) {
const coord = ring[i];
segment.push(coord);
if (splitpoints.has(coord)) {
if (segment.length > 1) {
const ringStartIdx = segments.findLastIndex(s => pointsEqual(s[0], coord));
if (ringStartIdx >= 0) ringSegments.push(segments.splice(ringStartIdx));
}
if (i == 0 || i == lastIndex) continue;
segment = [coord];
segments.push(segment);
}
}
return ringSegments.map(rs => [rs[0][0], ...rs.flatMap(s => s.slice(1))]);
}
// This function converts the output of tracedPolygons (a big ol' pile of rings) into valid GeoJSON (multipolygons with holes).
function buildJstsPolygon(ringCoords, ignoreHoles = false) {
const { Orientation, Coordinate } = jsts;
ringCoords = ringCoords.flatMap(ring => splitRing(ring));
const polygonMeta = ringCoords.map(rc => {
const coords = rc.map(c => new Coordinate(...c));
const group = Orientation.isCCW(coords) ? "shellMeta" : "holeMeta";
const ring = jstsFactory.createLinearRing(coords);
const polygon = jstsFactory.createPolygon(ring);
if (ignoreHoles && group == "holeMeta") return undefined;
return {
ring,
polygon,
group,
bbox: Bbox.fromPoints(rc),
area: polygon.getArea()
};
});
polygonMeta.sort((a,b) => a.area - b.area);
let { shellMeta, holeMeta } = _.groupBy(polygonMeta, rm => rm.group);
shellMeta ??= [];
holeMeta ??= [];
shellMeta.forEach(shell => shell.holeRings = []);
if (!ignoreHoles) {
for (let hole of holeMeta) {
let shell;
if (shellMeta.length == 1) {
shell = shellMeta[0];
}
else {
const candidates = shellMeta.filter(shell => shell.area > hole.area && Bbox.covers(shell.bbox, hole.bbox));
if (candidates.length == 1) {
shell = candidates[0];
}
else {
shell = candidates.find(shell => shell.polygon.covers(hole.polygon));
}
}
if (!shell) {
debugger;
throw "couldn't find shell for hole";
}
shell.holeRings.push(hole.ring);
}
}
const islands = [];
for (let shell of shellMeta) {
const holeRings = shell.holeRings;
if (holeRings.length == 0) {
islands.push(shell.polygon);
}
else {
islands.push(jstsFactory.createPolygon(shell.ring, shell.holeRings));
}
}
const result = jstsFactory.createMultiPolygon(islands);
if (islands.length > 1 || islands[0].getNumInteriorRing() > 1) {
return result.buffer(0);
}
return result;
}
return buildJstsPolygon
}
async function cleanArcs(topology) {
const arcs = topology.arcs;
const l = arcs.length;
for (let i = 0; i < l; i++) {
const arc = arcs[i];
const ls = turf.lineString(arc);
turf.cleanCoords(ls, { mutate: true });
arcs[i] = turf.getCoords(ls);
if (i % 1000 == 0) await pauseIfNeeded();
}
}
async function nnDownscaleImage(imageSource, downscaleFactor) {
const width = imageSource.naturalWidth ?? imageSource.width;
const height = imageSource.naturalHeight ?? imageSource.height;
const newWidth = Math.round(width / downscaleFactor);
const newHeight = Math.round(height / downscaleFactor);
const stepX = width / newWidth;
const offsetX = Math.round(stepX / 2 - 0.5);
const stepY = height / newHeight;
const offsetY = Math.round(stepY / 2 - 0.5);
const srcCanvas = new OffscreenCanvas(width, height);
const srcCtx = srcCanvas.getContext("2d", { alpha: false, desynchronized: true });
srcCtx.drawImage(imageSource, 0, 0);
const srcArray = srcCtx.getImageData(0, 0, width, height).data;
const destArray = new Uint8ClampedArray(4 * newWidth * newHeight);
let i = 0;
for (let y = 0; y < newHeight; y++) {
const srcY = Math.min(Math.round(offsetX + y * stepY), height);
for (let x = 0; x < newWidth; x++) {
const srcX = Math.min(Math.round(offsetY + x * stepX), width);
const si = 4 * (srcY * width + srcX);
destArray[i] = srcArray[si];
destArray[i+1] = srcArray[si+1];
destArray[i+2] = srcArray[si+2];
destArray[i+3] = srcArray[si+3];
i += 4;
}
}
return await createImageBitmap(new ImageData(destArray, newWidth, newHeight));
}
async function tracePolygons(worldMapImage, colorTable, downscaleFactor, cancellationToken) {
downscaleFactor = Math.max(downscaleFactor, 1);
cancellationToken ??= getCancellationToken();
const allPolygons = new Map();
const ingestPolygons = function(newPolygons, rect) {
console.log('ingesting', rect);
for (let [colorNum, newRings] of newPolygons) {
let currentRings = allPolygons.get(colorNum);
currentRings ? currentRings.push(...newRings) : allPolygons.set(colorNum, newRings);
}
}
const bitmap = await createImageBitmap(worldMapImage.canvas);
const ts = new TileSlicer(bitmap);
const edgeFinder = new TileEdgeFinder(colorTable);
const edgeExtractors = [];
const destroy = () => {
ts.destroy();
edgeFinder.destroy();
edgeExtractors.forEach(e => e.destroy());
}
const maybeDestroy = () => {
if (!cancellationToken.cancel) return false;
destroy();
return true;
}
invalidation.then(() => {
cancellationToken.cancel = true;
destroy();
});
const extractionPromises = [];
tracePolygonsIntermediate.splice(0, 1000);
const [tileCountX, tileCountY] = ts.getTileCounts(downscaleFactor);
for (let tileX = 0; tileX < tileCountX; tileX++) {
for (let tileY = 0; tileY < tileCountY; tileY++) {
if (maybeDestroy()) return;
const tile = await ts.getTileBitmap(tileX, tileY, downscaleFactor);
if (maybeDestroy()) return;
const { colorCanvas, edgeCanvas, rect } = await edgeFinder.processTile(tile);
tracePolygonsIntermediate.push({ tile: tile.bitmap, colorCanvas, edgeCanvas });
if (maybeDestroy()) return;
const edgeExtractor = new TileEdgeExtractorWorker();
edgeExtractors.push(edgeExtractor);
extractionPromises.push(edgeExtractor.getPolygons(colorCanvas, edgeCanvas, rect));
}
}
for (let promise of extractionPromises) {
if (maybeDestroy()) return;
const { polygons, rect } = await promise;
if (maybeDestroy()) return;
ingestPolygons(polygons, rect);
}
destroy();
return {
bbox: ts.getMapSize(downscaleFactor),
polygons: allPolygons
}
}
tracePolygonsIntermediate = [];
tracePolygonsIntermediate[0].tile.bitmap
intermediates = {
const tileset = tracePolygonsIntermediate[0];
const canvases = []
canvases.push(await createCanvas(tileset.tile));
canvases.push(await createCanvas(tileset.colorCanvas));
canvases.push(await createCanvas(tileset.edgeCanvas));
return htl.html`${canvases}`;
}
class TileEdgeExtractor extends PauseAndCancel {
async _extractPixels(colorCanvas, edgeCanvas) {
this.restart();
const [edgeColorsIO, edgeNeighborsIO] = [colorCanvas, edgeCanvas].map(canvas => {
const { width, height } = canvas;
const ctx = canvas.getContext("2d", { willReadFrequently: true });
const imageData = ctx.getImageData(0, 0, width, height);
const pixelIO = PixelIO.fromImageData(imageData);
canvas.width = 1;
canvas.height = 1;
return pixelIO;
});
colorCanvas = undefined;
edgeCanvas = undefined;
// Extract the vector data
const pixels = new Map();
for (let x = 0; x < edgeColorsIO.width; x++) {
for (let y = 0; y < edgeColorsIO.height; y++) {
if (this.isCancelled) return;
let redValue = edgeNeighborsIO.getRgba(x,y)[0];
if (redValue == 0) continue;
let colorNum = edgeColorsIO.getColorNum(x, y);
const cn = ColorNum.toRgba(colorNum)
let pixelData = pixels.get(colorNum);
if (!pixelData) { pixelData = []; pixels.set(colorNum, pixelData); }
let dirs = EdgeFinderFilter.neighborAlphasDecoded[redValue];
pixelData.push({ x, y, ...dirs });
}
await this._pauseIfNeeded();
}
return pixels;
}
async getPolygons(colorCanvas, edgeCanvas, rect) {
debugger;
this.restart();
const offset = [rect.x, rect.y];
// Fork of http://defghi1977.html.xdomain.jp/tech/img2svg3/dot2svg3.htm
const direcs = {e:0, s:1, w:2, n:3};
const xshift = 17, yshift = 2;
const ymask = 0b11111111111111100, dmask = 0b11;
const joinXYD = (x, y, d) => x << xshift | y << yshift | d;
const splitXYD = v => [v >>> xshift, (v & ymask) >>> yshift, v & dmask];
const toNext = (x, y, d, nd) => {
switch(d){
case direcs.e: x++; break;
case direcs.s: y++; break;
case direcs.w: x--; break;
case direcs.n: y--; break;
}
return joinXYD(x, y, nd);
};
const pushVectorsWrapPixel = (vectors, glPixel) => {
let { x, y, n, e, s, w } = glPixel;
// glPixel.n means it has a neighbor to the north; which means we actually want to draw the eastward-pointing vector, etc.
//clockwise
if (n) vectors.add(joinXYD(x , y , direcs.e));
if (e) vectors.add(joinXYD(x + 1, y , direcs.s));
if (s) vectors.add(joinXYD(x + 1, y + 1, direcs.w));
if (w) vectors.add(joinXYD(x , y + 1, direcs.n));
};
const getPathPoints = (vectors) => {
let result = [], path = [];
let x = 0, y = 0, d = 0;
let nx = 0, ny = 0, nd = 0;
let len = 0;
for (let vector of vectors.values()){
if(!vectors.has(vector)) return;
vectors.delete(vector);
[x, y, d] = splitXYD(vector);
path = [[x, y]];
result.push(path);
for (;;){
if (this.isCancelled) return [];
const next = findNext(vectors, x, y, d);
if(next === undefined) break;
vectors.delete(next);
[nx, ny, nd] = splitXYD(next);
/* if(d != nd) */ path.push([nx,ny]);
[x, y, d] = [nx, ny, nd];
}
}
return result;
};
const findNext = (vectors, x, y, d) => {
//search vectors order by anti clockwise.
for(let i = 0; i > -4; i--){
if(i == 1){continue;}
const next = toNext(x, y, d, (d + i) & 3);
if(vectors.has(next)){
return next;
}
}
};
const pixels = await this._extractPixels(colorCanvas, edgeCanvas);
let polygons = new Map();
for (let [colorNum, objPixels] of pixels) {
if (this.isCancelled) return;
let vectors = new Set();
objPixels.forEach(p => pushVectorsWrapPixel(vectors, p));
let rings = getPathPoints(vectors);
for (let i = 0; i < rings.length; i++) {
rings[i] = rings[i].map(p => [p[0] + offset[0], p[1] + offset[1]]);
}
rings.forEach(r => r.push(r[0]));
polygons.set(colorNum, rings);
await this._pauseIfNeeded();
}
return { polygons, rect };
}
}
class ImageTransferUtil {
static makeTransferable(imageData) {
return {
pixelBuffer: imageData.data.buffer,
width: imageData.width,
height: imageData.height
}
}
static fromTransferable(transferable) {
const { pixelBuffer, width, height } = transferable;
const pixels = new Uint8ClampedArray(pixelBuffer);
return new ImageData(pixels, width, height);
}
}
class TileEdgeExtractorWorker extends PauseAndCancel {
constructor() {
super();
this.worker = new Worker(tileEdgeExtractorWorkerUrl);
}
destroy() {
this.cancel();
this.worker.terminate();
}
async _pauseIfNeeded() {
return;
}
async getPolygons(colorCanvas, edgeCanvas, rect) {
function getTransferableImageData(canvas) {
const ctx = canvas.getContext('2d');
const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
return ImageTransferUtil.makeTransferable(imageData);
}
const promise = getNakedPromise();
this.worker.onmessage = function(e) {
promise.resolve(e.data);
};
const colorImageData = getTransferableImageData(colorCanvas);
const edgeImageData = getTransferableImageData(edgeCanvas);
debugger;
this.worker.postMessage({ colorImageData, edgeImageData, rect }, [ colorImageData.pixelBuffer, edgeImageData.pixelBuffer ]);
promise.finally(() => this.worker.terminate());
return promise;
}
}
{
const bitmap = await createImageBitmap(worldMapImage.canvas);
const ts = new TileSlicer(bitmap);
const tile = await ts.getTileBitmap(1, 0, 1);
return createCanvas(tile.bitmap);
}
class TileSlicerLight {
static {
TileSlicerLight.baseTileSize = Math.min(GLHelper.maxTextureSize, 4096); //GLHelper.maxTextureSize / 2;
}
constructor(width, height) {
Object.defineProperty(this, "width", { enumerable: true, writable: false, value: width });
Object.defineProperty(this, "height", { enumerable: true, writable: false, value: height });
}
getMapSize(downscaleFactor) {
downscaleFactor = Math.max(downscaleFactor, 1);
return [this.width, this.height].map(c => Math.round(c / downscaleFactor));
}
getTileCount(downscaleFactor) {
downscaleFactor = Math.max(downscaleFactor, 1);
let counts = this.getTileCounts(downscaleFactor);
return counts[0] * counts[1];
}
getTileCounts(downscaleFactor) {
downscaleFactor = Math.max(downscaleFactor, 1);
let countX = Math.ceil((this.width / downscaleFactor) / TileSlicerLight.baseTileSize);
let countY = Math.ceil((this.height / downscaleFactor) / TileSlicerLight.baseTileSize);
return [countX, countY];
}
_getTileSizeInfo(tileX, tileY, downscaleFactor) {
const bounds = this.getMapSize(downscaleFactor);
const tileSize = TileSlicerLight.baseTileSize;
const [x0, y0] = [tileX, tileY].map(c => c * tileSize);
const x1 = Math.min(x0 + tileSize, bounds[0]);
const y1 = Math.min(y0 + tileSize, bounds[1]);
let rect = { x: x0, y: y0, width: x1 - x0, height: y1 - y0 };
if (rect.width <= 0 || rect.height <= 0) rect = { x: NaN, y: NaN, width: NaN, height: NaN };
return {
inputBitmapDims: bounds,
rect
}
}
}
class WorkerGlobalScope {}
EdgeFinderFilter.neighborAlphasDecoded
class EdgeFinderFilter extends PIXI.Filter {
constructor() {
let uniformValues = {
inputDimensions: [1, 1],
};
super(es300VertexShader, EdgeFinderFilter.fragmentShader, uniformValues);
}
get inputDimensions() { return this.uniforms.inputDimensions; }
set inputDimensions(value) { this.uniforms.inputDimensions = value; }
apply() {
// debugger;
return super.apply(...arguments);
}
static {
EdgeFinderFilter.neighborAlphas = {
aN: 16,
aE: 32,
aS: 64,
aW: 128
}
{
// EdgeFinderFilter.neighborAlphasDecoded
let options = [];
let allDirs = ["n", "e", "s", "w"];
let empty = allDirs.reduce((obj, dir) => { obj[dir] = false; return obj }, { value: 0 });
for (let [key, value] of Object.entries(EdgeFinderFilter.neighborAlphas)) {
let f = Object.assign({}, empty);
let dir = key[1].toLowerCase();
let t = Object.assign({}, empty, Object.fromEntries([["value", value], [dir, true]]));
options.push([f, t]);
}
let combos = [];
for (let rawCombo of d3.cross(...options)) {
let combo = Object.assign({}, empty);
for (let v of rawCombo) {
combo.value += v.value;
allDirs.forEach(d => combo[d] ||= v[d]);
}
combos[combo.value] = combo;
delete combo.value;
}
EdgeFinderFilter.neighborAlphasDecoded = combos;
}
let defines = Object.entries(EdgeFinderFilter.neighborAlphas)
.map(([key, value]) => ` float ${key} = ${value / 255};`)
.join("\n");
EdgeFinderFilter.fragmentShader = `#version 300 es
precision highp float;
${defines.trim()}
in vec2 vTextureCoord;
in vec2 vFragCoord;
in vec2 vFilterCoord;
uniform sampler2D uSampler;
uniform vec2 inputDimensions;
uniform vec4 inputSize;
out vec4 fragColor;
vec2 uvToXy(vec2 uv, vec2 dimensions) {
return vec2(uv.x * dimensions.x, uv.y * dimensions.y);
}
vec2 xyToUv(vec2 xy, vec2 dimensions) {
return vec2(xy.x / dimensions.x, xy.y / dimensions.y);
}
void main () {
vec2 xyC = vFragCoord;
vec2 xyN = vFragCoord + vec2( 0.0, -1.0);
vec2 xyE = vFragCoord + vec2( 1.0, 0.0);
vec2 xyS = vFragCoord + vec2( 0.0, 1.0);
vec2 xyW = vFragCoord + vec2(-1.0, 0.0);
bool eN = xyC.y < 1.0;
bool eE = xyC.x > inputDimensions.x - 1.0;
bool eS = xyC.y > inputDimensions.y - 1.0;
bool eW = xyC.x < 1.0;
vec2 uvC = xyToUv(xyC, inputSize.xy);
vec2 uvN = xyToUv(xyN, inputSize.xy);
vec2 uvE = xyToUv(xyE, inputSize.xy);
vec2 uvS = xyToUv(xyS, inputSize.xy);
vec2 uvW = xyToUv(xyW, inputSize.xy);
vec4 cC = texture(uSampler, uvC);
if (cC.a == 0.0) return;
vec4 cN = texture(uSampler, uvN);
vec4 cE = texture(uSampler, uvE);
vec4 cS = texture(uSampler, uvS);
vec4 cW = texture(uSampler, uvW);
vec4 outputColor = vec4(0.0, 0.0, 0.0, 0.0);
float encodedNeighbors = 0.0;
if (eN || cC != cN) {
outputColor.rgb = cC.rgb;
encodedNeighbors += aN;
}
if (eE || cC != cE) {
outputColor.rgb = cC.rgb;
encodedNeighbors += aE;
}
if (eS || cC != cS) {
outputColor.rgb = cC.rgb;
encodedNeighbors += aS;
}
if (eW || cC != cW) {
outputColor.rgb = cC.rgb;
encodedNeighbors += aW;
}
if (encodedNeighbors == 0.0) {
fragColor = vec4(0.0, 0.0, 0.0, 0.0);
}
else {
fragColor = vec4(encodedNeighbors, 0.0, 0.0, 1.0);
}
}`;
}
}
function buildColorSwap(layerName) {
let selectedLayers = mapSpec.layers;
let getSelectedProps = (props) => props;
if (layerName) {
selectedLayers = _.pick(mapSpec.layers, [layerName]);
let selectedPropNames = Object.values(selectedLayers).map(l => l.prop);
getSelectedProps = (props) => _.pick(props, selectedPropNames);
}
const provincesFlat = [];
for (let [colorNum, props] of mapSpec.provinceProps) {
const traceId = Object.values(selectedLayers).map(p => props[p.prop]).join("|");
provincesFlat.push({ colorNum, traceId, props: getSelectedProps(props) });
}
const uniques = new Map();
for (let group of Object.values(_.groupBy(provincesFlat, "traceId"))) {
const props = group[0].props;
props.colorNum = group[0].colorNum;
const sourceColorNums = group.map(p => p.colorNum);
uniques.set(group[0].colorNum, { props, sourceColorNums });
}
const colorSwap = {};
const sourceColors = colorSwap.sourceColors = new Map();
const traceColorProps = colorSwap.traceColorProps = new Map();
for (let [traceColorNum, { props, sourceColorNums }] of uniques) {
sourceColorNums.forEach(sc => colorSwap.sourceColors.set(sc, traceColorNum));
colorSwap.traceColorProps.set(traceColorNum, props);
}
colorSwap.getLayerProp = function(layerName, traceColorNum) {
const props = traceColorProps.get(traceColorNum);
if (!props) return {};
const prop = selectedLayers[layerName].prop;
return { name: prop, value: props[prop] };
}
return colorSwap;
}
{
const shell = [[0,0], [0,10], [10,10], [10,0], [0,0]];
const hole = [[3,3], [10,5], [3,7], [3,3]];
return turf.buffer(turf.polygon([shell, hole]), 0)
}
class PixelIO {
static {
const buffer = new ArrayBuffer(2);
new DataView(buffer).setInt16(0, 256, true);
PixelIO.isLittleEndian = (new Int16Array(buffer)[0] === 256);
}
constructor(width, height, uint8ClampedArrayBuffer) {
this.width = width;
this.height = height;
if (width && height) uint8ClampedArrayBuffer ??= new Uint8ClampedArray(4 * width * height).buffer;
this.dataView = new DataView(uint8ClampedArrayBuffer);
}
getOffset(x, y) {
if (x >= this.width || y >= this.height) return -1;
return 4 * (y * this.width + x);
}
getColorNum(x, y) {
return this.getColorNumAt(this.getOffset(x, y));
}
getColorNumAt(i) {
return this.dataView.getUint32(i, PixelIO.littleEndian);
}
getNextColorNumAt(i) {
return this.dataView.getUint32(i, PixelIO.littleEndian);
}
getRgba(x, y) {
return this.getRgbaAt(this.getOffset(x, y));
}
getRgbaAt(i) {
return (PixelIO.littleEndian) ?
[ this.dataView.getUint8(i+3), this.dataView.getUint8(i+2), this.dataView.getUint8(i+1), this.dataView.getUint8(i) ] :
[ this.dataView.getUint8(i), this.dataView.getUint8(i+1), this.dataView.getUint8(i+2), this.dataView.getUint8(i+3) ];
}
setColorNum(x, y, colorNum) {
this.dataView.setUint32(this.getOffset(x, y), colorNum);
}
drawTo(canvasOrContext, dx = 0, dy = 0, ...putImageDataArgs) {
let ctx = (canvasOrContext.getContext) ? canvasOrContext.getContext("2d") : canvasOrContext;
const dataArray = new Uint8ClampedArray(this.dataView.buffer);
const imageData = new ImageData(dataArray, this.width, this.height);
ctx.putImageData(imageData, dx, dy, ...putImageDataArgs);
}
static fromImageSource(src) {
let canvas = DOM.canvas(src.naturalWidth ?? src.width, src.naturalHeight ?? src.height);
let ctx = canvas.getContext("2d", { willReadFrequently: true });
ctx.drawImage(src, 0, 0);
return PixelIO.fromImageData(ctx.getImageData(0, 0, canvas.width, canvas.height));
}
static fromImageData(imageData) {
return new PixelIO(imageData.width, imageData.height, imageData.data.buffer);
}
static fromArray(array, width, height) {
let clampedArray;
if (array.length != 4 * width * height) throw "fromArray: array parameter must be of length width * height;"
if (array instanceof Uint8ClampedArray) {
clampedArray = array;
}
else if (array instanceof Object.getPrototypeOf(Uint8Array)) {
clampedArray = new Uint8ClampedArray(array);
}
return new PixelIO(width, height, clampedArray.buffer);
}
}
{
var line1 = turf.lineString([[-2, 2], [4, 2]]);
var line2 = turf.lineString([[1, 1], [1, 2], [1, 3], [1, 4]]);
var cross = turf.booleanCrosses(line1, line2);
return de9im.crosses(line1, line2);
}
turf.boo
Type JavaScript, then Shift-Enter. Ctrl-space for more options. Arrow ↑/↓ to switch modes.
function getChildrenFromMultiGeometry(jstsMulti) {
if (!jstsMulti.getNumGeometries) return [jstsMulti];
const children = []
for (let i = 0; i < jstsMulti.getNumGeometries(); i++) {
children.push(jstsMulti.getGeometryN(i));
}
return children;
}
function getChildrenFromMultiGeoJson(geoMulti) {
if (!geoMulti.geometry.type.startsWith("Multi")) return [geoMulti];
const geometry = geoMulti.geometry;
const type = geometry.type.replace("Multi", "");
return geometry.coordinates.map(c => ({
type: geoMulti.type,
properties: Object.assign({}, geoMulti.properties),
geometry: {
type,
coordinates: c
}
}));
}
function getChildrenFromMultiTopoJson(geometry) {
if (!geometry) return [];
if (!geometry.type.startsWith("Multi")) return [geometry];
const type = geometry.type.replace("Multi", "");
return geometry.arcs.map(c => ({
type,
properties: Object.assign({}, geometry.properties),
arcs: c
}));
}
mergeFeatures(topojson.feature(pixelTopology, pixelTopology.objects.states).features, "key")
{
const features = topojson.feature(pixelTopology, pixelTopology.objects.states).features
const split = _.groupBy(features, f => f.geometry.type.startsWith("Multi"));
return split;
}
_.pick({potato: 7, tomato: 5}, undefined)
_.chain([{potato: 7, tomato: 5}, {potato: 7, tomato: 9}]).groupBy(f => ({ tomato: f.tomato })).value();
function mergeFeatures(features, fnGroupBy) {
const geoPath = d3.geoPath(d3.geoIdentity());
const splitByType = _.groupBy(features, f => f.geometry.type.startsWith("Multi"));
const flatFeatures = [
...(splitByType[false] ?? []),
...(splitByType[true] ?? []).flatMap(f => getChildrenFromMultiGeoJson(f))
];
const featuresByKey = Object.entries(_.groupBy(flatFeatures, groupBy));
const resultFeatures = new Map();
for (let featureSet of featuresByKey) {
// const key = groupBy(featureSet[0]);
// resultFeatures.set(key, featureSet);
}
return { featuresByKey, resultFeatures }
//return groupedByKey;
/*
for (let featureSet of Object.values(_.groupBy(edgeFeatures, f => f.properties[keyField]))) {
features.push(...unionPolygonFeatures(featureSet));
}
/*
const multiFeatures = split[true] ?? [];
const singleFeatures = split[false] ?? [];
const result = [
Object.values(_.groupBy(multiFeatures, f => f.properties[keyField]))
.flatMap(f => getChildrenFromMultiGeoJson(f)),
Object.values(_.groupBy(singleFeatures, f => f.properties[keyField]))
.flatMap(f => getChildrenFromMultiGeoJson(f)),
];
for (let featureSet of
results.push(...unionPolygonFeatures(featureSet));
}
const mpCoords =
return {
type: "Feature",
properties: features[0].properties,
geometry: {
type: "MultiPolygon",
coordinates: features.map(f => f.geometry.coordinates)
}
};
}
// Hemisphere wrapping
const extendedObjects = {};
for (let [layerName, gc] of Object.entries(topology.objects)) {
const geometries = topology.objects[layerName].geometries;
if (!geometries.length) return;
const eastGeometries = geometries.filter(g => {
const feature = topojson.feature(topology, g);
const gx1 = geoPath.bounds(feature)[1][0];
return (gx1 >= xMid);
});
const features = [
...(await getOffsetFeatures(eastGeometries, -x1)),
...(await getOffsetFeatures(geometries, 0)),
...(await getOffsetFeatures(geometries, x1))
];
const edgeFeatures = features.filter(f => {
const [gx0,,gx1] = geoPath.bounds(f).flat();
return (gx0 == x0 || gx0 == x1 || gx1 == x0 || gx1 == x1);
});
_.pull(features, ...edgeFeatures);
for (let featureSet of Object.values(_.groupBy(edgeFeatures, f => f.properties[keyField]))) {
features.push(...unionPolygonFeatures(featureSet));
}
extendedObjects[layerName] = { type: "FeatureCollection", features: features };
await pauseIfNeeded();
}
const extended = topojson.topology(extendedObjects);
topology.arcs = extended.arcs;
topology.objects = extended.objects;
return topology;
*/
}
function visitAll(object, fn) {
Object.keys(object).forEach(function(k) {
let halt = fn(object[k], k, object);
if (object[k] && typeof object[k] === 'object' && !halt) {
visitAll(object[k], fn);
}
});
}
turf = require('@turf/turf@6.5.0/turf.min.js');
function createCanvas(imageSource) {
const width = imageSource.naturalWidth ?? imageSource.width;
const height = imageSource.naturalHeight ?? imageSource.height;
const canvas = DOM.canvas(width, height);
const ctx = canvas.getContext("2d");
ctx.drawImage(imageSource, 0, 0);
canvas.style.maxWidth = "100%";
canvas.style.imageRendering = "pixelated";
return canvas;
}
// TODO:
function createImageBitmapSync(image, sx, sy, sw, sh) {
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
