In case Flash no longer exists; a copy of this site is included in the Flashpoint archive's "ultimate" collection.

Dead Code Preservation :: Archived AS3 works from wonderfl.net

Triangle Mesh Morphing (Radial Triangulation)

Click to change image
クリックで画像自動生成します
2つのBitmapData画像を与えて、その中間画像を生成します (モーフィング)
 特徴点らしきものを抽出し、2つの特徴点を比較しながら
自動で三角メッシュを生成します。
メッシュの対応付けを簡単にするため画像の重心から
放射状にメッシュを生成します。
三角メッシュ生成やマッチングまたはトランジションによって
いろいろと変形画像は変えられます
 しかし、大雑把なメッシュ生成のため
画像によっては綺麗に変形できません
特に、はずれ特徴点があるときはうまくいかないことが多いです
マッチング用のパラメーターをいじれば多少ましになるかも
/**
 * Copyright heriet ( http://wonderfl.net/user/heriet )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/ujzg
 */

//
// Click to change image
// クリックで画像自動生成します
// 
// 2つのBitmapData画像を与えて、その中間画像を生成します (モーフィング)
//
// 特徴点らしきものを抽出し、2つの特徴点を比較しながら
// 自動で三角メッシュを生成します。
// メッシュの対応付けを簡単にするため画像の重心から
// 放射状にメッシュを生成します。
// 
// 三角メッシュ生成やマッチングまたはトランジションによって
// いろいろと変形画像は変えられます
// 
// しかし、大雑把なメッシュ生成のため
// 画像によっては綺麗に変形できません
// 特に、はずれ特徴点があるときはうまくいかないことが多いです
// 
// マッチング用のパラメーターをいじれば多少ましになるかも
//


package  
{
  import flash.display.Bitmap;
  import flash.display.BitmapData;
  import flash.display.Graphics;
  import flash.display.Sprite;
  import flash.display.Shape;
  import flash.filters.ConvolutionFilter;
  import flash.geom.Point;
  import flash.events.Event;
  import flash.events.MouseEvent;
  import flash.display.Loader;
  import net.wonderfl.utils.SequentialLoader;
  
  [SWF(width="465", height="465", frameRate = "60", backgroundColor="0x00FF00")]
  public class TriangleMorphWonderfl extends Sprite
  {
    private static const POINT_ZERO:Point = new Point();
    private static const SOURCE_URL:String = "http://assets.wonderfl.net/images/related_images/8/89/89eb/89ebbef01488d88e537cd4bd36da53a4c971fdd9";
    private static const DESTINATION_URL:String = "http://assets.wonderfl.net/images/related_images/5/5f/5f41/5f41402638adb4c6c95767b2c2ece5cacbd5681f";
    private var _imageArray:Array = [];
    private var transitions:Array = [Transitions.LINEAR, Transitions.POW2, Transitions.SINE];
		
    private var source:BitmapData;
    private var destination:BitmapData;
        
    private var morphSprite:TriangleMorphSprite;
    
    private var sourceGenerator:Sprite;
    private var destinationGenerator:Sprite;
    private var frameCount:int;
    
    private var radialMapping:Radial = new Radial();
    private var interFrames:int;
    
    public function TriangleMorphWonderfl() 
    {
      //initialize();
      SequentialLoader.loadImages([SOURCE_URL, DESTINATION_URL], _imageArray, imageLoadedHandler);

    }
    private function imageLoadedHandler():void
    {
      var ldr:Loader = _imageArray.pop();
      destination = new BitmapData(ldr.width, ldr.height, true, 0);
      destination.draw(ldr);
      
      ldr = _imageArray.pop();
      source = new BitmapData(ldr.width, ldr.height, true, 0);
      source.draw(ldr);
      
      generateMorphImage();
    }
    private function clickHandler(e:MouseEvent):void
    {
      stage.removeEventListener(MouseEvent.CLICK, clickHandler);
      removeEventListener(Event.ENTER_FRAME, enterFrameHandler);
      initialize();
    }
    public function initialize():void
    {
      while (numChildren > 0) 
        removeChildAt(0);
      
      sourceGenerator = new Sprite();
      destinationGenerator = new Sprite();
      
      if (source != null)
        source.dispose();
      if (destination != null)
        destination.dispose();
      
      source = new BitmapData(96, 96, true, 0);
      destination = new BitmapData(96, 96, true, 0);
      
      generateRandomGraphics(sourceGenerator.graphics);
      generateRandomGraphics(destinationGenerator.graphics);
      frameCount = 0;
      
      addEventListener(Event.ENTER_FRAME, waitFrame);
    }
    // tekito-
    private function generateRandomGraphics(g:Graphics):void
    {
      var i:int;
      var n:int;
      
      n = (int) (Math.random() * 4) + 1;
      
      for (i = 0; i < n; i++ ){
        g.beginFill(generateColor());
        g.drawEllipse((int) (Math.random() * 24 + 8), (int) (Math.random() * 24 + 8), (int) (Math.random() * 48 + 5), (int) (Math.random() * 48 + 5));
        g.endFill();
      }
      
      n = (int) (Math.random() * 4) + 1;
      for (i = 0; i < n; i++ ){
        g.beginFill(generateColor());
        g.drawRect((int) (Math.random() * 24 + 8), (int) (Math.random() * 24 + 8), (int) (Math.random() * 50 + 5), (int) (Math.random() * 48 + 5));
        g.endFill();
      }
      
      n = (int) (Math.random() * 4) + 1;
      for (i = 0; i < n; i++ ){
        g.beginFill(generateColor());
        var cx:int = (int) (Math.random() * 24 + 8);
        var cy:int = (int) (Math.random() * 24 + 8);
        var sx:int = (int) (Math.random() * 64);
        var sy:int = (int) (Math.random() * 64);
        g.moveTo(sx + cx, sy + cy);
        
        var m:int = (int) (Math.random() * 3) + 2;
        for (var j:int = 0; j < m;  j++){
          var dx:int = (int) (Math.random() * 32);
          var dy:int = (int) (Math.random() * 32);
          g.lineTo(dx + cx, dy + cy);
        }
        g.lineTo(sx + cx, sy + cy);
        g.endFill();
      }
    }
    private function generateColor():uint
    {
      var red:int = Math.random() * 64 + 196;
      var green:int = Math.random() * 196 + 64;
      var blue:int = Math.random() * 128 + 128;
      
      return (red << 16) + (green << 8) + blue;
    }
    // wait 2 frames for imageGenerator
    private function waitFrame(e:Event):void
    {
      removeEventListener(Event.ENTER_FRAME, waitFrame);
      addEventListener(Event.ENTER_FRAME, generateImage);
    }
    private function generateImage(e:Event):void
    {
      removeEventListener(Event.ENTER_FRAME, generateImage);
      
      source.draw(sourceGenerator);
      destination.draw(destinationGenerator);
      source.threshold(source, source.rect, POINT_ZERO, '!=', 0xFF000000, 0, 0xFF000000);
      destination.threshold(destination, destination.rect, POINT_ZERO, '!=', 0xFF000000, 0, 0xFF000000);
      
      generateMorphImage();
    }
    private function generateMorphImage():void
    {
      var myBitmap:Bitmap = new Bitmap(source);
			var sprite1:Sprite = new Sprite();
			addChild(sprite1);
			myBitmap.x = myBitmap.y = 0.5;
			
      sprite1.addChild(myBitmap);
      sprite1.scaleX = sprite1.scaleY = 2;
      sprite1.x = 32;
      sprite1.y = 8;
      
      myBitmap = new Bitmap(destination);
			var sprite2:Sprite = new Sprite();
			addChild(sprite2);
			myBitmap.x = myBitmap.y = 0.5;
			
      sprite2.addChild(myBitmap);
      sprite2.scaleX = sprite2.scaleY = 2;
      sprite2.x = (32 + 96)*2;
      sprite2.y = 8;
      
      /* Main routine */
      
      interFrames = Math.random() * 24 + 24;
      radialMapping.moveTransition = transitions[int(Math.random() * 1000) % transitions.length];
      radialMapping.colorTransition = transitions[int(Math.random() * 1000) % transitions.length];
			
      // create morphing bitmapData source to destination
      morphSprite = new TriangleMorphSprite(source, destination, interFrames, radialMapping);
      
      addChild(morphSprite);
      morphSprite.x = 32;
      morphSprite.y = 150;
			morphSprite.scaleX = morphSprite.scaleY = 4;
      
			var myShape:Shape = new Shape();
			drawTriangleMesh(morphSprite.sourceMass, myShape.graphics);
			sprite1.addChild(myShape);
			
			myShape = new Shape();
			drawTriangleMesh(morphSprite.destinationMass, myShape.graphics);
			sprite2.addChild(myShape);
			
      addEventListener(Event.ENTER_FRAME, enterFrameHandler);
      stage.addEventListener(MouseEvent.CLICK, clickHandler);
    }
    private function enterFrameHandler(e:Event):void
    {
      if (frameCount < 30)
        morphSprite.update();
      else if (frameCount <= 30 + interFrames) {
        morphSprite.nextFrame();
      }
      else if (frameCount < 60 + interFrames)
        morphSprite.update();
      else {
        morphSprite.prevFrame();
      }
			
      if (frameCount >= 60 + interFrames*2)
        frameCount = 0;
       
      frameCount++;
    }
		public function drawTriangleMesh(mass:Mass, g:Graphics):void
		{
			g.lineStyle(1, 0x222222, 0.5);
			g.drawTriangles(mass.vertices, mass.indicies, mass.uvtData);
			g.drawTriangles(mass.vertices2, null, mass.uvtData2);
		}
  }
}

