forked from: Triangle Mesh Morphing (Radial Triangulation)

/**
 * Copyright jmbyh521 ( http://wonderfl.net/user/jmbyh521 )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/qdcD
 */

// forked from heriet's Triangle Mesh Morphing (Radial Triangulation)
//
// 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;
    }
  }
}