/** * 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; } } }