Created
January 26, 2015 11:04
-
-
Save soywiz/7e83eaaea2d2c19696af to your computer and use it in GitHub Desktop.
Haxe: Calculate distance-map in linear time
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package ; | |
import haxe.Log; | |
import haxe.ds.Vector; | |
import haxe.io.Bytes; | |
class Fixer { | |
static public function main() { | |
var m = Matrix.fromRows([ | |
[0, 0, 0, 1, 0, 1, 1], | |
[0, 0, 0, 1, 0, 0, 0], | |
[0, 0, 0, 1, 0, 0, 0], | |
[0, 0, 0, 0, 0, 0, 0], | |
[0, 0, 0, 0, 0, 0, 0] | |
]).transform(function(x, y, v) { | |
//trace(v); | |
var node = new Node(x, y, (v != 0)); | |
if (node.value) node.nearest = node; | |
return node; | |
}); | |
var nearestNode = null; | |
var nearestNode2 = null; | |
for (kind in [ | |
{ columnsRows: false, reverse: false }, | |
{ columnsRows: false, reverse: true }, | |
{ columnsRows: true, reverse: false }, | |
{ columnsRows: true, reverse: true } | |
]) { | |
m.iterate(kind.columnsRows, kind.reverse, function(x, y) { | |
nearestNode = null; | |
nearestNode2 = null; | |
}, function(x, y, current) { | |
if (current.value) { | |
nearestNode = current; | |
} else { | |
current.tryUpdateWithNode(nearestNode); | |
current.tryUpdateWithNode(nearestNode2); | |
} | |
nearestNode2 = current.nearest; | |
}); | |
} | |
m.dump(','); | |
} | |
} | |
class Node { | |
public var value:Bool; | |
public var x:Int; | |
public var y:Int; | |
public var nearest(default, set):Node = null; | |
public var distance(default, null):Float; | |
public function new(x:Int, y:Int, value:Bool) { | |
this.x = x; | |
this.y = y; | |
this.value = value; | |
this.distance = Math.POSITIVE_INFINITY; | |
} | |
private function set_nearest(node:Node):Node { | |
this.nearest = node; | |
this.distance = calculateDistance(this, node); | |
return node; | |
} | |
public function tryUpdateWithNode(possibleNearestNode:Node) { | |
if (possibleNearestNode == null) return; | |
if (Node.calculateDistance(possibleNearestNode, this) < this.distance) { | |
this.nearest = possibleNearestNode; | |
} | |
} | |
static public function calculateDistance(a:Node, b:Node):Float { | |
if (a == null || b == null) return Math.POSITIVE_INFINITY; | |
var x = a.x - b.x; | |
var y = a.y - b.y; | |
return Math.sqrt(x * x + y * y); | |
} | |
public function toString() { | |
return '' + Std.int(distance); | |
}//return value ? '1' : '0'; | |
} | |
class Matrix<T> { | |
private var data:Vector<T>; | |
public var width(default, null):Int; | |
public var height(default, null):Int; | |
@:generic static public function fromRows<T>(rows:Array<Array<T>>):Matrix<T> { | |
var height = rows.length; | |
var width = rows[0].length; | |
var matrix = new Matrix(width, height); | |
for (row in 0 ... height) { | |
for (column in 0 ... width) { | |
matrix.set(column, row, rows[row][column]); | |
} | |
} | |
return matrix; | |
} | |
public function new(width:Int, height:Int) { | |
this.data = new Vector<T>(width * height); | |
this.width = width; | |
this.height = height; | |
} | |
public function transform<T2>(transformer: Int -> Int -> T -> T2):Matrix<T2> { | |
var that = new Matrix<T2>(width, height); | |
for (y in 0 ... height) { | |
for (x in 0 ... width) { | |
that.set(x, y, transformer(x, y, this.get(x, y))); | |
} | |
} | |
return that; | |
} | |
private inline function getIndex(x:Int, y:Int) { | |
return y * width + x; | |
} | |
public function get(x:Int, y:Int):T { | |
return this.data[getIndex(x, y)]; | |
} | |
public function iterate(columnsRows:Bool, reverse:Bool, startLine: Int -> Int -> Void, cell: Int -> Int -> T -> Void) { | |
if (columnsRows) { | |
iterateColumns(reverse, startLine, cell); | |
} else { | |
iterateRows(reverse, startLine, cell); | |
} | |
} | |
public function iterateColumns(reverse:Bool, startLine: Int -> Int -> Void, cell: Int -> Int -> T -> Void) { | |
for (x in 0 ... width) { | |
startLine(x, 0); | |
for (y in 0 ... height) { | |
var yy = (reverse) ? height - y - 1 : y; | |
cell(x, yy, get(x, yy)); | |
} | |
} | |
} | |
public function iterateRows(reverse:Bool, startLine: Int -> Int -> Void, cell: Int -> Int -> T -> Void) { | |
for (y in 0 ... height) { | |
startLine(0, y); | |
for (x in 0 ... width) { | |
var xx = (reverse) ? width - x - 1 : x; | |
cell(xx, y, get(xx, y)); | |
} | |
} | |
} | |
public function set(x:Int, y:Int, value:T):T { | |
this.data[getIndex(x, y)] = value; | |
return value; | |
} | |
public function dump(separator = '') { | |
for (y in 0 ... height) { | |
var parts = []; | |
for (x in 0 ... width) { | |
parts.push('' + get(x, y)); | |
} | |
trace(parts.join(separator)); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment