// Copyright 2016 Christian d'Heureuse, Inventec Informatik AG, Zurich, Switzerland // www.source-code.biz, www.inventec.ch/chdh // // License: GPL, GNU General Public License, http://www.gnu.org/licenses/gpl.html // Home page: http://www.source-code.biz/snippets/typescript/patterns /// /// /// namespace SquareGridPatternFinder1 { import absSmi = Utils.absSmi; import assertSmi = Utils.assertSmi; import BitSpace = Utils.BitSpace; import BivariateNumericFunction = Utils.BivariateNumericFunction; import hypot = Polyfills.hypot; import makeSmi = Utils.makeSmi; import Point = Utils.Point; import UnivariateNumericFunction = Utils.UnivariateNumericFunction; import wrap = Utils.wrap; export enum FieldType {scalar, vector, vectorDir}; export class FieldConfig { influenceRange: number; // integer squareRange: boolean; // true = square, false = circular fieldFunction: UnivariateNumericFunction; // field strength as a function of distance fieldType: FieldType; foldingFactor: number | null; // integer, only for vector fields dirFunction: UnivariateNumericFunction | null; // directional lock-in function (boost value as a function of angle in the range -pi..+pi) targetFunction: UnivariateNumericFunction;}// input: field strength, output: >=0 = the lower the better, <0 = not selectable export class FinderConfig { stepWidth: number; // integer fieldConfigs: FieldConfig[]; aggregateFunction: Function | null; } // input: field target values, output: >=0 = the lower the better, <0 = not selectable // aggregateFunction is ignored if there is only a single field. //--- Finder ------------------------------------------------------------------- // Architecture: finder -> aggregator -> targetFunction -> integrator -> fieldFunction export class Finder implements SquareGridPatternGenerator.Finder { private bitSpace: BitSpace; private config: FinderConfig; private aggregator: FieldAggregator; constructor (bitSpace: BitSpace, config: FinderConfig) { this.bitSpace = bitSpace; this.config = config; assertSmi(config.stepWidth); let n = config.fieldConfigs.length; let integrators: FieldIntegrator[] = Array(n); let targetFunctions: UnivariateNumericFunction[] = Array(n); for (let i = 0; i < n; i++) { let fieldConfig = config.fieldConfigs[i]; integrators[i] = this.createFieldIntegrator(fieldConfig); targetFunctions[i] = fieldConfig.targetFunction; } this.aggregator = new FieldAggregator(integrators, targetFunctions, config.aggregateFunction); } private createFieldIntegrator (fieldConfig: FieldConfig) : FieldIntegrator { assertSmi(fieldConfig.influenceRange); switch (fieldConfig.fieldType) { case FieldType.scalar: { return new ScalarFieldIntegrator(this.bitSpace, fieldConfig); } case FieldType.vector: { return new VectorFieldIntegrator(this.bitSpace, fieldConfig); } case FieldType.vectorDir: { return new VectorDirFieldIntegrator(this.bitSpace, fieldConfig); } default: { throw new Error(); }}} public findNextPoint (p0: Point) : Point | null { let x0: number = makeSmi(p0.x); let y0: number = makeSmi(p0.y); var optX: number | null = null; var optY: number | null = null; var optAggr: number | null = null; let bitSpace = this.bitSpace; let width = makeSmi(bitSpace.width); let height = makeSmi(bitSpace.height); let d = makeSmi(this.config.stepWidth); let aggregator = this.aggregator; for (let dy = -d; dy <= d; dy++) { for (let dx = -d; dx <= d; dx++) { let x = wrap(x0 + dx, width); let y = wrap(y0 + dy, height); if (!bitSpace.getCell(x, y)) { let aggr = aggregator.aggregate(x, y); if (aggr >= 0 && (aggr < optAggr || optAggr == null)) { optX = x; optY = y; optAggr = aggr; }}}} if (optX == null || optY == null) { return null; } return {x: optX, y: optY}; }} //--- Field Aggregator --------------------------------------------------------- class FieldAggregator { private integrators: FieldIntegrator[]; private targetFunctions: UnivariateNumericFunction[]; private aggregateFunction: Function | null; private targetValues: number[]; constructor (integrators: FieldIntegrator[], targetFunctions: UnivariateNumericFunction[], aggregateFunction: Function | null) { this.integrators = integrators; this.targetFunctions = targetFunctions; this.aggregateFunction = aggregateFunction; this.targetValues = Array(integrators.length); } public aggregate (x: number, y: number) : number { let n = this.integrators.length; let targetValues = this.targetValues; for (let i = 0; i < n; i++) { let v = this.integrators[i].integrate(x, y); targetValues[i] = this.targetFunctions[i](v); } if (n == 1) { return targetValues[0]; } return this.aggregateFunction!.apply(null, targetValues); }} //--- Field integrators -------------------------------------------------------- interface FieldIntegrator { integrate: BivariateNumericFunction; } class ScalarFieldIntegrator implements FieldIntegrator { private bitSpace: BitSpace; private fieldConfig: FieldConfig; private fieldMap: Float64Array; // maps relative coordinates to scalar field values constructor (bitSpace: BitSpace, fieldConfig: FieldConfig) { this.bitSpace = bitSpace; this.fieldConfig = fieldConfig; this.fieldMap = Calc.createScalarFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange); } public integrate (px: number, py: number) : number { let sum: number = 0; let bitSpace = this.bitSpace; let width = makeSmi(bitSpace.width); let height = makeSmi(bitSpace.height); let r = makeSmi(this.fieldConfig.influenceRange); // makeSmi() is necessary here for V8 optimization!? It's not clear why. let w = makeSmi(r + r + 1); let fieldMap = this.fieldMap; for (let dy = -r; dy <= r; dy++) { let y = wrap(py + dy, height); let mapNdxBase = (dy + r) * w + r; for (let dx = -r; dx <= r; dx++) { let x = wrap(px + dx, width); if (bitSpace.getCell(x, y)) { let p = mapNdxBase + dx; sum += fieldMap[p]; }}} return sum; }} class VectorFieldIntegrator implements FieldIntegrator { private bitSpace: BitSpace; private fieldConfig: FieldConfig; private fieldMap: Float64Array; // maps relative coordinates to vector field X/Y values constructor (bitSpace: BitSpace, fieldConfig: FieldConfig) { this.bitSpace = bitSpace; this.fieldConfig = fieldConfig; this.fieldMap = Calc.createVectorFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange, fieldConfig.foldingFactor!); } public integrate (px: number, py: number) : number { let v = integrateVector(px, py, this.bitSpace, this.fieldConfig.influenceRange, this.fieldMap); let strength = hypot(v.x, v.y); return strength; }} function integrateVector (px: number, py: number, bitSpace: BitSpace, influenceRange: number, fieldMap: Float64Array) : Point { let sumX: number = 0; let sumY: number = 0; let width = makeSmi(bitSpace.width); let height = makeSmi(bitSpace.height); let r = makeSmi(influenceRange); // makeSmi() is necessary here for V8 optimization!? It's not clear why. let w = makeSmi(r + r + 1); for (let dy = -r; dy <= r; dy++) { let y = wrap(py + dy, height); let mapNdxBase = 2 * ((dy + r) * w + r); for (let dx = -r; dx <= r; dx++) { let x = wrap(px + dx, width); if (bitSpace.getCell(x, y)) { let p = mapNdxBase + dx + dx; sumX += fieldMap[p]; sumY += fieldMap[p + 1]; }}} return {x: sumX, y: sumY}; } class VectorDirFieldIntegrator implements FieldIntegrator { private bitSpace: BitSpace; private fieldConfig: FieldConfig; private scalarFieldMap: Float64Array; // maps relative coordinates to scalar field values private vectorFieldMap: Float64Array; // maps relative coordinates to vector field X/Y values private angleMap: Float64Array; // maps relative coordinates to angles in the range -pi..+pi private dirFunctionCached: UnivariateNumericFunction; constructor (bitSpace: BitSpace, fieldConfig: FieldConfig) { this.bitSpace = bitSpace; this.fieldConfig = fieldConfig; this.scalarFieldMap = Calc.createScalarFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange); this.vectorFieldMap = Calc.createVectorFieldMap(fieldConfig.fieldFunction, fieldConfig.influenceRange, fieldConfig.squareRange, fieldConfig.foldingFactor!); this.angleMap = Calc.createAngleMap(fieldConfig.influenceRange, fieldConfig.foldingFactor!); this.dirFunctionCached = Utils.createLinearInterpolationCacheFunction(fieldConfig.dirFunction!, -Math.PI, Math.PI, 0x1001); } public integrate (px: number, py: number) : number { let v = integrateVector(px, py, this.bitSpace, this.fieldConfig.influenceRange, this.vectorFieldMap); if (v.x == 0 && v.y == 0) { return 0; } let directionAngle = Math.atan2(v.y, v.x); // let directionStrength = hypot(v.x, v.y); return this.computeFieldStrengthDirected(px, py, directionAngle); } private computeFieldStrengthDirected (px: number, py: number, directionAngle: number) : number { let sum: number = 0; let bitSpace = this.bitSpace; let width = makeSmi(bitSpace.width); let height = makeSmi(bitSpace.height); let r = makeSmi(this.fieldConfig.influenceRange); // makeSmi() is necessary here for V8 optimization!? It's not clear why. let w = makeSmi(r + r + 1); let dirFunctionCached = this.dirFunctionCached; for (let dy = -r; dy <= r; dy++) { let y = wrap(py + dy, height); let mapNdxBase = (dy + r) * w + r; for (let dx = -r; dx <= r; dx++) { let x = wrap(px + dx, width); if (bitSpace.getCell(x, y)) { let p = mapNdxBase + dx; let level = this.scalarFieldMap[p]; let angle = this.angleMap[p]; let relAngle = Utils.normalizeAngle(angle - directionAngle); let directionalBoost = dirFunctionCached(relAngle); // console.log("direction=" + direction + " dx=" + dx + " dy=" + dy + " angle=" + angle + " relAngle=" + relAngle + " dirBoost=" + directionalBoost + " level=" + level); sum += level * directionalBoost; }}} return sum; }} //--- Field calculations ------------------------------------------------------- class Calc { public static calcPointFieldStrength (dx: number, dy: number, fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean) : number { const eps = 1E-9; if (dx > -eps && dx < eps && dy > -eps && dy < eps) { return 0; } // field value at 0,0 is undefined and must have no effect if (dx < -range - eps || dx > range + eps || dy < -range - eps || dy > range + eps) { return 0; } let d = hypot(dx, dy); if (!squareRange && d > range + eps) { return 0; } return fieldFunction(d); } public static createScalarFieldMap (fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean) : Float64Array { let w = 2 * range + 1; let map = new Float64Array(w * w); for (let dy = -range; dy <= range; dy++) { for (let dx = -range; dx <= range; dx++) { let p = (dy + range) * w + dx + range; map[p] = Calc.calcPointFieldStrength(dx, dy, fieldFunction, range, squareRange); }} return map; } public static calcPointFieldVector (dx: number, dy: number, fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean, foldingFactor: number) : Point { const eps = 1E-9; if (dx > -eps && dx < eps && dy > -eps && dy < eps) { return new Point(0, 0); } // field value at 0,0 is undefined and must have no effect if (dx < -range - eps || dx > range + eps || dy < -range - eps || dy > range + eps) { return new Point(0, 0); } let d = hypot(dx, dy); if (!squareRange && d > range + eps) { return new Point(0, 0); } let fieldStrength = fieldFunction(d); if (foldingFactor == 1) { let vx = dx / d * fieldStrength; let vy = dy / d * fieldStrength; return new Point(vx, vy); } let arg = Math.atan2(dy, dx) * foldingFactor; let vx = Math.cos(arg) * fieldStrength; let vy = Math.sin(arg) * fieldStrength; // console.log("y=" + dy + " x=" + dx + " d=" + d + " arg=" + arg + " vy=" + vy + " vx=" + vx); return new Point(vx, vy); } public static createVectorFieldMap (fieldFunction: UnivariateNumericFunction, range: number, squareRange: boolean, foldingFactor: number) : Float64Array { let w = 2 * range + 1; let map = new Float64Array(2 * w * w); for (let dy = -range; dy <= range; dy++) { for (let dx = -range; dx <= range; dx++) { let v = Calc.calcPointFieldVector(dx, dy, fieldFunction, range, squareRange, foldingFactor); let p = 2 * ((dy + range) * w + dx + range); map[p ] = v.x; map[p + 1] = v.y; }} return map; } public static calcPointAngle (dx: number, dy: number, foldingFactor: number) { let a = Math.atan2(dy, dx); return Utils.normalizeAngle(a * foldingFactor); } public static createAngleMap (range: number, foldingFactor: number) : Float64Array { let w = 2 * range + 1; let map = new Float64Array(w * w); for (let dy = -range; dy <= range; dy++) { for (let dx = -range; dx <= range; dx++) { let p = (dy + range) * w + dx + range; map[p] = Calc.calcPointAngle(dx, dy, foldingFactor); }} return map; }} //--- Info --------------------------------------------------------------------- export function genScalarFieldInfo (fieldFunction: UnivariateNumericFunction, influenceRange: number, squareRange: boolean) : string { let minSum = 0, maxSum = 0, fullSum = 0; let r = influenceRange; for (let dy = -r; dy <= r; dy++) { for (let dx = -r; dx <= r; dx++) { let fieldStrength = Calc.calcPointFieldStrength(dx, dy, fieldFunction, r, squareRange); if (fieldStrength < 0) { minSum += fieldStrength; } if (fieldStrength > 0) { maxSum += fieldStrength; } fullSum += fieldStrength; }} return (minSum == 0 ? "" : "min=" + minSum.toFixed(2) + " ") + "max=" + maxSum.toFixed(2) + (fullSum == maxSum ? "" : " full=" + fullSum.toFixed(2)); } export function genVectorFieldInfo (fieldFunction: UnivariateNumericFunction, influenceRange: number, squareRange: boolean, foldingFactor: number) : string { // const eps = 1E-9; // let sum180 = 0, sum90x = 0, sum90y = 0; // let sum = new Point(0, 0); // let sec: Point[] = Array(5); // for (let i = 0; i < 5; i++) { // sec[i] = new Point(0, 0); } let sumX = 0; let r = influenceRange; for (let dy = -r; dy <= r; dy++) { for (let dx = -r; dx <= r; dx++) { let v = Calc.calcPointFieldVector(dx, dy, fieldFunction, r, squareRange, foldingFactor); // if (v.x > 0) { // sum180 += v.x; } // if (v.x >= -eps && v.y >= -eps) { // sum90x += v.x; // sum90y += v.y; }} // sum.x += v.x; sum.y += v.y; // let i = getVectorSectorOrAxis(v); // sec[i].x += v.x; // sec[i].y += v.y; if (v.x > 0) { sumX += v.x; } }} // let sum90 = hypot(sum90x, sum90y); // return "sum180=" + sum180.toFixed(2) + " sum90=" + sum90.toFixed(2) + " (" + sum90x.toFixed(2) + ", " + sum90y.toFixed(2) + ")"; // return "sum=" + sum.x + "/" + sum.y; // let s = "
"; // for (let i = 0; i < 5; i++) { // s += "sec" + i + "=" + sec[i].x + "/" + sec[i].y + " "; } // return s; } return "max=" + sumX.toFixed(2); } function getVectorSector (v: Point) : number { const eps = 1E-9; if (v.x >= eps && v.y > -eps) { return 0; } else if (v.x < eps && v.y >= eps) { return 1; } else if (v.x <= -eps && v.y < eps) { return 2; } else { return 3; }} // Returns 4 if the point is on the x or y axis. function getVectorSectorOrAxis (v: Point) : number { const eps = 1E-9; if (v.x > -eps && v.x < eps || v.y > -eps && v.y < eps) { return 4; } if (v.y > 0) { if (v.x > 0) { return 0; } else { return 1; }} else { if (v.x < 0) { return 2; } else { return 3; }}} } // end namespace SquareGridFinder1