import flash.display.Bitmap;
import flash.display.BitmapData;
import flash.display.Graphics;
import flash.display.Shape;
import flash.display.Sprite;
import flash.geom.Point;

class TriangleMorphSprite extends Sprite
{
	private static const POINT_ZERO:Point = new Point();
	private var _source:BitmapData;
	private var _destination:BitmapData;
	
	private var _sourceMass:Mass;
	private var _destinationMass:Mass;
	private var _sourceShape:Shape = new Shape();
	private var _destinationShape:Shape = new Shape();
	private var _sourceBitmap:Bitmap;
	private var _destinationBitmap:Bitmap;
		
	private var _interFrames:int; // inter frame num. total frames = 1 + inter frames + 1
	public function get interFrames():int { return _interFrames }
	public function get totalFrames():int { return _interFrames + 2 }
		
	private var _rate:Number;
	private var _currentFrame:int;
	public function get currentFrame():int { return _currentFrame }
	public function set currentFrame(value:int):void { _currentFrame = value }
		
	public function get sourceMass():Mass { return _sourceMass; }	
	public function get destinationMass():Mass { return _destinationMass; }
	
	private var _mapping:IMapping = Mappings.RADIAL;
	
	public function TriangleMorphSprite(source:BitmapData, destination:BitmapData,interFrames:int = 1, mapping:IMapping = null)
	{
		_source = expandBitmapData(source);
		_destination = expandBitmapData(destination);
			
		_sourceBitmap = new Bitmap(_source);
		_destinationBitmap = new Bitmap(_destination);
			
		_interFrames = interFrames;
		_rate = 1.0 / (interFrames + 1);
		_currentFrame = 0;
			
		if(mapping != null)
			_mapping = mapping;
			
		_sourceMass = new Mass(_source);
		_destinationMass = new Mass(_destination);
			
		_mapping.map(_sourceMass, _destinationMass);
			
		drawFeaturePoints(source, _sourceMass.contourConvexPoints);
		drawFeaturePoints(destination, _destinationMass.contourConvexPoints);
		drawLargePoint(source, _sourceMass.centerX, _sourceMass.centerY, 0x00FF00);
		drawLargePoint(destination, _destinationMass.centerX, _destinationMass.centerY, 0x00FF00);
		
	}
	public function update():void
	{	
		drawFrame(currentFrame);
	}
	public function nextFrame():void
	{
		_currentFrame++;
		update();
	}
	public function prevFrame():void
	{
		_currentFrame--;
		update();
	}
	public function drawFrame(frame:int):void
	{
		while (numChildren > 0)
			removeChildAt(0);
		
		if (frame == 0) {
			addChild(_sourceBitmap)
		}
		else if (frame == _interFrames + 1) {
			addChild(_destinationBitmap);
		}
		else {
			addChild(_sourceShape);
			addChild(_destinationShape);
			var t:Number = _rate * frame;
			var vertices:Vector.<Number> = margeVertices(t, _sourceMass.vertices, _destinationMass.vertices);
			var vertices2:Vector.<Number> = margeVertices(t,_sourceMass.vertices2, _destinationMass.vertices2);
			drawMass(t, vertices, vertices2, _source, _sourceMass, _sourceShape);
			drawMass(1 - t, vertices, vertices2, _destination, _destinationMass, _destinationShape);
		}
	}
	public function margeVertices(t:Number, fromVer:Vector.<Number>, toVer:Vector.<Number>):Vector.<Number>
	{
		var vertices:Vector.<Number> = new Vector.<Number>();
		var n:int = toVer.length;
		
		for (var i:int = 0; i < n; i += 2 ) {
			var vx:Number = _mapping.moveTransition.calculate(t, fromVer[i], toVer[i])
			var vy:Number = _mapping.moveTransition.calculate(t, fromVer[i + 1], toVer[i+1])
			vertices.push(vx, vy);
		}
		return vertices;
	}
	public function drawMass(t:Number, vertices:Vector.<Number>, vertices2:Vector.<Number>, buffer:BitmapData, mass:Mass, shape:Shape):void
	{
		var g:Graphics = shape.graphics;
		g.clear();
		g.beginBitmapFill(buffer, null, false);
		g.drawTriangles(vertices, mass.indicies, mass.uvtData);
		g.drawTriangles(vertices2, null, mass.uvtData2);
		
		var alpha:Number = _mapping.colorTransition.calculate(t, 1, 0);
		
		if (t != 0 && t != 1.0)
			alpha += 0.125;
		
		if (alpha > 1.0) alpha = 1.0;
		else if (alpha < 0) alpha = 0;
		
		shape.alpha = alpha;
	}
	public function expandBitmapData(buffer:BitmapData, size:int = 1):BitmapData
	{
		var bitmapData:BitmapData = new BitmapData(buffer.width + size * 2, buffer.height + size * 2, buffer.transparent, 0);
		bitmapData.copyPixels(buffer, buffer.rect, new Point(size, size), null, null, true);
		return bitmapData;
	}
	private function drawFeaturePoints(source:BitmapData, featurePoints:Vector.<FeaturePoint>):void
	{
		var n:int = featurePoints.length;
		for (var i:int = 0; i < n; i++ ) {
			var featurePoint:FeaturePoint = featurePoints[i];
			drawLargePoint(source, featurePoint.x - 1, featurePoint.y - 1, 0xFF00FF);
		}
	}
	private function drawLargePoint(source:BitmapData, x:int, y:int, color:uint):void
	{
		for (var iy:int = -1; iy <= 1; iy++ ) {
			for (var ix:int = -1; ix <= 1; ix++ ) {
				if (ix == 0 && iy == 0)
					source.setPixel(x + ix, y + iy, color);
				else
					source.setPixel32(x + ix, y + iy, 0xFF000000);
			}
		}
	}
}

