gridfinder - npm Package Compare versions

Comparing version 1.49.0 to 1.56.0

lib/debugDetectGrid.js

@@ -33,2 +33,3 @@ import * as detectGrid from "./detectGrid.js";
 	let points = self.points(data);
+	console.log(points);
 	self.range = new ColorRange(points.map(p => p.val));
@@ -89,19 +90,8 @@
 		points(data) {
-			let out = [];
-
 			let rows = detectGrid.scoreRows(data);
-			let threshold = util.nth([...rows], detectGrid.TOP_LINES, util.numericDesc);
-			rows.forEach((val, y) => {
-				if (val > threshold)
-					out.push({val, y});
-			});
-			
 			let cols = detectGrid.scoreCols(data);
-			threshold = util.nth([...cols], detectGrid.TOP_LINES, util.numericDesc);
-			cols.forEach((val, x) => {
-				if (val > threshold)
-					out.push({val, x});
-			});
-
-			return out;
+			return [
+				...detectGrid.bestPoints(rows).map(y => ({y, val: rows[Math.round(y)]})),
+				...detectGrid.bestPoints(cols).map(x => ({x, val: cols[Math.round(x)]})),
+			];
 		},
@@ -108,0 +98,0 @@

lib/detectGrid.js

 import {findGrid1d} from "./findGrid.js";
-import {averageInliers, nth, numericAsc, numericDesc, percentile} from "./util.js";
+import {averageInliers, nth, numericAsc, numericDesc, percentile, roundErrorFraction} from "./util.js";
 
