/**
 * AS3 implementation of the ShortStraw Corner Finder (Wolin et al. 2008)
 * Felix Raab. 21 July 2009. www.betriebsraum.de/blog
 * Released under MIT license: http://www.opensource.org/licenses/mit-license.php
 */
package de.betriebsraum.geom.cornerfinder {
    
    import flash.geom.Point;
    import flash.geom.Rectangle;    
    
    public class ShortStraw {
        
        public static var DIAGONAL_INTERVAL:uint = 40;
        public static var STRAW_WINDOW:uint = 3;
        public static var MEDIAN_THRESHOLD:Number = 0.95;
        public static var LINE_THRESHOLD:Number = 0.95;
        
        public function ShortStraw() {
            
        }
        
        public static function getCornerPoints(points:Array):Array {
            if (!points || points.length < 2) return null;
            var s:Number = determineResampleSpacing(points);
            var resampled:Array = resamplePoints(points.concat(), s);
            var indices:Array = getCorners(resampled);
            var cornerPoints:Array = [];
            for (var i:int = 0; i < indices.length; i++) {
                var p:Point = resampled[indices[i]] as Point;
                cornerPoints.push(new Point(p.x, p.y));
            }
            return cornerPoints;
        }
        
        public static function getCornerIndices(points:Array):Array {
            if (!points || points.length < 2) return null;
            var s:Number = determineResampleSpacing(points);
            var resampled:Array = resamplePoints(points.concat(), s);
            return getCorners(resampled);
        }
        
        protected static function determineResampleSpacing(points:Array):Number {
            var b:Rectangle = boundingBox(points);
            var p1:Point = new Point(b.x, b.y);
            var p2:Point = new Point(b.x + b.width, b.y + b.height);
            var d:Number = Point.distance(p1, p2);
            return d / DIAGONAL_INTERVAL;
        }
        
        protected static function resamplePoints(points:Array, s:Number):Array {
            var interval:Number = s;
            var distance:Number = 0;
            var newPoints:Array = [(points[0] as Point).clone()];    
            for (var i:int = 1; i < points.length; i++) {
                var p1:Point = points[i - 1] as Point;
                var p2:Point = points[i] as Point;
                var d:Number = Point.distance(p1, p2);
                if ((distance + d) >= interval) {
                    var qx:Number = p1.x + ((interval - distance) / d) * (p2.x - p1.x);
                    var qy:Number = p1.y + ((interval - distance) / d) * (p2.y - p1.y);
                    var q:Point = new Point(qx, qy);
                    newPoints.push(q);
                    points.splice(i, 0, q);
                    distance = 0;
                } else {
                    distance += d;
                }
            }
            return newPoints;
        }
        
        protected static function getCorners(points:Array):Array {
            var corners:Array = [0];
            var w:uint = STRAW_WINDOW;
            var straws:Array = [];
            var i:int;
            for (i = w; i < points.length - w; i++) {
                var p1:Point = points[i - w] as Point;
                var p2:Point = points[i + w] as Point;
                straws.push(Point.distance(p1, p2));
            }
            var t:Number = median(straws) * MEDIAN_THRESHOLD;
            for (i = w; i < points.length - w; i++) {
                var s:Number = straws[i - w];
                if (s < t) {
                    var localMin:Number = Number.POSITIVE_INFINITY;
                    var localMinIndex:uint = i;
                    while (i < straws.length && s < t) {
                        if (s < localMin) {
                            localMin = s;
                            localMinIndex = i;
                        }
                        i++;
                        s = straws[i - w];
                    }
                    corners.push(localMinIndex);
                }
            }
            corners.push(points.length - 1);
            corners = postProcessCorners(points, corners, straws);
            return corners;
        }
        
        protected static function postProcessCorners(points:Array, corners:Array, straws:Array):Array {
            var go:Boolean = false;
            var i:int;
            var c1:uint;
            var c2:uint;
             while (!go) {
                go = true;
                for (i = 1; i < corners.length; i++) {
                    c1 = corners[i - 1];
                    c2 = corners[i];
                    if (!isLine(points, c1, c2)) {
                        var newCorner:uint = halfwayCorner(straws, c1, c2);
                        if (newCorner > c1 && newCorner < c2) {
                            corners.splice(i, 0, newCorner);
                            go = false;
                        }
                    }
                }
            }
               for (i = 1; i < corners.length - 1; i++) {
                c1 = corners[i - 1];
                c2 = corners[i + 1];
                if (isLine(points, c1, c2)) {
                    corners.splice(i, 1);
                    i--;
                }
            }
            return corners;
        }
        
        protected static function boundingBox(points:Array):Rectangle {
            var minX:Number = Number.POSITIVE_INFINITY;
            var maxX:Number = Number.NEGATIVE_INFINITY;
            var minY:Number = Number.POSITIVE_INFINITY;
            var maxY:Number = Number.NEGATIVE_INFINITY;
            for (var i:int = 0; i < points.length; i++) {
                var p:Point = points[i] as Point;
                if (p.x < minX) {
                    minX = p.x;
                }
                if (p.x > maxX) {
                    maxX = p.x;
                }
                if (p.y < minY) {
                    minY = p.y;
                }
                if (p.y > maxY) {
                    maxY = p.y;
                }
            }
            return new Rectangle(minX, minY, maxX - minX, maxY - minY);
        }
        
        protected static function median(values:Array):Number {
            var s:Array = values.concat();
            s.sort(Array.NUMERIC);
            var m:Number;
            if (s.length % 2 == 0) {
                m = s.length / 2;
                return (s[m - 1] + s[m]) / 2;
            } else {
                m = (s.length + 1) / 2;
                return s[m - 1];
            }
        }
        
        protected static function isLine(points:Array, a:uint, b:uint):Boolean {
            var distance:Number = Point.distance(points[a] as Point, points[b] as Point);
            var pathDistance:Number = pathDistance(points, a, b);
            return (distance / pathDistance) > LINE_THRESHOLD;
        }
        
        protected static function pathDistance(points:Array, a:uint, b:uint):Number {
            var d:Number = 0;
            for (var i:int = a; i < b; i++) {
                d += Point.distance(points[i] as Point, points[i + 1] as Point);
            }
            return d;
        }
        
        protected static function halfwayCorner(straws:Array, a:uint, b:uint):uint {
            var quarter:uint = (b - a) / 4;
            var minValue:Number = Number.POSITIVE_INFINITY;
            var minIndex:uint;
            var w:uint = STRAW_WINDOW;
            for (var i:int = a + quarter; i < b - quarter; i++) {
                var s:Number = straws[i - w];
                if (s < minValue) {
                    minValue = s;
                    minIndex = i;
                }
            }
            return minIndex;
        }

    }
    
}