// no use
class ColorSpacePoint
{
  public static const RGB:String = 'rgb';
  public static const HLS:String = 'hls';
  public static const LAB:String = 'lab';
  
  public function ColorSpacePoint(color:uint) 
  {
  }
}

class FeaturePoint 
{
	public var x:Number;
	public var y:Number;
	public var radian:Number;
	public var degree:Number;
	public var length:Number;
	public var index:int;
	public var contourListIndex:int;
	public var contourIndex:int;
	
	public function FeaturePoint(x:Number, y:Number, radian:Number, length:Number, contourListIndex:int, contourIndex:int) 
	{
		this.x = x;
		this.y = y;
		this.radian = radian;
		this.degree = MathUtil.getRadianToDegree(radian);
		this.length = length;
		this.contourListIndex = contourListIndex;
		this.contourIndex = contourIndex;
	}
}

class Mass
{
	private static const PI:Number = Math.PI;
	private static const DEFAULT_EXTRACT_RADIAN:Number = Math.PI / 18;
	
	public var width:int;
	public var height:int;
	public var centerX:Number = 0;
	public var centerY:Number = 0;
	public var vertices:Vector.<Number>;
	public var indicies:Vector.<int>;
	public var uvtData:Vector.<Number>;
	
	public var vertices2:Vector.<Number>;
	public var uvtData2:Vector.<Number>;
	
	public var contourList:Vector.<Vector.<Point>>;
	public var contourConvexPoints:Vector.<FeaturePoint> = new Vector.<FeaturePoint>(); // 凸
	public var contourConcavePoints:Vector.<FeaturePoint> = new Vector.<FeaturePoint>(); // 凹
	
	public var contourExtractRadian:Number;
	
	public function Mass(bitmapData:BitmapData, backgroundColor:uint = 0, contourExtractRadian:Number = DEFAULT_EXTRACT_RADIAN) 
	{
		width = bitmapData.width;
		height = bitmapData.height;
		this.contourExtractRadian = contourExtractRadian;
		
		calcCenter(bitmapData, backgroundColor);
		extractFeaturePoint(bitmapData, backgroundColor);
	}
	private function calcCenter(bitmapData:BitmapData, backgroundColor:uint = 0):void
	{
		var n:int;
		var x:int, y:int;
		
		for (y = 0; y < height; y++ ) {
			for (x = 0; x < width; x++ ) {
				var color:uint = bitmapData.getPixel32(x, y);
				if (color != backgroundColor) {
					centerX += x;
					centerY += y;
					n++;
				}
			}
		}
		
		if (n != 0) {
			centerX /= n;
			centerY /= n;
		}
	}
	private function extractFeaturePoint(bitmapData:BitmapData, backgroundColor:uint = 0):void
	{
     var contourTracer:ContourTracer = new ContourTracer();
		contourList = contourTracer.findContourListForRun(bitmapData, backgroundColor, 0xFF000000, ContourTracer.TRACE_OUTSIDE);
		
		var n:int = contourList.length;
		for (var i:int = 0; i < n; i++ ) {
			var contour:Vector.<Point> = contourList[i];
			var m:int = contour.length;
				
			var prevLength:Number = MathUtil.getPointToPointLength(centerX, centerY, contour[m - 1].x + 0.5, contour[m - 1].y + 0.5);
			var currentLength:Number  = MathUtil.getPointToPointLength(centerX, centerY, contour[0].x + 0.5, contour[0].y + 0.5);
			var currentGrad:Boolean = prevLength < currentLength;
			var maxLength:Number = currentLength;
			var maxPoint:Point = contour[0];
			var maxIndex:int = 0;
				
			var prevGrad:Boolean = currentGrad;
			var prevPoint:Point = contour[0];
			var prevFeature:FeaturePoint = null;
			prevLength = currentLength;
			
			for (var j:int = 1; j < m; j++) {
				var point:Point = contour[j];
				currentLength  = MathUtil.getPointToPointLength(centerX, centerY, point.x + 0.5, point.y + 0.5);
				
				currentGrad = prevLength < currentLength;
				if (prevGrad != currentGrad) {
					var radian:Number = MathUtil.getPointToPointRadian(centerX, centerY, point.x + 0.5, point.y + 0.5);
					var featurePoint:FeaturePoint = new FeaturePoint(prevPoint.x, prevPoint.y, radian, currentLength, i, j);
					
					if (currentGrad)
						contourConcavePoints.push(featurePoint);
					else
						contourConvexPoints.push(featurePoint);
						
					prevFeature = featurePoint;
				}
				else if (prevFeature != null) {
					radian = MathUtil.getPointToPointRadian(centerX, centerY, point.x + 0.5, point.y + 0.5);
					var diffRadian:Number = MathUtil.getRadianDiff(prevFeature.radian, radian);
					if (diffRadian > contourExtractRadian) {
						featurePoint = new FeaturePoint(prevPoint.x, prevPoint.y, radian, currentLength, i, j);
						contourConvexPoints.push(featurePoint);
						prevFeature = featurePoint;
					}
				}
				
				if (maxLength < currentLength) {
					maxLength = currentLength;
					maxPoint = point;
					maxIndex = j;
				}
				
				prevGrad = currentGrad;
				prevLength = currentLength;
				prevPoint = point;
			}
			
			var maxAdded:Boolean = false;
			var l:int = contourConvexPoints.length;
			for (var k:int = 0; k < l; k++ ) {
				featurePoint = contourConvexPoints[k];
				if (featurePoint.x == maxPoint.x && featurePoint.y == maxPoint.y) {
					maxAdded = true;
					break;
				}
			}
			if (!maxAdded) {
				radian = MathUtil.getPointToPointRadian(centerX, centerY, maxPoint.x + 0.5, maxPoint.y + 0.5);
				featurePoint = new FeaturePoint(maxPoint.x, maxPoint.y, radian, maxLength, i, maxIndex);
				contourConvexPoints.push(featurePoint);
			}
		}
	}
}