@@ -23,3 +23,3 @@ function* probes(limit) {
 
-	let lavg = sum;
+	let lavg = 0;
 	for (let i = from; i < x; i++) {
@@ -31,3 +31,3 @@ let off = offset(i, y) * 4;
 
-	let ravg = sum;
+	let ravg = 0;
 	for (let i = x + 1; i <= to; i++) {
@@ -72,10 +72,44 @@ let off = offset(i, y) * 4;
 
-export const TOP_LINES = 16;
+export function bestPoints(line) {
+	let threshold = nth([...line], Math.log2(line.length)|0, numericDesc);
 
+	let r = [];
+	for (let i = 0; i < line.length; i++) {
+		let maxv = line[i]
+		if (maxv < threshold) continue;
+		let maxi = i;
+
+		while (i + 1 < line.length) {
+			let v = line[++i]
+			if (v < threshold) break;
+			if (v <= maxv) continue;
+
+			maxv = v;
+			maxi = i;
+		}
+
+		if (maxi == 0 || maxi + 1 == line.length) {
+			r.push(maxi);
+			continue;
+		}
+
+		let iv = maxi;
+
+		let pow = 1;
+		maxv = Math.pow(maxv, pow)
+		let left = Math.pow(line[maxi-1], pow);
+		let right = Math.pow(line[maxi+1], pow);
+
+		if ( left != right ) {
+			maxi += 0.5 * (right - left) / (maxv - Math.min(left, right));
+		}
+
+		r.push(maxi);
+	}
+	return r;
+}
+
 function detectGrid1d(line) {
-	let sorted = line.map((value, point) => ({value, point}));
-	sorted.sort((b, a) => a.value - b.value);
+	let bestLines = bestPoints(line);
 
-	let limit = Math.min(TOP_LINES, sorted.length);
-
 	let best = 0;
@@ -86,17 +120,49 @@ let bestsize = Infinity;
 
-	for (let ai = 0; ai < limit-1; ai++) {
-		let a = sorted[ai];
-		for (let bi = ai+1; bi < limit; bi++) {
-			let b = sorted[bi];
+	for (let ai = 0; ai < bestLines.length-1; ai++) {
+		let a = bestLines[ai];
+		for (let bi = ai+1; bi < bestLines.length; bi++) {
+			let b = bestLines[bi];
 
-			let size = Math.abs(a.point - b.point);
+			let size = b - a;
 			if (size < 8) continue;
-			let off = a.point % size;
 
+			let distance = size;
+			for (let i = 0; i < bestLines.length; i++) {
+				if (i == ai || i == bi) continue;
+				let p = bestLines[i];
+				let da = Math.abs(p - a);
+				let db = Math.abs(p - b);
+
+				if (roundErrorFraction(da, size) > 0.01 || roundErrorFraction(db, size) > 0.01)
+					continue;
+
+				let d;
+				if (da > db)
+					d = da;
+				else
+					d = db;
+
+				if (d < distance) continue;
+
+				distance = d;
+				size = d / Math.round(d / size);
+			}
+
+			let off = b % size;
+
 			let avg = 0;
 			for (let p = off; p < line.length; p += size) {
-				avg += Math.sqrt(line[p]);
+				let floor = p|0;
+				let ceil = floor + 1;
+
+				let v;
+				if (ceil < line.length)
+					v = line[floor] * (p - floor + 1) + line[ceil] * (ceil - p + 1);
+				else
+					v = line[floor];
+
+				avg += Math.sqrt(v);
 			}
 			avg /= (line.length - off) / size + 1;
-			avg /= Math.sqrt(size); // Prefer smaller grids.
+			avg /= size; // Prefer smaller grids.
 
@@ -107,3 +173,3 @@ if (avg <= best) continue;
 			bestsize = size;
-			bestpoint = a.point;
+			bestpoint = b;
 			bestoff = off;
@@ -127,2 +193,4 @@ }
 
+	console.log("heihgt");
+
 	let rows = scoreRows(img);
@@ -129,0 +197,0 @@ let ydim = detectGrid1d(rows);

lib/detectGrid.test.js

@@ -12,13 +12,17 @@ import * as gridfinder from "./lib.js";
 		"crossroad-keep.jpg": {
-			width: 11, // 22.25,
-			height: 10, // Wrong, non-integer.
-			offTolerance: 10, // Wrong.
+			width: 29.41,
 		},
+		// "dragons-lair.jpg": {
+		// 	width: 35,
+		// },
 		// "grass.jpg": {
 		// 	width: 12.5,
 		// },
+		"forest-camp.jpg": {
+			width: 64,
+		},
 		"irish-pub.jpg": {
 			width: 70,
-			height: 11, // Wrong
-			offY: -3, // Wrong.
+			heightTolerance: 10, // Wrong, detects roof tiles.
+			offY: 4, // Wrong.
 		},
@@ -28,21 +32,29 @@ "mythictable-tutorial.jpg": {
 		},
-		"overgrown-courtyard.jpg": {
-			width: 35,
-			height: 20, // Wrong
-			offY: -5,
-		},
+		// "overgrown-courtyard.jpg": {
+		// 	width: 35
+		// },
 		"floating-islands.jpg": {
 			width: 17.06,
-			offTolerance: 5, // Wrong, but we don't do non-integer grids yet.
 		},
-		// "spaceship-main-blur.jpg": {
-		// 	width: 10.66,
-		// 	tolerance: 0.1,
-		// 	offTolerance: 5,
-		// },
-		// "spaceship-main-sharp.jpg": {
-		// 	width: 10.66,
-		// 	tolerance: 0.1,
-		// 	offTolerance: 5,
-		// },
+		"spaceship-main-blur.jpg": {
+			width: 10.66,
+			tolerance: 0.02,
+			offTolerance: 10, // Wrong.
+		},
+		"spaceship-main-sharp.jpg": {
+			width: 10.66,
+			tolerance: 0.02,
+			offTolerance: 5, // Wrong.
+		},
+		"water-temple-low.jpg": {
+			width: 32,
+		},
+		"water-temple-medium.jpg": {
+			width: 32,
+			offTolerance: 3, // Wrong.
+		},
+		"water-temple-high.jpg": {
+			width: 32,
+			offTolerance: 3, // Wrong.
+		},
 		// "xak-tsaroth.jpg": {
@@ -57,2 +69,4 @@ // 	width: 35,
 				tolerance=0.01,
+				widthTolerance=tolerance,
+				heightTolerance=tolerance,
 
@@ -76,8 +90,8 @@ offX=0,
 
-			assert(Math.abs(cellSize.width/width - 1) < tolerance, `Expected width ${width} got ${cellSize.width}`);
-			assert(Math.abs(cellSize.height/height - 1) < tolerance, `Expected height ${height} got ${cellSize.height}`);
-			assert(Math.abs(offset.x - offX) < offTolerance, `Expected X-off ${offX} got ${offset.x}`);
-			assert(Math.abs(offset.y - offY) < offTolerance, `Expected Y-off ${offY} got ${offset.y}`);
+			assert(Math.abs(cellSize.width/width - 1) < widthTolerance, `Expected width ${width} got ${cellSize.width}`);
+			assert(Math.abs(cellSize.height/height - 1) < heightTolerance, `Expected height ${height} got ${cellSize.height}`);
+			assert(Math.abs(offset.x - offX) < offTolerance, `Expected offX ${offX} got ${offset.x}`);
+			assert(Math.abs(offset.y - offY) < offTolerance, `Expected offY ${offY} got ${offset.y}`);
 		})
 	})
 })

lib/util.js

@@ -31,1 +31,9 @@ export function numericAsc(a, b) { return a - b }
 }
+
+export function roundError(v, multiple=1) {
+	return v - Math.round(v / multiple) * multiple;
+}
+
+export function roundErrorFraction(v, multiple=1) {
+	return Math.abs(roundError(v, multiple) / v);
+}

package.json

 {
   "name": "gridfinder",
-  "version": "1.49.0",
+  "version": "1.56.0",
   "license": "Apache 2.0",
@@ -5,0 +5,0 @@ "homepage": "https://gridfinder.kevincox.ca",

No alert changes

Improved metrics

Total package byte prevSize

10331748

increased by18.98%

Number of package files

51

increased by18.6%

Lines of code

1276

increased by5.37%

No dependency changes