root/as3/PotrAs/src/com/nitoyon/potras/PathList.as

/* Copyright (C) 2001-2007 Peter Selinger and nitoyon.
   Original code(Potrace v1.8) by Peter Selinger.
   Ported to ActionScript 3.0 by nitoyon.
   This file is part of PotrAs. It is free software and it is covered
   by the GNU General Public License. See the file COPYING for details. */

package com.nitoyon.potras
{
        import flash.display.BitmapData;
        import flash.geom.Point;
        import flash.geom.Rectangle;
        import flash.geom.Matrix;
        import flash.filters.ColorMatrixFilter;

        /**
         * Decompose the given bitmap into paths.
         */
        public class PathList
        {
                /**
                 * Decompose the given bitmap into paths.
                 *
                 * @param bitmapData BitmapData to create paths.
                 * @return paths.
                 */
                public static function create(bitmapData:BitmapData):Array
                {
                        var pathList:Array = [];
                        var y:int = 0;

                        var bmdCopy:BitmapData = bitmapData.clone();
                        var param:Object = {turdSize : 3};

                        // XOR
                        var filter:ColorMatrixFilter = new ColorMatrixFilter([
                                -1, 0, 0, 0, 255, 
                                -1, 0, 0, 0, 255, 
                                -1, 0, 0, 0, 255,
                                 0, 0, 0, 1, 0
                        ]);

                        var point:Point = new Point();
                        while(findNext(bmdCopy, point))
                        {
                                // calculate the sign by looking at the original
                                var sign:String = bmdCopy.getPixel(point.x, point.y) == 0 ? '+' : '-';

                                // calculate the path
                                var p:Object = findPath(bmdCopy, new Point(point.x, point.y - 1), sign, param.turnPolicy);
                                if(!p)
                                {
                                        pathList = null;
                                        break;
                                }

                                // update buffered image
                                xorPath(bmdCopy, p, filter);

                                // if it's a turd, eliminate it, else append it to the list
                                if(p.area > param.turdSize)
                                {
                                        pathList.push(p);
                                }
                        }

                        bmdCopy.dispose();
                        return pathList;
                }

                /**
                 * find the next set pixel in a row <= y.
                 *
                 * <p>Pixels are searched first left-to-right, then top-down.</p>
                 *
                 * <p>If found, return Point object. Else return null.</p>
                 */
                private static function findNext(bmd:BitmapData, pt:Point):Boolean
                {
                        for(var y:int = pt.y; y < bmd.height; y++)
                        {
                                for(var x:int = 0; x < bmd.width; x++)
                                {
                                        if(bmd.getPixel(x, y) == 0x000000)
                                        {
                                                pt.x = x;
                                                pt.y = y;
                                                return true;
                                        }
                                }
                        }

                        return false;
                }

                /**
                 * compute a path in the given pixmap, separating black from white.
                 *
                 * <p>Start path at the <code>startPoint</code>, which must be an upper
                 * left corner of the path.
                 * Also compute the area enclosed by the path. Return a
                 * new path object. (note that a legitimate path
                 * cannot have length 0).</p>
                 *
                 * @param sign Required for correct interpretation of turnpolicies.
                 */
                private static function findPath(bmd:BitmapData, startPoint:Point, sign:String, turnpolicy:int):Object
                {
                        var area:int = 0;
                        var pointList:Array = [];

                        var pt:Point = startPoint.clone();
                        var dir:Point = new Point(0, 1);

                        var rotateRight:Matrix = new Matrix(0, -1, 1, 0);
                        var rotateLeft:Matrix  = new Matrix(0, 1, -1, 0);

                        while(true)
                        {
                                // add point to path
                                pointList.push(pt.clone());

                                // move to next point
                                pt.offset(dir.x, dir.y);
                                area += pt.x * -dir.y;

                                // path complete?
                                if(pt.equals(startPoint))
                                {
                                        break;
                                }

                                // determine next direction
                                var c:Boolean = bmd.getPixel32(pt.x + (dir.x - dir.y - 1) /2, pt.y + (dir.y + dir.x + 1) / 2) == 0xff000000;
                                var d:Boolean = bmd.getPixel32(pt.x + (dir.x + dir.y - 1) /2, pt.y + (dir.y - dir.x + 1) / 2) == 0xff000000;

                                // c d
                                // X _
                                if(c && !d) // ambiguous turn
                                {
                                        if(true) // TODO: left turn only by nitoyon
                                        {
                                                dir = rotateLeft.transformPoint(dir);
                                        }
                                        else
                                        {
                                                dir = rotateRight.transformPoint(dir);
                                        }
                                }
                                else if(c) // left turn
                                {
                                        dir = rotateLeft.transformPoint(dir);
                                }
                                else if(!d) // right turn
                                {
                                        dir = rotateRight.transformPoint(dir);
                                }
                        }

                        // allocate new path object
                        var path:Object = {};
                        path.priv = pointList;
                        path.area = area;
                        path.sign = sign;

                        return path;
                }

                /**
                 *  xor the given pixmap with the interior of the given path. 
                 *  Note: the path must be within the dimensions of the pixmap.
                 */
                private static function xorPath(bm:BitmapData, p:Object, filter:ColorMatrixFilter):void
                {
                        var priv:Array = p.priv as Array;
                        var len:int = priv.length;

                        // get minimum x
                        var minX:int = 99999;
                        for(var i:int = 0; i < len; i++)
                        {
                                minX = Math.min(minX, priv[i].x);
                        }

                        var y1:int = priv[len - 1].y;
                        var pt:Point = new Point();
                        var rect:Rectangle = new Rectangle;
                        for(i = 0; i < len; i++)
                        {
                                var x:int = priv[i].x;
                                var y:int = priv[i].y;

                                if(y != y1)
                                {
                                        // efficiently invert the rectangle [minX, x] x [y,y1]
                                        var y2:int = Math.max(y, y1);
                                        pt.x = minX; pt.y = y2;
                                        rect.x = minX; rect.y = y2; rect.width = x - minX; rect.height = 1;
                                        bm.applyFilter(bm, rect, pt, filter);
                                        y1 = y;
                                }
                        }
                }
        }
}