interface ITransition 
{
  function calculate(t:Number, from:Number, to:Number):Number;
}
class Linear implements ITransition
{
  public function calculate(t:Number, from:Number, to:Number):Number
  {
    return (to-from) * t + from;
  }  
}
class Pow implements ITransition
{
  public var dimension:Number;
  
  public function Pow(dimension:Number = 2.0) 
  {
    this.dimension = dimension;
  }
  public function calculate(t:Number, from:Number, to:Number):Number
  {
    return (to-from) * Math.pow(t, dimension) + from;
  }  
}
class Sine implements ITransition
{
  public var frequency:int;
  
  public function Sine(frequency:int = 0)
  {
    this.frequency = frequency;
  }
  public function calculate(t:Number, from:Number, to:Number):Number
  {
    return (to-from) * Math.sin(t * (1/2 + 2 * frequency) * Math.PI) + from;
  }  
}
class Transitions 
{
  public static const LINEAR:Linear = new Linear();
  public static const POW2:Pow = new Pow(2);
  public static const SINE:Sine = new Sine();
}

interface IMapping 
{
  function get moveTransition():ITransition;
  function set moveTransition(value:ITransition):void;
  function get colorTransition():ITransition;
  function set colorTransition(value:ITransition):void;
  function get colorSpace():String;
  function set colorSpace(value:String):void;
  function map(m1:Mass, m2:Mass):void;
}
class MappingBase implements IMapping
  {
  public function get moveTransition():ITransition { return _moveTransition; }
  public function set moveTransition(value:ITransition):void { _moveTransition = value;}
  public function get colorTransition():ITransition { return _colorTransition; }
  public function set colorTransition(value:ITransition):void { _colorTransition = value; }
  public function get colorSpace():String { return _colorSpace; }
  public function set colorSpace(value:String):void { _colorSpace = value; }
    
  protected var _moveTransition:ITransition;
  protected var _colorTransition:ITransition;
  protected var _colorSpace:String;
    
  public function MappingBase(moveTransition:ITransition = null, colorTransition:ITransition = null, colorSpace:String = null)
  {
    _moveTransition = moveTransition;
    _colorTransition = colorTransition;
    _colorSpace = colorSpace;
  }
  public function map(m1:Mass, m2:Mass):void
  {
  }
}

class Radial extends MappingBase
{
	private static const PI:Number = Math.PI;
	private static const M_PI:Number = Math.PI * (-1);
	private static const DEFAULT_SEARCH_RANGE:Number = PI / 12;
	private static const DEFAULT_SEARCH_MAX:Number = PI / 4;
	public var partDeg:int;
	public var searchRadianRangeUnit:Number;
	public var searchRangeMax:Number;
	public var extraChainDeg:int;
	public var triangleMargin:Number;
		
