type: sampleTopology.type,

bbox: sampleTopology.bbox.map(c => 4*c),

objects: sampleTopology.objects,

arcs: sampleTopology.arcs.map(a => a.map(c => [4*c[0], 4*c[1]]))

const { regl, commands, buffers } = reglProgram;

const tileTexture = regl.texture({ data: bitmap });

const tileDimensions = [ bitmap.width, bitmap.height ];

const mapEdgesAbs = {

x0: mapRect.x,

y0: mapRect.y,

x1: mapRect.x + mapRect.width,

y1: mapRect.y + mapRect.height

};

const mapBboxVec = [

mapEdgesAbs.x0 - tileRect.x,

mapEdgesAbs.y0 - tileRect.y,

mapEdgesAbs.x1 - tileRect.x - 1,

mapEdgesAbs.y1 - tileRect.y - 1

]

const tileBboxVec = [

TILE_PADDING,

TILE_PADDING,

TILE_PADDING + tileRect.width - 1,

TILE_PADDING + tileRect.height - 1

]

Object.values(buffers).forEach(b => b.resize(...tileDimensions));

commands.replaceColors({ uSampler: tileTexture, framebuffer: buffers.color });

await glClientWaitAsync(regl);

tileTexture.destroy();

commands.traceImage({ uSampler: buffers.color, mapBboxVec, tileBboxVec, framebuffer: buffers.traced });

await glClientWaitAsync(regl);

const results = [];

const rect = Bbox.dims(tileBboxVec);

if (mapRect.width == tileRect.x + tileRect.width) rect.width++;

if (mapRect.height == tileRect.y + tileRect.height) rect.height++;

const data = await readFramebufferAsync(regl, buffers.traced, rect);

return new PixelIO(rect.width, rect.height, data);

topology = {...topology};

topology.objects = {...topology.objects};

const { layerObjectColors, replacedColorProps } = layerMap;

const keyColors = new Map();

// debugger;

replacedColorProps.forEach((props, colorNum) => keyColors.set(props.key, colorNum));

const tracedGeometries = topology.objects.traced.geometries;

for (let [layerName, layerObjects] of Object.entries(layerObjectColors)) {

const layerGeometries = [];

for (let [id, keys] of Object.entries(layerObjects)) {

// debugger;

const colorNums = keys.map(k => keyColors.get(k));

const matches = tracedGeometries.filter(g => colorNums.includes(g.properties.colorNum));

const merged = (matches.length == 1) ? {...matches[0]} : topojson.mergeArcs(topology, matches);

merged.properties = { id };

layerGeometries.push(merged);

}

topology.objects[layerName] = turf.geometryCollection(layerGeometries).geometry;

}

return topology;

const { Orientation, Coordinate } = jsts;

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);

return {

coords: rc,

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.holeCoords = []);

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) {

throw "couldn't find shell for hole";

}

shell.holeCoords.push(hole.coords);

}

const islandCoords = shellMeta.map(shell => [shell.coords, ...shell.holeCoords]);

const polygon = (islandCoords.length == 1) ? turf.polygon(islandCoords[0]) : turf.multiPolygon(islandCoords);

