Marching Squares Algorithm
Marching Squares algorithm - could be optimised, I guess
(By that I don't mean slapping Vectors all over the shop)
Click to sample an area for outline mapping
based on:
http://en.wikipedia.org/wiki/Marching_squares
@author Aaron Steed, nitrome.com
/**
* Copyright st33d ( http://wonderfl.net/user/st33d )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/yWi2
*/
package {
import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Graphics;
import flash.display.Shape;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
import flash.geom.Rectangle;
/**
* Marching Squares algorithm - could be optimised, I guess
* (By that I don't mean slapping Vectors all over the shop)
*
* Click to sample an area for outline mapping
*
* based on:
* http://en.wikipedia.org/wiki/Marching_squares
*
*
* @author Aaron Steed, nitrome.com
*/
[SWF(frameRate="30", backgroundColor = "#CCCCCC")]
public class FlashTest extends Sprite {
public var result:Shape;
public var check_image:BitmapData;
public var check_image_holder:Bitmap;
public var map_image:BitmapData;
public var map_image_holder:Bitmap;
public var mouse_pressed:Boolean;
public var mouse_count:int;
public var frame_count:int;
public static const WIDTH:Number = 465;
public static const HEIGHT:Number = 465;
public function FlashTest(){
init();
}
private function init():void {
initImages();
frame_count = 0;
mouse_count = -1;
mouse_pressed = false;
stage.addEventListener(MouseEvent.MOUSE_DOWN, mousePressed);
stage.addEventListener(MouseEvent.MOUSE_UP, mouseReleased);
addEventListener(Event.ENTER_FRAME, loop);
}
private function loop(e:Event = null):void {
if(mouse_pressed){
capture();
march();
}
frame_count++;
}
private function mousePressed(e:MouseEvent = null):void{
mouse_count = frame_count;
mouse_pressed = true;
}
private function mouseReleased(e:MouseEvent = null):void{
mouse_pressed = false;
}
private function capture():void{
check_image.fillRect(check_image.rect, 0xff0000ff);
check_image.copyPixels(map_image, new Rectangle( -1 + (mouseX / 4), -1 + (mouseY / 4), 14, 14), new Point(1,1));
}
public static const SCAN_POINTS:Array = [new Point(0, 0), new Point(1, 0), new Point(0, 1), new Point(1, 1)];
public static const UP:Point = new Point(0, -1);
public static const RIGHT:Point = new Point(1, 0);
public static const DOWN:Point = new Point(0, 1);
public static const LEFT:Point = new Point(-1, 0);
public static const MARCH:Array = [
RIGHT,//new Point(1, 0), // 0: 0000
DOWN,// new Point(0, 1), // 1: 0001
LEFT,// new Point(-1, 0), // 2: 0010
LEFT,// new Point(-1, 0), // 3: 0011
RIGHT,// new Point(1, 0), // 4: 0100
DOWN,// new Point(0, 1), // 5: 0101
LEFT,// new Point(-1, 0), // 6: 0110
LEFT,// new Point(-1, 0), // 7: 0111
UP,// new Point(0, -1), // 8: 1000
UP,// new Point(0, -1), // 9: 1001
UP,// new Point(0, -1), // 10: 1010
UP,// new Point(0, -1), // 11: 1011
RIGHT,// new Point(1, 0), // 12: 1100
DOWN,// new Point(0, 1), // 13: 1101
RIGHT// new Point(1, 0), // 14: 1110
];
private function march():void{
// get bounding box
var bounds:Rectangle = check_image.getColorBoundsRect(0xFFFFFFFF, 0xFFFF0000);
var gfx:Graphics = result.graphics;
gfx.clear();
gfx.lineStyle(5, 0);
var scale:Number = check_image_holder.scaleX;
var buffer:BitmapData = check_image.clone();
var j:int;
while(bounds.width + bounds.height > 0){
var pos:Point = new Point(bounds.x - 1, bounds.y - 1);
var loop:Point = null;
var index:int = getMarchVectorIndex(bounds.x - 1, bounds.y - 1);
var march_vector:Point = MARCH[index];
// fail safe
var i:int;
while(++i < 1000){
if((index) && !loop){
loop = pos.clone();
buffer.setPixel(loop.x + 1, loop.y + 1, 0xFFFF00);
gfx.moveTo((pos.x + 1) * scale, (pos.y + 1) * scale);
}
pos.x += march_vector.x;
pos.y += march_vector.y;
if(loop) gfx.lineTo((pos.x + 1) * scale, (pos.y + 1) * scale);
if(loop && pos.x == loop.x && pos.y == loop.y) break;
index = getMarchVectorIndex(pos.x, pos.y);
march_vector = MARCH[index];
}
check_image.floodFill(loop.x+1, loop.y+1, 0xFF0000FF);
bounds = check_image.getColorBoundsRect(0xFFFFFFFF, 0xFFFF0000);
// fail safe
if(++j > 100) break;
}
check_image.copyPixels(buffer, buffer.rect, new Point());
}
public function getMarchVectorIndex(x:int, y:int, col:uint = 0xFFFF0000):int{
var index:int = 0;
if(check_image.getPixel32(x+1, y+1) == col) index++;
if(check_image.getPixel32(x, y + 1) == col) index += 1 << 1;
if(check_image.getPixel32(x + 1, y) == col) index += 1 << 2;
if(check_image.getPixel32(x, y) == col) index += 1 << 3;
return index;
}
private function initImages():void{
map_image = new BitmapData(WIDTH >> 3, HEIGHT >> 2, true, 0xff0000ff);
map_image_holder = new Bitmap(map_image);
map_image_holder.scaleX = map_image_holder.scaleY = 4;
addChild(map_image_holder);
var rect:Rectangle = new Rectangle();
for(var i:int = 0; i < 100; i++) {
rect.x = Math.random() * map_image.width;
rect.y = Math.random() * map_image.height;
rect.width = Math.random() * 20;
rect.height = Math.random() * 20;
map_image.fillRect(rect, 0xffff0000);
}
check_image = new BitmapData(16, 16, true, 0xff00ff00);
check_image_holder = new Bitmap(check_image);
addChild(check_image_holder);
check_image_holder.scaleX = check_image_holder.scaleY = 14;
check_image_holder.x = WIDTH * 0.5;
result = new Shape();
addChild(result);
result.x = WIDTH * 0.5;
}
}
}