	public function Radial(moveTransition:ITransition = null, colorTransition:ITransition = null, colorSpace:String = null, partDeg:int = 10, searchRadianRangeUnit:Number = DEFAULT_SEARCH_RANGE, searchRangeMax:Number = DEFAULT_SEARCH_MAX, extraChainDeg:int = 30, triangleMargin:Number = 5) 
	{
		super(moveTransition, colorTransition, colorSpace);
		
		this.partDeg = partDeg;
		this.searchRadianRangeUnit = searchRadianRangeUnit;
		this.searchRangeMax = searchRangeMax;
		this.extraChainDeg = extraChainDeg;
		this.triangleMargin = triangleMargin;
	}
	override public function map(m1:Mass, m2:Mass):void
	{
		m1.contourConvexPoints = pruneFeaturePoint(m1);
		m2.contourConvexPoints = pruneFeaturePoint(m2);
			
		setFeaturePointIndex(m1.contourConvexPoints);
		setFeaturePointIndex(m2.contourConvexPoints);
			
		m1.vertices = new Vector.<Number>();
		m2.vertices = new Vector.<Number>();
		m1.indicies = new Vector.<int>();
		m2.indicies = new Vector.<int>();
		m1.uvtData = new Vector.<Number>();
		m2.uvtData = new Vector.<Number>();
			
		m1.vertices2 = new Vector.<Number>();
		m2.vertices2 = new Vector.<Number>();
		m1.uvtData2 = new Vector.<Number>();
		m2.uvtData2 = new Vector.<Number>();
			
		var firstPoint1:FeaturePoint = m1.contourConvexPoints[0];
		var firstPoint2:FeaturePoint = getNearestFeaturePoint(firstPoint1, m2.contourConvexPoints, 0, m2.contourConvexPoints.length);
		if (firstPoint2 == null)
			firstPoint2 = m2.contourConcavePoints[0]
		var matchedTrianglePoints:Vector.<FeaturePoint> = addRadialMatchVertices(m1, m2, firstPoint1, firstPoint2);
			
		addRadialIndicies(m1);
		addRadialIndicies(m2);
			
		addRadialUvtData(m1, m1.vertices, m1.uvtData);
		addRadialUvtData(m2, m2.vertices, m2.uvtData);
			
		addConcaveMatchVertices(m1, m2, matchedTrianglePoints);
		addRadialUvtData(m1, m1.vertices2, m1.uvtData2);
		addRadialUvtData(m2, m2.vertices2, m2.uvtData2);
		
	}
	private function setFeaturePointIndex(v:Vector.<FeaturePoint>):void
	{
		var n:int = v.length;
		for (var i:int = 0; i < n; i++ ) {
			var p:FeaturePoint = v[i];
			p.index = i;
		}
	}
	private function addRadialMatchVertices(m1:Mass, m2:Mass, firstPoint1:FeaturePoint, firstPoint2:FeaturePoint):Vector.<FeaturePoint>
	{
		
		m1.vertices.push(m1.centerX, m1.centerY);
		m2.vertices.push(m2.centerX, m2.centerY);
			
		var c1:Vector.<Vector.<FeaturePoint>> = createFeatureContourList(m1);
		var c2:Vector.<Vector.<FeaturePoint>> = createFeatureContourList(m2);
		var matchedTrianglePoints:Vector.<FeaturePoint> = new Vector.<FeaturePoint>();
		matchedTrianglePoints.push(firstPoint1, firstPoint2);
			
		var firstIndex1:int = firstPoint1.index;
		var firstIndex2:int = firstPoint2.index;
			
		var n1:int = m1.contourConvexPoints.length;
		var n2:int = m2.contourConvexPoints.length;
		var saerchedInfoTable1:Array = [];
		var saerchedInfoTable2:Array = [];
		
		var j:int = 0;
		var searchedNum:int = 1;
		var firstRad1:Number = firstPoint1.radian;
		var firstRad2:Number = firstPoint2.radian;
		var searchedRad1:Number = 0;
		var searchedRad2:Number = 0;
		var prevPoint2:FeaturePoint;
			
		var serchNum1:int = n1 - 1;
		for (var i:int = 0; i < serchNum1; i++ ) {
			var currentPoint1:FeaturePoint = m1.contourConvexPoints[(firstIndex1 + 1 + i) % n1];
				
			var currentPoint2:FeaturePoint = null;
			var searchRange:Number = searchRadianRangeUnit;
			var isSearchedFeature:Boolean = true;
			do {
				currentPoint2 = getNearestFeaturePoint(currentPoint1, m2.contourConvexPoints, firstIndex2 + searchedNum, n2 - searchedNum, currentPoint1.radian - searchRange, currentPoint1.radian + searchRange);
				searchRange += searchRadianRangeUnit;
				
				if (currentPoint2 == null) {
					var searchStart:Number = currentPoint1.radian;
					currentPoint2 = getNearestContourFeaturePoint(currentPoint1, c2, saerchedInfoTable2, searchStart, searchStart + searchRange)
					searchRange += searchRadianRangeUnit;
					if (currentPoint2 != null)
						isSearchedFeature = false;
				}
			} while (currentPoint2 == null && searchRange < searchRangeMax)
				
			if (currentPoint2 != null) {
				var cp1:FeaturePoint = currentPoint1;
				var cp2:FeaturePoint = currentPoint2;
					
				if(isSearchedFeature){
					var prevSearchedNum:int = searchedNum;
					searchedNum = (currentPoint2.index + 1 - firstIndex2 + n2) % n2;
				}
				
				var searchedDiff:int = searchedNum - prevSearchedNum;
				if (isSearchedFeature && searchedDiff >= 2) {
					currentPoint2 = m2.contourConvexPoints[(currentPoint2.index - 1 + n2) % n2];
					searchRange = searchRadianRangeUnit;
					do {
						searchStart = currentPoint2.radian;
						currentPoint1 = getNearestContourFeaturePoint(currentPoint2, c1, saerchedInfoTable1, searchStart, searchStart + searchRange)
						searchRange += searchRadianRangeUnit;
					} while (currentPoint1 == null && searchRange < searchRangeMax)
					
					if(currentPoint1 != null){
						matchedTrianglePoints.push(currentPoint1, currentPoint2);
						searchedRad1 = MathUtil.adjustRadian(currentPoint1.radian + 1 / 36000 - firstRad1);
						searchedRad2 = MathUtil.adjustRadian(currentPoint2.radian + 1 / 36000 - firstRad2);
					}
				}
				
				matchedTrianglePoints.push(cp1, cp2);
				searchedRad1 = MathUtil.adjustRadian(cp1.radian + 1 / 36000 - firstRad1);
				searchedRad2 = MathUtil.adjustRadian(cp2.radian + 1 / 36000 - firstRad2);
			}
			else {
				cp1 = currentPoint1;
				if(cp2 != null)
					cp2 = m2.contourConvexPoints[(cp2.index + 1 + n2) % n2];
				if(cp2 != null && MathUtil.getDegreeDiff(cp1.degree, cp2.degree) < extraChainDeg){
					matchedTrianglePoints.push(cp1, cp2);
					searchedRad1 = MathUtil.adjustRadian(cp1.radian + 1 / 36000 - firstRad1);
					searchedRad2 = MathUtil.adjustRadian(cp2.radian + 1 / 36000 - firstRad2);
				}
			}
		}
		
		addTriangleVertices(matchedTrianglePoints, m1.vertices, m2.vertices);
		
		return matchedTrianglePoints;
	}
	private function addTriangleVertices(t:Vector.<FeaturePoint>, v1:Vector.<Number>, v2:Vector.<Number>):void
	{
		var n:int = t.length;
		for (var i:int = 0; i < n; i += 2 ) {
			addFeatureVertices(v1, t[i]);
			addFeatureVertices(v2, t[i + 1]);
		}
		addFeatureVertices(v1, t[0]);
		addFeatureVertices(v2, t[1]);
	}
	private function addFeatureVertices(v:Vector.<Number>, p:FeaturePoint):void
	{
		var mx:Number = Math.cos(p.radian) * triangleMargin;
		var my:Number = Math.sin(p.radian) * triangleMargin;
		v.push(p.x + mx, p.y + my);
	}
	private function createFeatureContourList(mass:Mass):Vector.<Vector.<FeaturePoint>>
	{
		var featureContourList:Vector.<Vector.<FeaturePoint>> = new Vector.<Vector.<FeaturePoint>>();
		var n:int = mass.contourList.length;
		for (var i:int = 0; i < n; i++) {
			var contour:Vector.<Point> = mass.contourList[i];
			var featureContour:Vector.<FeaturePoint> = new Vector.<FeaturePoint>();
			var m:int = contour.length;
			for (var j:int = 0; j < m; j++ ) {
				var p:Point = contour[j];
				var length:Number = MathUtil.getPointToPointLength(mass.centerX, mass.centerY, p.x + 0.5, p.y + 0.5);
				var radian:Number = MathUtil.getPointToPointRadian(mass.centerX, mass.centerY, p.x + 0.5, p.y + 0.5);
				var featurePoint:FeaturePoint = new FeaturePoint(p.x, p.y, radian, length, i, j);
				featureContour.push(featurePoint);
			}
			featureContourList.push(featureContour);
		}
		return featureContourList;
	}
	private function addRadialIndicies(m:Mass):void
	{
		var n:int = m.vertices.length;
		
		for (var i:int = 1; i < n; i++) {
			m.indicies.push(0, i, i + 1);
		}
	}
	private function addConcaveMatchVertices(m1:Mass, m2:Mass, matchedTrianglePoints:Vector.<FeaturePoint>):void
	{
		var n:int = m1.vertices.length;
		var tn:int = matchedTrianglePoints.length;
		var prevConvex1:FeaturePoint = matchedTrianglePoints[0];
		var prevConvex2:FeaturePoint = matchedTrianglePoints[0+1];
			
		var currentPoint:FeaturePoint;
		var nextPoint:FeaturePoint;
		var nextNextPoint:FeaturePoint;
		
		for (var i:int = 2; i < n; i++) {
			currentPoint = matchedTrianglePoints[((i - 1) * 2) % tn];
			nextPoint = matchedTrianglePoints[(i * 2) % tn];
			nextNextPoint = matchedTrianglePoints[((i + 1) * 2) % tn];
			prevConvex1 = addConcaveVertices(m1.vertices2, prevConvex1, currentPoint, nextPoint, nextNextPoint);
			
			currentPoint = matchedTrianglePoints[((i - 1) * 2 + 1) % tn];
			nextPoint = matchedTrianglePoints[(i * 2 + 1) % tn];
			nextNextPoint = matchedTrianglePoints[((i + 1) * 2 + 1) % tn];
			prevConvex2 = addConcaveVertices(m2.vertices2, prevConvex2, currentPoint, nextPoint, nextNextPoint);
		}
	}
	private function addConcaveVertices(ver:Vector.<Number>, prevConvex:FeaturePoint, currentPoint:FeaturePoint, nextPoint:FeaturePoint, nextNextPoint:FeaturePoint):FeaturePoint
	{
		if (currentPoint.length < prevConvex.length) {
			if (currentPoint.length < nextPoint.length) {
				addFeatureVertices(ver,prevConvex);
				addFeatureVertices(ver,currentPoint);
				addFeatureVertices(ver, nextPoint);
				return nextPoint;
			}
			else {
				addFeatureVertices(ver,nextPoint);
				addFeatureVertices(ver,nextPoint);
				addFeatureVertices(ver,nextPoint);
				return currentPoint;
			}
		}
		else {
			addFeatureVertices(ver,prevConvex);
			addFeatureVertices(ver,prevConvex);
			addFeatureVertices(ver,prevConvex);
			return currentPoint;
		}
	}
	private function addRadialUvtData(m:Mass, ver:Vector.<Number>, uvt:Vector.<Number>):void
	{
		var n:int = ver.length;
		for (var i:int = 0; i < n; i+=2)
		{
			var u:Number = ver[i] / m.width;
			var v:Number = ver[i + 1] / m.height;
			uvt.push(u, v);
		}
	}
	
