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))
};
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));
}
{
const bitmap = await createImageBitmap(worldMapImage.canvas);
const ts = new TileSlicer(bitmap);
const tile = await ts.getTileBitmap(0, 0, 1);
return createCanvas(tile.bitmap);
}
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', newPolygons, 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();
debugger
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 colorNum = edgeNeighborsIO.getColorNum(x, y);
let redValue = ColorNum.toRgbaArray(colorNum)[0];
if (redValue == 0) continue;
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) {
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();
debugger;
for (let [colorNum, objPixels] of pixels) {
if (this.isCancelled) return;
debugger;
const getDirections = op => Object.entries(op).filter(e => e[1] === true).map(e => e[0]);
const rawDirections = new Set(objPixels.flatMap(op => getDirections(op)));
let vectors = new Set();
objPixels.forEach(p => pushVectorsWrapPixel(vectors, p));
const wrappedDirections = new Set([...vectors].map(v => splitXYD(v)[2]));
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);
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
async function buildColorTable(colorSwap) {
// Build column data
let columns = [...new Array(256)].map(() => []);
for (let [sourceColorNum, traceColorNum] of colorSwap.sourceColors.entries()) {
let [red] = ColorNum.toRgbaArray(sourceColorNum);
let column = red % 256;
columns[column].push([sourceColorNum, traceColorNum]);
}
// Build the texture
let textureWidth = 512;
let textureHeight = 1 + _.max(columns.map(c => c.length));
let canvas = new DOM.canvas(textureWidth, textureHeight);
let ctx = canvas.getContext("2d");
let imageData = ctx.createImageData(textureWidth, textureHeight);
let pixelIO = PixelIO.fromImageData(imageData);
// Draw the pixels
for (let colNum = 0; colNum < columns.length; colNum++) {
let x = colNum * 2;
let row = columns[colNum];
for (let y = 0; y < row.length; y++) {
let values = row[y];
for (let i = 0; i < values.length; i++) {
pixelIO.setColorNum(x+i, y, values[i]);
}
}
}
pixelIO.drawTo(ctx);
let bitmap = await createImageBitmap(canvas);
return { canvas, bitmap, width: textureWidth, height: textureHeight };
}
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 {
constructor(width, height, array) {
this.width = width;
this.height = height;
if (!array) {
this.colorNumArray = new Uint32Array(width * height);
}
else {
if (!array.buffer) throw "PixelIO: array parameter must be a TypedArray.";
if (array.buffer.byteLength != 4 * width * height) throw "PixelIO: array length did not match provided dimensions.";
this.colorNumArray = new Uint32Array(array.buffer);
}
}
_getOffset(x, y) {
if (x >= this.width || y >= this.height) return -1;
return y * this.width + x;
}
getColorNum(x, y) {
return this.colorNumArray[this._getOffset(x, y)];
}
setColorNum(x, y, colorNum) {
this.colorNumArray[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.colorNumArray.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);
}
}
{
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
}));
}
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.
