package  
{
	/**
	 * @author nicoptere
	 * blog: http://www.nicoptere.net/blog/
	 * svn: http://nicoptere.googlecode.com/svn/trunk/
	 * 
	 * based on :
	 * http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/azar/skeleton.html#algorithm
	 * 
	 */
	import flash.display.*;
	public class Hilditch 
	{
		static public var W:int;
		static public var H:int;
		static public var L:int;
		
		static public var points:Array;
		static public var output:Array;
		
		public function Hilditch(){}
		
		static public function parse( bd:BitmapData ):void
		{
			//assigne les variables statiques 
			W = bd.width;
			H = bd.height;
			L = W * H;
			points = [];
			output = [];
			
			var i:int = 0;
			var j:int = 0;

			for( i = 0; i < W ; ++i ) 
			{
				points.push( new Array() );
				output.push( new Array() );
				for( j = 0; j < H ; ++j ) 
				{
					
					if( bd.getPixel32( i, j ) != 0 )
					{
						
						points[ i ][ j ] = true;
						output[ i ][ j ] = true;

					}else
					{
						
						points[ i ][ j ] = false;
						output[ i ][ j ] = false;
						
					}
				}	
			}
		}
		
		static public function skeletize(  bd:BitmapData = null ):int
		{
			var count:int = 0;
			if( bd == null )return -1;
			if( points == null  )
			{
				
				//transforme le bitmapdata en un array 2D de booléennes
				bd.lock();
				parse( bd );
				bd.unlock();
				return skeletize( bd );
				
			}
			else
			{
				//lance une passe de thinning
				var Bp:int, Ap1:int, Ap2:int, Ap4:int;
				
				var p1:Boolean, p2:Boolean, p3:Boolean, p4:Boolean, p5:Boolean, p6:Boolean, p7:Boolean, p8:Boolean, p9:Boolean;
				var p10:Boolean, p11:Boolean, p12:Boolean, p13:Boolean, p14:Boolean, p15:Boolean;
				
				var i:int;
				var j:int;
				
				for( i = 2; i < W-2 ; ++i ) 
				{
					
					for( j = 2; j < H-2 ; ++j ) 
					{
						
						p1 = points[ i ][ j ];
						if( p1 )
						{
							
							count++;
							Bp = 0;
							Ap1 = 0;
							Ap2 = 0;
							Ap4 = 0;
							
							p2 = points[ i - 1 ][   j   ];
							p3 = points[ i - 1 ][ j + 1 ];
							p4 = points[   i   ][ j + 1 ];
							p5 = points[ i + 1 ][ j + 1 ];
							p6 = points[ i + 1 ][   j   ];
							p7 = points[ i + 1 ][ j - 1 ];
							p8 = points[   i   ][ j - 1 ];
							p9 = points[ i - 1 ][ j - 1 ];
							
							if( p2 )Bp++;
							if( p3 )Bp++;
							if( p4 )Bp++;
							if( p5 )Bp++;
							if( p6 )Bp++;
							if( p7 )Bp++;
							if( p8 )Bp++;
							if( p9 )Bp++;

							if( Bp >= 2 && Bp <= 6 )
							{
								
								Ap1 = A( p2, p3, p4, p5, p6, p7, p8, p9 );
								
								if( Ap1 == 1 )
								{
									
									p10 = points[ i -  2 ][ j - 1 ];
									p11 = points[ i - 2 ][   j   ];
									p12 = points[ i - 2 ][ j + 1 ];
									Ap2 = A( p11, p12, p3, p4, p1, p8, p9, p10 );
									
									if(  ( !p2 && !p4 && !p8 ) || Ap2 <= 4 )
									{
										
										p13 = points[ i - 1 ][ j + 2 ];
										p14 = points[   i   ][ j + 2 ];
										p15 = points[ i + 1 ][ j + 2 ];
										
										Ap4 = A( p3, p13, p14, p15, p5, p6, p1, p2 );
										
										if( ( !p2 && !p4 && !p6 ) || Ap4 <= 4 )
										{
											
											output[ i ][ j ] = false;
											
										}
									}
								}
							}
						} 
					}	
				}
		
				for( i = 0; i < W ; ++i ) 
				{
					for( j = 0; j < H ; ++j ) 
					{
						
						points[ i ][ j ] = false;
						if( output[ i ][ j ] )	points[ i ][ j ] = true;
						
					}	
				}
			}
			return count;
		}
		
		static function A( p2:Boolean, p3:Boolean, p4:Boolean, p5:Boolean, p6:Boolean, p7:Boolean, p8:Boolean, p9:Boolean ):int
		{
			
			var c:int = 0;
			if( !p2 && p3 )c++;
			if( !p3 && p4 )c++;
			if( !p4 && p5 )c++;
			if( !p5 && p6 )c++;
			if( !p6 && p7 )c++;
			if( !p7 && p8 )c++;
			if( !p8 && p9 )c++;
			if( !p9 && p2 )c++;
			return c;
			
		}
	}
}