	private function pruneFeaturePoint(mass:Mass):Vector.<FeaturePoint>
	{
		var pruned:Vector.<FeaturePoint> = new Vector.<FeaturePoint>();
		mass.contourConvexPoints.sort(compareDeg);
		
		var partDeg2:Number = partDeg / 2;
		var partGroup:Vector.<FeaturePoint> = new Vector.<FeaturePoint>();
		var startIndex:int = getMaxLengthFeaturePointIndex(mass.contourConvexPoints);
		var centerDeg:Number = mass.contourConvexPoints[startIndex].degree;
		
		for (var i:int = 1; i < n; i++ ) {
			var featurePoint:FeaturePoint = mass.contourConvexPoints[(startIndex - i) % n];
			var diffDeg:int = MathUtil.getDegreeDiff(featurePoint.degree, centerDeg);
			
			if (diffDeg > partDeg2)
				break;
			startIndex--;
		}
			
		partGroup.push(mass.contourConvexPoints[startIndex]);
		
		var n:int = mass.contourConvexPoints.length;
		for (i = 0; i < n; i++ ) {
			featurePoint = mass.contourConvexPoints[(startIndex+i) % n];
			
			diffDeg =  MathUtil.getDegreeDiff(featurePoint.degree, centerDeg + partDeg2 - partDeg);
			if (diffDeg > partDeg) {
				if (partGroup.length > 0) {
					var maxLengthIndex:int = getMaxLengthFeaturePointIndex(partGroup);
					var maxLengthFeaturePoint:FeaturePoint = partGroup[maxLengthIndex];
					centerDeg = maxLengthFeaturePoint.degree;
					pruned.push(maxLengthFeaturePoint);
					partGroup.splice(0, partGroup.length);
				}
			}
			
			partGroup.push(featurePoint);
		}
		
		if (partGroup.length > 0) {
			maxLengthIndex = getMaxLengthFeaturePointIndex(partGroup);
			maxLengthFeaturePoint = partGroup[maxLengthIndex];
			centerDeg = maxLengthFeaturePoint.degree;
			pruned.push(maxLengthFeaturePoint);
			partGroup.splice(0, partGroup.length);
		}
		
		n = pruned.length;
		var prevFeaturePoint:FeaturePoint = pruned[0];
		
		for (i = 1; i < n; i++ ) {
			featurePoint = pruned[i];
			diffDeg =  MathUtil.getDegreeDiff(featurePoint.degree, prevFeaturePoint.degree);
			
			if (diffDeg < partDeg) {
				if (featurePoint.length < prevFeaturePoint.length) {
					pruned.splice(i, 1);
				}
				else {
					pruned.splice(i - 1, 1);
					prevFeaturePoint = featurePoint;
					i--;
				}
				n = pruned.length;
			}
			else
				prevFeaturePoint = featurePoint;
		}
		
		return pruned;
	}
	private function getMaxLengthFeaturePointIndex(v:Vector.<FeaturePoint>):int
	{
		var maxLength:Number = v[0].length;
		var maxFeaturePoint:FeaturePoint = v[0];
		var maxFeaturePointIndex:int = 0;
		
		var n:int = v.length;
		for (var i:int = 1; i < n; i++ ) {
			var featurePoint:FeaturePoint = v[i];
			if (maxLength < featurePoint.length) {
				maxLength = featurePoint.length;
				maxFeaturePoint = featurePoint;
				maxFeaturePointIndex = i;
			}
		}
		
		return maxFeaturePointIndex;
	}
	private function compareDeg(p1:FeaturePoint, p2:FeaturePoint):Number
	{
		if (p1.degree < p2.degree)
			return -1;
		else if (p1.degree > p2.degree)
			return 1;
		else if (p1.length < p2.length)
			return -1;
		else if (p1.length > p2.length)
			return 1;
		else
			return 0;
	}
	public function getNearestContourFeaturePoint(centerPoint:FeaturePoint, contourList:Vector.<Vector.<FeaturePoint>>, searchedInfoTable:Array, startRad:Number = M_PI, endRad:Number = PI):FeaturePoint
	{
		var minLength:Number = Number.MAX_VALUE;
		var minPoint:FeaturePoint = null;
		var n:int = contourList.length;
		for (var i:int = 0; i < n; i++ ) {
			var contour:Vector.<FeaturePoint> = contourList[i];
			var m:int = contour.length;
			var searchedInfo:Array = searchedInfoTable[i];
			var point:FeaturePoint;
			if (searchedInfo == null) {
				point = getNearestFeaturePoint(centerPoint, contour, 0, m, startRad, endRad);
				
				if(point != null){
					searchedInfo = [point.contourIndex, 1];
					searchedInfoTable[i] = searchedInfo;
				}
			}
			else {
				var startIndex:int = searchedInfo[0];
				var searchedNum:int = searchedInfo[1];
				point = getNearestFeaturePoint(centerPoint, contour, startIndex, m - searchedNum, startRad, endRad);
				
				if(point != null){
					var prevSearchedNum:int = searchedInfo[1];
					searchedInfo[1] = (point.contourIndex + m + 1 - startIndex) % m;
				}
			}
			
			
			if (point != null && point.length < minLength) {
				minPoint = point;
			}
		}
		return minPoint;
	}
	public function getNearestFeaturePoint(centerPoint:FeaturePoint, pointList:Vector.<FeaturePoint>, startIndex:int, num:int, startRad:Number = M_PI, endRad:Number = PI):FeaturePoint
	{
		var minLength:Number = Number.MAX_VALUE;
		var minPoint:FeaturePoint = null;
		
		var n:int = pointList.length;
		for (var i:int = 0; i < num; i++ ) {
			var point:FeaturePoint = pointList[(startIndex+i) % n];
			var length:Number = MathUtil.getPointToPointLength(centerPoint.x, centerPoint.y, point.x, point.y);
			if (length < minLength) {
				var rad:Number = point.radian;
				
				if (MathUtil.isRadianWithinRange(rad, startRad, endRad)) {
					minLength = length;
					minPoint = point;
				}
			}
		}
		
		return minPoint;
	}
}	