/*

return polygon.geometry;

/*

const coordTypes = topology.properties.coordTypes;

const junctionCoordNums = [...coordTypes.numericMap.entries()].filter(e => e[1] == "junction").map(e => e[0]);

const junctions = MaskSet.around(new Set(junctionCoordNums), CoordMask);

function weight(triangle) {

if (junctions.has(triangle[1])) return Infinity;

return topojson.planarTriangleArea(triangle);

}

const result = topojson.presimplify(topology, weight);

result.properties = topology.properties;

return result;

let a = [1,2,3,4,5,1];

rotateRing(a, -2)

return a;

if (a === b) return true;

if (a === undefined || b === undefined) return false;

return a[0] == b[0] && a[1] == b[1];

if (newStartIndex <= 0) return;

const newRing = [

...ring.slice(newStartIndex, -1),

...ring.slice(0, newStartIndex),

ring[newStartIndex]

];

ring.splice(0, ring.length, ...newRing);

const topology = sampleTopology;

const usedArcStats = [];

for (let geometry of sampleTopology.objects.traced.geometries) {

const arcIds = geometry.arcs.flat().map(a => (a < 0) ? ~a : a).flat();

arcIds.forEach(i => usedArcStats.push(arcStats[i]));

}

let weightCounts = _.groupBy(usedArcStats.flat(), "value");

weightCounts = Object.entries(weightCounts).map(([k,v]) => ({ value: parseFloat(k), coordCount: _.sumBy(v, "coordCount") }));

weightCounts = _.sortBy(weightCounts, v => -v.value);

for (let i = 1; i < weightCounts.length; i++) {

weightCounts[i].coordCount += weightCounts[i-1].coordCount;

}

weightCounts = _.sortBy(weightCounts, v => v.value);

return weightCounts

/*

const allStats = arcStats.flat();

const values = _.sortBy(_.uniq(allStats.map(s => s.value)));

const coordCounts = [];

for (let value of values) {

const stats = allStats.filter(s => s.value >= value);

coordCounts.push({ x: parseFloat(Math.log2(value).toFixed(4)), y: _.sumBy(stats, "coordCount") });

}

return coordCounts;

const allStats = arcStats.flat();

const values = _.uniq(allStats.map(s => s.value));

const minLogValue = Math.floor(Math.log2(_.min(values)));

const maxLogValue = Math.ceil(Math.log2(_.max(values.filter(v => v < Infinity))));

const coordCounts = [];

for (let value of d3.range(minLogValue, maxLogValue).map(v => 2**v)) {

const stats = allStats.filter(s => s.value >= value);

coordCounts.push({ value, coordCounts: _.sumBy(stats, "coordCount") });

}

return coordCounts;

const topology = sampleTopology;

const arcStats = topology.arcs.map(arc => {

const weightCounts = new Map();

for (let weight of arc.map(a => a[2])) {

weightCounts.set(weight, (weightCounts.get(weight) ?? 0) + 1);

}

return weightCounts;

/*

return weightCounts;

});

return arcStats;

const ts = performance.now();

const topology = sampleTopology;

const arcWeightCounts = topology.arcs.map(arc => {

const weightCounts = new Map();

for (let weight of arc.map(a => a[2])) {

weightCounts.set(weight, (weightCounts.get(weight) ?? 0) + 1);

}

return weightCounts;

});

const result = sumWeightCounts(arcWeightCounts);

const runtime = performance.now() - ts;

return { result, runtime };

const sums = new Map();

weightCounts.forEach(wc => {

for (const [weight, count] of wc.entries()) {

sums.set(weight, (sums.get(weight) ?? 0) + count);

}

});

return sums;

return arc.length > 3 && coordsEqual(arc[0], arc.at(-1));

const traceResult = sampleTraceResult;

const [x0, y0, x1, y1] = traceResult.bbox;

const scaleX = d3.scaleLinear().domain([x0, x1]).range([-180, 180]);

const scaleY = d3.scaleLinear().domain([y0, y1]).range([60, -60]);

// debugger;

const scale = {

transform: c => {

c[0] = scaleX(c[0]);

c[1] = scaleY(c[1]);

},

untransform: c => {

c[0] = Math.round(scaleX.invert(c[0])),

c[1] = Math.round(scaleY.invert(c[1]))

}

}

const geojson = _.cloneDeep(await buildGeoJsonRaw(traceResult));

turf.coordEach(geojson, c => scale.transform(c));

// turf.coordEach(geojson, c => scale.untransform(c));

// const untransformed = transformed.map(c => scale.untransform(c));

const stitched = d3.geoStitch(geojson);

turf.coordEach(stitched, c => scale.untransform(c));

return { stitched: stitched.features.filter(f => {

const coords = turf.coordAll(f);

return (_.min(coords.map(c => c[0])) < 10 && _.max(coords.map(c => c[0])) > 2040)

}) };

options = Object.assign({ wrapX: false, smooth: true, allowExpansion: true }, options);

/*

// Create topology

const geojson = await buildGeoJsonRaw(traceResult);

// geojson.features.push(edges);

let topology = topojson.topology({traced: geojson});

topology.bbox = [...traceResult.bbox];

// topology.arcs = topology.arcs.map(a => a.map(c => [...c]));

// Separate ring and line arcs

const ringArcs = [];

const lineArcs = [];

topology.arcs.forEach(arc => (isRing(arc)) ? ringArcs.push(arc) : lineArcs.push(arc));

// Add endpoints of line arcs to coordTypes as junctions

const coordTypes = traceResult.coordTypes.clone();

for (let arc of lineArcs) {

coordTypes.set(arc[0], "junction");

coordTypes.set(arc.at(-1), "junction");

}

// Rotate ring arcs to start on a junction if possible, or the closest point to the polygon center otherwise

const fnFindNewStart = (options.allowExpansion) ? (c => coordTypes.get(c) == "junction") : (c => !!coordTypes.get(c))

for (let arc of ringArcs) {

let newStart = fnFindNewStart(arc);

if (newStart < 0) {

if (Math.abs(d3.polygonArea(arc)) == 1) continue;

const centroid = d3.polygonCentroid(arc);

const distancesSquared = arc.map(c => (centroid[0] - c[0])**2 + (centroid[1] - c[1])**2);

const min = _.min(distancesSquared);

newStart = distancesSquared.indexOf(min);

}

if (newStart > 0) rotateRing(arc, newStart);

}

// Smooth topology

if (options.smooth) smoothTopology(topology, coordTypes, options.allowExpansion);

// Build topology.properties

topology.properties = {

options,

coordTypes

};

// nodeEdges(topology);

// Remove unneeded points

topology = presimplifyProtectJunctions(topology);

topology.arcs = topology.arcs.map(arc => arc.filter(c => c[2] !== 0));

return topology;

let st2 = {...sampleTopology};

st2.properties = {...st2.properties};

delete st2.properties.coordTypes;

st2 = _.cloneDeep(st2);

const tas = new TopoArcUtil(st2);

return tas.findArcId(st2.arcs[12].toReversed());

tas.splitAtIndex(0, 2);

return st2.arcs[0];

function isRing(arc) {

return eq(arc[0], arc.at(-1));

}

function eq(xy1, xy2) {

return (xy1 == xy2) || (xy1[0] == xy2[0] && xy1[1] == xy2[1]);

}

function isValueBetween(value, a, b) {

const min = (a < b) ? a : b;

const max = (min == a) ? b : a;

return value >= min && value <= max;

}

function isPointBetween(point, xy1, xy2) {

const [px, py] = point;

const [x1, y1] = xy1;

const [x2, y2] = xy2;

// Slope check

if ((py - y1) * (x2 - x1) != (y2 - y1) * (py - x1)) return false;

// Bounds check

if (!isValueBetween(px, x1, x2)) return false;

if (!isValueBetween(py, y1, y2)) return false;

return true;

}

class TopoArcUtil {

constructor(topology) {

this.topology = topology;

this.shiftedRingArcIds = new Set();

this.arcs = this.topology.arcs;

const allGeometries = [];

Object.values(topology.objects).forEach(o => turf.geomEach(o, g => allGeometries.push(g)));

const allArcArrays = [];

for (let geometry of allGeometries) {

switch (geometry.type) {

case "Polygon": allArcArrays.push(...geometry.arcs); break;

case "MultiPolygon": geometry.arcs.forEach(a => allArcArrays.push(...a)); break;

}

}

this._arcUsageIndex = new Map();

for (let arcArray of allArcArrays) {

for (let arcId of arcArray) {

this._addArcUsageToIndex(arcArray, arcId);

}

}

}

_addArcUsageToIndex(arcArray, arcId) {

if (arcId < 0) arcId = ~arcId;

if (!this._arcUsageIndex.has(arcId)) this._arcUsageIndex.set(arcId, []);

this._arcUsageIndex.get(arcId).push(arcArray);

}

findArcId(points) {

const [coord1, coord2] = points;

let foundArcId = undefined;

for (let arcId = 0; arcId < this.arcs.length; arcId++) {

let arc = this.arcs[arcId];

if (!arc) continue;

if (eq(coord1, arc[0]) && eq(coord2, arc[1])) foundArcId = arcId;

if (eq(coord1, arc.at(-1)) && eq(coord2, arc.at(-2))) foundArcId = ~arcId;

if (foundArcId !== undefined) break;

}

const foundArc = (foundArcId >= 0) ? this.arcs[foundArcId] : this.arcs[~foundArcId];

if (foundArc.length != points.length) throw "wyd";

return foundArcId;

}

shiftRing(arcId, index) {

if (this.shiftedRingArcIds.has(arcId)) throw "can't shift twice";

const arc = this.arcs[arcId];

if (!isRing(arc)) throw "not a ring";

arc.pop();

const newLeft = arc.splice(index);

arc.splice(0, 0, ...newLeft);

arc.push(arc[0]);

this.shiftedRingArcIds.add(arcId);

}

splitAtIndex(arcId, index) {

if (index == 0) return;

const arcs = this.arcs;

const arc = arcs[arcId];

if (index == arc.length -1) return;

if (isRing(arc) && !this.shiftedRingArcIds.has(arcId)) {

this.shiftRing(arcId, index);

return;

}

const [arcLeftId, arcRightId] = [arcId, arcs.length];

const [arcLeft, arcRight] = [arc.splice(0, index+1), arc.splice(index)]; // arcRight[0] == arcLeft.at(-1) == arc[index];

arcs[arcLeftId] = arcLeft;

arcs[arcRightId] = arcRight;

const negArcId = ~arcId;

for (let arcArray of this._arcUsageIndex.get(arcId) ?? []) {

this._addArcToIndex(arcArray, arcRightId);

const posIndex = arcArray.indexOf(arcLeftId);

if (posIndex >= 0) {

arcArray.splice(posIndex, 1, arcLeftId, arcRightId);

}

else {

const negIndex = arcArray.indexOf(~arcLeftId);

if (negIndex >= 0) {

arcArray.splice(negIndex, 1, ~arcRightId, ~arcLeftId);

}

}

}

}

splitAtPoint(arcId, point) {

const arc = this.arcs[arcId];

if (eq(arc[0], point)) return;

if (eq(arc.at(-1), point)) return;

for (let i = 1; i < arc.length-1; i++) {

if (eq(arc[i], point)) {

// exact match

this.splitAtIndex(arcId, i);

return;

}

const prev = arc[i-1];

if (isPointBetween(point, prev, arc[i])) {

// between two existing points

arc.splice(i, 0, point);

this.splitAtIndex(arcId, i);

return;

}

}

throw "couldn't splitAtPoint";

}

}

return TopoArcUtil;

}

const yValueSet = new Set();

const edgeArcs = new Set();

const x0 = topology.bbox[0];

const x1 = topology.bbox[2];

for (let i = 0; i < topology.arcs.length; i++) {

const arc = topology.arcs[i];

for (let [x, y] of arc) {

if (x == x0 || x == x1) {

yValueSet.add(y);

edgeArcs.add(arc);

}

}

}

const yValues = _.sortBy([...yValueSet]);

return yValues;

function getIntermediateValues(fromY, toY) {

if (fromY > toY) return getIntermediateValues(toY, fromY).toReversed();

return yValues.filter(y => y > fromY && y < toY);

}

for (let arc of edgeArcs) {

let oldArc = [...arc];

for (let i = 0; i < arc.length-1; i++) {

const [fromX, fromY] = arc[i];

if (fromX != x0 && fromX != x1) continue;

const [toX, toY] = arc[i+1];

if (toX != x0 && toX != x1) continue;

if (fromX != toX || fromY == toY) continue;

const newValues = getIntermediateValues(fromY, toY).map(y => [fromX, y]);

if (!newValues.length) continue;

arc.splice(i+1, 0, ...newValues);

}

}

function coordsEqual(c1, c2) {

return (c1[0] == c2[0] && c1[1] == c2[1]);

}

function maybePush(arc, coord) {

const prevCoord = arc.at(-1);

if (!prevCoord || !coordsEqual(prevCoord, coord)) arc.push(coord);

}

function getMaxShiftAmount(coordType, allowExpansion) {

if (!coordType) return Infinity;

if (!allowExpansion) return 0;

if (coordType == "corner" || coordType == "intrusion") return 0.25;

return 0;

}

function smoothArc(arc, coordTypes, allowExpansion) {

const arcCoordTypes = arc.map(c => coordTypes.get(c));

const smoothArc = [];

function getSegmentToNext(fromCoordIndex) {

const fromCoord = arc[fromCoordIndex];

if (!fromCoord) return;

const toCoord = arc[fromCoordIndex + 1];

if (!toCoord) return;

const axis = (fromCoord[0] != toCoord[0]) ? 0 : 1;

return {

fromCoordIndex, axis,

delta: toCoord[axis] - fromCoord[axis]

}

}

let coord, coordType,

prevSegment, nextSegment,

axis, delta, maxShiftAmount, shiftAmount;

for (let i = 0; i < arc.length; i++) {

coord = arc[i];

coordType = arcCoordTypes[i];

const maxShiftAmount = getMaxShiftAmount(coordType, allowExpansion);

if (!prevSegment || prevSegment.fromCoordIndex != i-1) {

prevSegment = getSegmentToNext(i-1);

}

if (prevSegment) {

let { delta, axis } = prevSegment;

delta *= -1;

shiftAmount = Math.sign(delta) * Math.min(maxShiftAmount, Math.abs(delta)/2);

const newCoord = [coord[0], coord[1]];

newCoord[axis] += shiftAmount;

maybePush(smoothArc, newCoord);

}

nextSegment = getSegmentToNext(i);

if (nextSegment) {

let { delta, axis } = nextSegment;

shiftAmount = Math.sign(delta) * Math.min(maxShiftAmount, Math.abs(delta)/2);

const newCoord = [coord[0], coord[1]];

newCoord[axis] += shiftAmount;

maybePush(smoothArc, newCoord);

}

prevSegment = nextSegment;

}

const first = arc[0];

const last = arc.at(-1);

if (first[0] == last[0] && first[1] == last[1]) {

maybePush(smoothArc, [...smoothArc[0]]);

}

return smoothArc;

}

function smoothTopology(topology, coordTypes, allowExpansion = true) {

// If any coord has a decimal part, don't smooth

for (let arc of topology.arcs) {

for (let coord of arc) {

if (~~coord[0] != coord[0] || ~~coord[1] != coord[1]) throw "topology has already been smoothed"

}

}

// Smooth

topology.arcs = topology.arcs.map(a => smoothArc(a, coordTypes, allowExpansion));

}

return smoothTopology;

function getSvgPath(polygon) {

const path = d3.path();

for (let ring of polygon.geometry.coordinates) {

path.moveTo(...ring[0]);

ring.slice(1).forEach(c => path.lineTo(...c));

path.closePath();

}

return svg`<path d="${path.toString()}">`;

}

const allCoords = Object.values(gcMergeResults).flat().map(f => turf.getCoords(f).flat()).flat();

const vb = Bbox.fromPoints(allCoords);

const result = svg`<svg

for (let polygon of gcMergeResults.newPolygons) {

const path = getSvgPath(polygon);

path.style.fill = "#ff000044";