class Mappings 
{
  public static const RADIAL:Radial = new Radial();
}

class MathUtil 
{
	private static const PI:Number = Math.PI;
	
	public static function tanh(x:Number):Number
	{
		var exp:Number = Math.exp(x);
		var exp_inv:Number = 1 / exp;
		var th:Number = (exp - exp_inv) / (exp + exp_inv);
		if(!isNaN(th)){
			return (exp - exp_inv) / (exp + exp_inv);
		}
		return x < 0 ? -1 : 1;
	}
	public static function isRadianWithinRange(rad:Number, startRad:Number, endRad:Number):Boolean
	{
		rad = adjustRadian(rad);
		startRad = adjustRadian(startRad);
		endRad = adjustRadian(endRad);
		
		if (startRad < endRad)
			return (startRad < rad) && (rad < endRad)
		else
			if(startRad > 0 && endRad < 0)
				return (endRad + PI *2 < rad) && (rad < startRad)
			else {
				return (endRad < rad) && (rad < startRad + PI * 2)
			}
	}
	public static function getPointToPointLength(fromX:Number, fromY:Number, toX:Number, toY:Number):Number
	{
		return Math.pow(toX - fromX, 2) + Math.pow(toY - fromY, 2);
	}
	public static function getPointToPointRadian(fromX:Number, fromY:Number, toX:Number, toY:Number):Number
	{
		return Math.atan2(toY - fromY, toX - fromX);
	}
	public static function getDegreeDiff(degree1:int, degree2:int):int
	{
		var diffDeg:int = (degree1 - degree2 + 360) % 360;
		if (diffDeg > 180) diffDeg = 360 - diffDeg;
		return diffDeg;
	}
	public static function getRadianDiff(rad1:Number, rad2:Number):Number
	{
		var diffRad:Number = adjustRadian(rad1 - rad2);
		return diffRad;
	}
	public static function getPointToPointDegree(fromX:Number, fromY:Number, toX:Number, toY:Number):int
	{
		return getRadianToDegree(getPointToPointRadian(fromX, fromY, toX, toY));
	}
	public static function getRadianToDegree(radian:Number):int
	{
		return (Math.floor(((radian * 180 / PI) + 90)) + 360) % 360;
	}
	public static function adjustRadian(radian:Number):Number
	{
		return radian - 2.0 * PI * Math.floor( 0.5 + radian / ( 2.0 * PI) )
	}
}

class ContourTracer
{
  public static const TRACE_ALL:int = 0;
  public static const TRACE_OUTSIDE:int = 1;
  public static const TRACE_INSIDE:int = 2;
  
  private static const AUTOMATON_STATE_TABLE:Array = [
    [2, 4, 3],
    [1, 5, 4],
    [4, 6, 1],
    [5, 1, 6],
    [4, 6, 1],
    [1, 5, 4],
  ];
  
  private static const AUTOMATON_CODE_SET_TABLE:Array = [
    [0, 2, 0],
    [5, 4, 4],
    [3, 3, 1],
    [0, 6, 0],
    [10, 10, 8],
    [7, 9, 9],
  ];
  
  /*
   * Find contour points for Run-type Direction Coding algorithm.
   * 
   * Bibliography:
   *   T. Miyatake, H. Matsushima, M. Ejiri, "A Fast Algorithm for Contour Tracing of Binary Images Based on Run-Type Direction Coding Technique",
   *   The transactions of the Institute of Electronics, Information and Communication Engineers, J79-D-2(3), pp.341-350, 1996.
   * 
   * @param source Source image
   * @param backgroundColor Background color of source image. This function processes binary color of source image as a background color and other colors.
   * @param maskColor Mask of background color. (e.g. Alpha mask is maskColor = 0xFF000000. Red mask is maskColor = 0xFF0000)
   * @param mode Mode of Tracer. ContourTracer.TRACE_ALL or ContourTracer.TRACE_OUTSIDE or ContourTracer.TRACE_INSIDE.
   * 
   * @return Vector of contour. One contour is composed one object's edge points.
   */
  public function findContourListForRun(source:BitmapData, backgroundColor:uint = 0x00000000, maskColor:uint = 0xFFFFFFFF, mode:int = TRACE_ALL):Vector.<Vector.<Point>>
  {
    var rdDataList:Vector.<RunTypeDirectionData> = new Vector.<RunTypeDirectionData>();
    
    var prevLineBuffer:Vector.<int>;
    var currentLineBuffer:Vector.<int> = new Vector.<int>();
    
    var width:int = source.width;
    var height:int = source.height;
    var endOfLine:int = width + 1;
    
    currentLineBuffer.push(endOfLine);
    
    var entryIndex:int = 0;
    var topWaitIndex:int = 0;
    var lastWaitIndex:int = 0;
    
    var automatonState:int = 1; // Automaton state for RD code extraction
    
    var x:int, y:int;
    
    for (y = 0; y <= height; y++) {
      prevLineBuffer = currentLineBuffer;
      currentLineBuffer = new Vector.<int>();
      
      if(y < height){
        // read run(left and right edge) of image line
        // if x = -1 or x = width, set source.getPixel32(x, y) = backgroundColor
        var isBackgroundRun:Boolean = true;
        for (x = 0; x <= width; x++ ) {
          var color:uint = x < width ? source.getPixel32(x, y) : backgroundColor;
          var binaryColor:Boolean = (color & maskColor) == (backgroundColor & maskColor);
          if (isBackgroundRun != binaryColor) {
            currentLineBuffer.push(x);
            isBackgroundRun = binaryColor;
          }
        }
      }
      currentLineBuffer.push(endOfLine);
      
      var prevIndex:int = 0;
      var currentIndex:int = 0;
      var prevPrevRun:int = 0;
      var prevRun:int = prevLineBuffer[prevIndex];
      var prevCurrentRun:int = 0;
      var currentRun:int = currentLineBuffer[currentIndex];
      
      while (prevRun != endOfLine || currentRun != endOfLine) {
        
        // extract RD code
        var cmpState:int = cmpInt(prevRun, currentRun) + 1; // (prev <=> current) + 1
        var rdCode:int = AUTOMATON_CODE_SET_TABLE[automatonState-1][cmpState];
        automatonState = AUTOMATON_STATE_TABLE[automatonState-1][cmpState];
        
        // link RD data
        if (rdCode != 0) {
          var rdData:RunTypeDirectionData = new RunTypeDirectionData(rdCode, prevPrevRun, prevRun, prevCurrentRun, currentRun, y);
          rdDataList.push(rdData);
          
          var myRDData:RunTypeDirectionData;
          if (rdCode == 1 || rdCode == 9) {
            myRDData = rdDataList[lastWaitIndex];
            myRDData.wLink = entryIndex;
            lastWaitIndex = entryIndex;
            
            var k:int;
            k = topWaitIndex;
            myRDData = rdDataList[k];
            var isLoop:Boolean = false;
            while (myRDData.link != -1) {
              k = myRDData.link;
              myRDData = rdDataList[k];
              if (k == topWaitIndex) {
                isLoop = true;
                break;
              }
            }
            if (isLoop)
              topWaitIndex = entryIndex;
          }
          else if (rdCode == 2 || rdCode == 3 || rdCode == 4) {
            // wait head
            myRDData = rdDataList[lastWaitIndex];
            myRDData.wLink = entryIndex;
            lastWaitIndex = entryIndex;
            // link tail
            myRDData = rdDataList[topWaitIndex];
            myRDData.link = entryIndex;
            rdData.isLinked = true;
            if(myRDData.isLinked && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
          }
          else if (rdCode == 5) {
            // link tail
            myRDData = rdDataList[topWaitIndex];
            myRDData.link = entryIndex;
            rdData.isLinked = true;
            if (myRDData.isLinked && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
            // link head
            myRDData = rdDataList[topWaitIndex];
            rdData.link = topWaitIndex;
            myRDData.isLinked = true;
            if (myRDData.link != -1 && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
          }
          else if (rdCode == 6 || rdCode == 7 || rdCode == 8) {
            // link head
            myRDData = rdDataList[topWaitIndex];
            rdData.link = topWaitIndex;
            myRDData.isLinked = true;
            if(myRDData.link != -1 && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
            // wait tail
            myRDData = rdDataList[lastWaitIndex];
            myRDData.wLink = entryIndex;
            lastWaitIndex = entryIndex;
          }
          else { // rdCode == 10
            // link head
            myRDData = rdDataList[topWaitIndex];
            rdData.link = topWaitIndex;
            myRDData.isLinked = true;
            if(myRDData.link != -1 && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
            // link tail
            myRDData = rdDataList[topWaitIndex];
            myRDData.link = entryIndex;
            rdData.isLinked = true;
            if (myRDData.isLinked && myRDData.wLink != -1)
              topWaitIndex = myRDData.wLink;
          }
          
          entryIndex++;
        }
        
        // update next run data
        prevPrevRun = prevRun;
        prevCurrentRun = currentRun;
        
        if (cmpState == 0) {
          prevIndex++;
          prevRun = prevLineBuffer[prevIndex];
        }
        else if (cmpState == 1) {
          prevIndex++;
          prevRun = prevLineBuffer[prevIndex];
          currentIndex++;
          currentRun = currentLineBuffer[currentIndex];
        }
        else {
          currentIndex++;
          currentRun = currentLineBuffer[currentIndex];
        }
      }
    }
    
    // RD Data List to Coutour Points
    var contourList:Vector.<Vector.<Point>> = new Vector.<Vector.<Point>>();
    var searchedNum:int = 0;
    var nextFirstIndex:int = 0;
    var n:int = rdDataList.length;
    
    while (searchedNum < n) {
      var contour:Vector.<Point> = new Vector.<Point>();
      
      entryIndex = -1;
      for (var i:int = nextFirstIndex; i < n; i++ ) {
        myRDData = rdDataList[i];
        if (!myRDData.isChecked) {
          if ((mode == TRACE_ALL)
          || (mode == TRACE_OUTSIDE && myRDData.code == 1)
          || (mode == TRACE_INSIDE && myRDData.code == 9)) {
            entryIndex = i;
            nextFirstIndex = i + 1;
            break;
          }
          else {
            // ignore contour
            while (!myRDData.isChecked) {
              myRDData.isChecked = true;
              searchedNum++;
              if (myRDData.link < 0)
                break;
              myRDData = rdDataList[myRDData.link];
            }
          }
        }
      }
      if (entryIndex == -1)
        break;
      
      myRDData = rdDataList[entryIndex];
      
      /* 
       no use flag. First RD code is 1 or 9. 
       var isOutside:Boolean = myRDData.code == 1;
       var isInside:Boolean = myRDData.code == 9;
       */
       
      var myPoint:Point = new Point(myRDData.x, myRDData.y);
      var prevX:int = myPoint.x;
      var prevY:int = myPoint.y;
      var posX:int, posY:int, sucY:int;
      
      // First contour point pushed last of contour list. RD link is ring.
      if (!(myRDData.link == entryIndex || myRDData.link < 0)) {
        entryIndex = myRDData.link;
        myRDData = rdDataList[myRDData.link];
      }
      
      do {
        myRDData.isChecked = true;
        searchedNum++;
        
        if (myRDData.code == 2) {
          myPoint = new Point(prevX, prevY + 1);
          contour.push(myPoint);
        }
        else if (myRDData.code == 6) {
          myPoint = new Point(prevX, prevY - 1);
          contour.push(myPoint);
        }
        else {
          if (myRDData.code == 4 || myRDData.code == 9) {
            posX = 0; posY = -1; sucY = 1;
          }
          else if (myRDData.code == 5 || myRDData.code == 7) {
            posX = 0; posY = -1; sucY = 0;
          }
          else if (myRDData.code == 8 || myRDData.code == 10) {
            posX = -1; posY = 0; sucY = -1;
          }
          else { // myRDData.code == 1 or 3
            posX = 0; posY = 0; sucY = 0;
          }
          
          while (prevX != myRDData.x + posX) {
            prevX = prevX < myRDData.x + posX ? prevX + 1 : prevX - 1;
            myPoint = new Point(prevX, myRDData.y + posY);
            contour.push(myPoint);
          }
          myPoint.y += sucY;
        }
          
        prevX = myPoint.x;
        prevY = myPoint.y;
        
        if (myRDData.link == entryIndex || myRDData.link < 0)
          break;
        
        entryIndex = myRDData.link;
        
        myRDData = rdDataList[entryIndex];
      } while (!myRDData.isChecked)
      
      // Replace first Point
      contour.reverse();
      
      if(contour.length != 0)
        contourList.push(contour);
    }
    
    return contourList;
    
    // val1 <=> val2 
    function cmpInt(val1:int, val2:int):int {
      if (val1 < val2) {
        return -1;
      }
      else if (val1 == val2) {
        return 0;
      }
      else {
        return 1;
      }
    }
  }
}

/*
 * Run-type Direction data
 * @author heriet
 */
 

class RunTypeDirectionData 
{
  public var x:int = 0;
  public var y:int = 0;
  public var code:int = 0;
  public var link:int = -1;
  public var wLink:int = -1;
  public var isLinked:Boolean = false;
  public var isChecked:Boolean = false;
  
  public function RunTypeDirectionData(code:int, prevPrev:int, prev:int, prevCurrent:int, current:int, y:int) 
  {
    this.code = code;
    this.y = y;
    
    if (code == 1 || code == 3) {
      this.x = prevCurrent;
    }
    else if (code == 4 || code == 9) {
      this.x = current;
    }
    else if (code == 5 || code == 7) {
      this.x = prev - 1;
    }
    else if (code == 8 || code == 10) {
      this.x = prevPrev;
    }
    else { // code == 2, or 6
      this.x = -1;
      this.y = -1;
    }
  }
}