// forked from xlune's "forked from: PV3Dその3”で日本語表示してみる
// forked from sake's PV3Dその3
/*
"PotrAs" 使って日本語表示してみる
*/
package
{
import caurina.transitions.Tweener;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.filters.BlurFilter;
import flash.filters.ColorMatrixFilter;
import flash.text.TextField;
import flash.text.TextFieldType;
import flash.utils.setInterval;
import flash.utils.clearInterval;
import org.papervision3d.cameras.Camera3D;
import org.papervision3d.materials.special.Letter3DMaterial;
import org.papervision3d.objects.DisplayObject3D;
import org.papervision3d.render.BasicRenderEngine;
import org.papervision3d.scenes.Scene3D;
import org.papervision3d.typography.Text3D;
import org.papervision3d.typography.fonts.HelveticaBold;
import org.papervision3d.view.Viewport3D;
import org.papervision3d.view.layer.ViewportLayer;
[SWF(width="465", height="465", backgroundColor="0x000000", frameRate="40")]
public class Main extends Sprite
{
private var _container:Sprite;
private var _viewport:Viewport3D;
private var _scene:Scene3D;
private var _camera:Camera3D;
private var _render:BasicRenderEngine;
private var _rootNode:DisplayObject3D;
private var _words:Text3D;
private var _theta:Number;
private var _delayTime:Number;
private var _wordMoveType:Number;
private const _ZOOM:Number = 20;
private const _FOCUS:Number = 30;
private const _DISTANCE:Number = 600;
private var _interval:uint;
private var _textField:TextField;
private var _submitButton:TextField;
private var _viewWords:String = "てきすとすりーでぃーで日本語を使ってみた";
public function Main()
{
init();
setMenu();
}
private function setMenu():void
{
var posY:int = stage.stageHeight - 40;
_textField = new TextField;
with(_textField)
{
type = TextFieldType.INPUT;
border = true;
borderColor = 0xFFFFFF;
textColor = 0xFFFFFF;
text = _viewWords;
multiline = false;
width = 300;
height = 20;
x = 30;
y = posY;
};
_submitButton = new TextField;
with(_submitButton)
{
selectable = false;
htmlText = '<P ALIGN="CENTER">GO</p>';
border = true;
borderColor = 0xFFFFFF;
textColor = 0xFFFFFF;
width = 70;
height = 20;
x = _textField.x + _textField.width + 20;
y = _textField.y;
};
_submitButton.addEventListener(MouseEvent.MOUSE_OUT, mouseOutHandler);
_submitButton.addEventListener(MouseEvent.MOUSE_OVER, mouseOverHandler);
_submitButton.addEventListener(MouseEvent.CLICK, clickHandler);
addChild(_textField);
addChild(_submitButton);
}
private function init():void
{
_theta = 0;
_wordMoveType = 0;
_delayTime = 0;
_container = new Sprite();
addChild(_container);
_container.x = stage.stageWidth / 2;
_container.y = stage.stageHeight / 2;
_viewport = new Viewport3D(0, 0, true, true);
_scene = new Scene3D();
_camera = new Camera3D();
_render = new BasicRenderEngine();
_rootNode = _scene.addChild(new DisplayObject3D("rootNode"));
addChild(_viewport);
_camera.target = DisplayObject3D.ZERO;
_camera.zoom = _ZOOM;
_camera.focus = _FOCUS;
var mat:Letter3DMaterial = new Letter3DMaterial();
mat.fillColor = 0xFFFFFF;
mat.doubleSided = true;
mat.interactive = true;
_words = new Text3D(_viewWords, new CustomFont(_viewWords, "_ゴシック", 75), mat);
_rootNode.addChild(_words);
_words.scale = 0.4;
dispersionWords(_words);
_interval = setInterval(moveWords, _viewWords.length * 300 + 1500);
addEventListener(Event.ENTER_FRAME, enterFrameHandler);
}
private function clickHandler(event:MouseEvent):void
{
removeEventListener(Event.ENTER_FRAME, enterFrameHandler);
clearInterval(_interval);
removeChild(_viewport);
removeChild(_container);
_textField.text = _viewWords = _textField.text || "文字を入力してください！！";
init();
}
private function mouseOverHandler(event:MouseEvent):void
{
var tg:TextField = TextField(event.target);
with(tg)
{
textColor = 0xFF9900;
borderColor = 0xFF9900;
}
}
private function mouseOutHandler(event:MouseEvent):void
{
var tg:TextField = TextField(event.target);
with(tg)
{
textColor = 0xFFFFFF;
borderColor = 0xFFFFFF;
}
}
private function dispersionWords(words:Text3D):void
{
for each(var word:DisplayObject3D in words.letters)
{
word.extra = {x:word.x, y:word.y, z:word.z};
word.x = word.y = word.z = word.scale = 0;
Tweener.addTween(
word,
{
scale: 1,
x: Math.random() * 2000 - 1000,
y: Math.random() * 2000 - 1000,
z: Math.random() * 2000 - 1000,
rotationX: Math.random() * 360,
rotationY: Math.random() * 360,
rotationZ: Math.random() * 360,
time: 3,
delay: 2 * Math.random() + 1
}
);
}
}
private function moveWords():void
{
if (_wordMoveType % 2 == 0)
{
resetWords(_words);
_delayTime = 0;
_wordMoveType++;
}
else
{
breakWords(_words);
_wordMoveType++;
}
}
private function resetWords(words:Text3D):void
{
for each(var word:DisplayObject3D in words.letters)
{
Tweener.addTween(
word,
{
x: word.extra.x,
y: word.extra.y,
z: word.extra.z,
rotationX: 0,
rotationY: 0,
rotationZ: 0,
time: 1,
transition: "easeOutBounce",
delay: _delayTime
}
);
Tweener.addTween(
word,
{
rotationY: 720,
time: 1,
delay: _delayTime + 2
}
);
_delayTime += 0.1;
}
}
private function breakWords(words:Text3D):void
{
for each(var word:DisplayObject3D in words.letters)
{
Tweener.addTween(
word,
{
x: Math.random() * 2000 - 1000,
y: Math.random() * 2000 - 1000,
z: Math.random() * 2000 - 1000,
rotationX: Math.random() * 360,
rotationY: Math.random() * 360,
rotationZ: Math.random() * 360,
time: 2,
delay: 1 * Math.random()
}
);
}
}
private function enterFrameHandler(event:Event):void
{
_camera.x = _DISTANCE * Math.sin(_theta * Math.PI / 180);
_camera.z = _DISTANCE * Math.cos(_theta * Math.PI / 180);
_theta += 0.3;
setBlur(_words);
_render.renderScene(_scene, _camera, _viewport);
}
private function DistanceFromCamera(obj:DisplayObject3D):Number
{
var vecX:Number = obj.sceneX - _camera.x;
var vecY:Number = obj.sceneY - _camera.y;
var vecZ:Number = obj.sceneZ - _camera.z;
return Math.sqrt((vecX * vecX) + (vecY * vecY) + (vecZ * vecZ));
}
private function setBlur(words:Text3D):void
{
for each(var word:DisplayObject3D in words.letters)
{
var vpl:ViewportLayer = word.createViewportLayer(_viewport, true);
var d:Number = Math.abs(DistanceFromCamera(word) - _DISTANCE) / 40;
vpl.filters = [new BlurFilter(d, d, 1)];
}
}
}
}
/** ======================================================================================
* 日本語表示用のカスタムフォント3D
** ====================================================================================*/
import org.papervision3d.typography.Font3D;
import flash.display.BitmapData;
import flash.geom.Point;
import flash.text.TextField;
import flash.text.TextFormat;
class CustomFont extends Font3D
{
private static var __motifs:Object = {};
private static var __widths:Object = {};
private static var __height:Number = 119;
private var _initialized:Boolean = false;
private var _text:String;
private var _font:String;
private var _size:uint;
public function CustomFont(text:String, font:String, size:uint)
{
_text = text;
_font = font;
_size = size;
}
private function initialize():void {
if(!_initialized)
{
initializeMotifsAndWidths();
_initialized = true;
}
}
////////////////////////////////////////////
override public function get motifs():Object
{
if(!_initialized)initialize();
return __motifs;
}
override public function get widths():Object
{
if(!_initialized)initialize();
return __widths;
}
override public function get height():Number
{
if(!_initialized)initialize();
return __height;
}
////////////////////////////////////////////
private function initializeMotifsAndWidths():void
{
var arr:Array = _text.split("");
var result:Array;
for(var i:uint=0,max:uint=arr.length; i<max; i++)
{
if(!__motifs[arr[i]])
{
result = getMotifsAndWidths(arr[i]);
__motifs[arr[i]] = result[0];
__widths[arr[i]] = result[1];
}
}
}
private function getMotifsAndWidths(str:String):Array
{
var arr:Array = [];
var pathList:ClosedPathList = CustomFont.traceLetter(str, _size, _font);
for each(var path:ClosedPath in pathList.$a)
{
arr = arr.concat(getPoints(path.$a));
}
var data:Array = [
arr,
_size
];
return data;
}
/**
* PotrAs(traceLetter) edited
*/
public static function traceLetter(letter:String, fontSize:int, font:String="_ゴシック"):ClosedPathList
{
var tf:TextFormat = new TextFormat();
tf.font = font;
tf.size = fontSize;
var text:TextField = new TextField();
text.defaultTextFormat = tf;
text.autoSize = "left";
text.text = letter;
// We have to use threshold method to binarize, because Mac OS draws antialiased text.
var bmdtmp:BitmapData = new BitmapData(fontSize * letter.length, fontSize * 1.2, true);
var bitmapdata:BitmapData = bmdtmp.clone();
bmdtmp.draw(text);
bitmapdata.threshold(bmdtmp, bmdtmp.rect, new Point(), "<", 0xffdddddd, 0xff000000);
var pathList:Array = PathList.create(bitmapdata);
var c:ClosedPathList = ProcessPath.processPath(pathList);
bmdtmp.dispose();
bitmapdata.dispose();
return c;
}
/**
* ClosedPath(draw) edited
*/
public function getPoints($a:Array):Array
{
var arr:Array = [];
var pt:Point = $a[$a.length - 1].c[2];
arr.push(['M', [pt.x, pt.y]]);
for(var i:int = 0; i < $a.length; i++)
{
var c:Curve = $a[i];
if(c.tag == ProcessPath.POTRACE_CORNER)
{
arr.push(['L', [c.c[1].x, c.c[1].y]]);
arr.push(['L', [c.c[2].x, c.c[2].y]]);
}
else
{
for(var t:Number = 0; t < 1.0; t += 0.02)
{
var p:Point = getBezierPoint(pt, c.c[0], c.c[1], c.c[2], t);
arr.push(['L', [p.x, p.y]]);
}
arr.push(['L', [c.c[2].x, c.c[2].y]]);
}
pt = c.c[2];
}
return arr;
}
/**
* ClosedPath(getBezierPoint) edited
*/
protected function getBezierPoint(p0:Point, p1:Point, p2:Point, p3:Point, t:Number):Point
{
return new Point(Math.pow(1 - t, 3) * p0.x + 3 * t * Math.pow(1 - t, 2) * p1.x
+ 3 * t * t * (1 - t) * p2.x + t * t * t * p3.x,
Math.pow(1 - t, 3) * p0.y + 3 * t * Math.pow(1 - t, 2) * p1.y
+ 3 * t * t * (1 - t) * p2.y + t * t * t * p3.y);
}
}
/** ======================================================================================
* これ以下はwonderflでPotrAsが使えないようなので無茶貼りです。
* import com.nitoyon.potras.*; の代替
* http://www.libspark.org/wiki/nitoyon/PotrAs
** ====================================================================================*/
/* 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. */
import flash.geom.Point;
import flash.display.Graphics;
class ClosedPath
{
/**
*
*/
public var $a:Array;
/**
* Constructor.
*
* initialize the members of the given curve structure to size m.
* Return 0 on success, 1 on error with errno set.
*/
public function ClosedPath(array:Array = null):void
{
$a = array || [];
}
/**
* draw
*/
public function draw(g:Graphics):void
{
var pt:Point = $a[$a.length - 1].c[2];
g.moveTo(pt.x, pt.y);
for(var i:int = 0; i < $a.length; i++)
{
var c:Curve = $a[i];
if(c.tag == ProcessPath.POTRACE_CORNER)
{
g.lineTo(c.c[1].x, c.c[1].y);
g.lineTo(c.c[2].x, c.c[2].y);
}
else
{
for(var t:Number = 0; t < 1.0; t += 0.02)
{
var p:Point = getBezierPoint(pt, c.c[0], c.c[1], c.c[2], t);
g.lineTo(p.x, p.y);
}
g.lineTo(c.c[2].x, c.c[2].y);
}
pt = c.c[2];
}
}
/**
* Get quad bezier curve point.
*/
private function getBezierPoint(p0:Point, p1:Point, p2:Point, p3:Point, t:Number):Point
{
return new Point(Math.pow(1 - t, 3) * p0.x + 3 * t * Math.pow(1 - t, 2) * p1.x
+ 3 * t * t * (1 - t) * p2.x + t * t * t * p3.x,
Math.pow(1 - t, 3) * p0.y + 3 * t * Math.pow(1 - t, 2) * p1.y
+ 3 * t * t * (1 - t) * p2.y + t * t * t * p3.y);
}
}
/* 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. */
import flash.display.Graphics;
import flash.display.BitmapData;
class ClosedPathList
{
/**
* ClosePath array.
*/
public var $a:Array;
/**
* Constructor.
*/
public function ClosedPathList():void
{
$a = [];
}
/**
* trace bitmap
*/
public static function trace(bmpdata:BitmapData):ClosedPathList
{
var pathList:Array = PathList.create(bmpdata);
return ProcessPath.processPath(pathList);
}
/**
* draw.
*/
public function draw(g:Graphics):void
{
for each(var path:* in $a)
{
if(path is ClosedPath)
{
path.draw(g);
}
}
}
}
/* 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. */
import flash.display.BitmapData;
import flash.geom.Point;
import flash.geom.Rectangle;
import flash.geom.Matrix;
import flash.filters.ColorMatrixFilter;
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;
}
}
}
}
/* 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. */
import flash.geom.Point;
class Curve
{
public var tag:int; /* tag[n]: POTRACE_CORNER or POTRACE_CURVETO */
public var c:Array = new Array(3); /* c[n][i]: control points.
c[n][0] is unused for tag[n]=POTRACE_CORNER */
/* the remainder of this structure is special to privcurve, and is
used in EPS debug output and special EPS "short coding". These
fields are valid only if "alphacurve" is set. */
public var vertex:Point; /* for POTRACE_CORNER, this equals c[1] */
public var alpha:Number; /* only for POTRACE_CURVETO */
public var alpha0:Number; /* "uncropped" alpha parameter - for debug output only */
public var beta:Number;
/**
* Constructor.
*
* initialize the members of the given curve structure to size m.
* Return 0 on success, 1 on error with errno set.
*/
public function Curve():void
{
c[0] = new Point();
c[1] = new Point();
c[2] = new Point();
vertex = new Point();
}
public function toString():String
{
return "alpha0: " + alpha0 + "\n"
+ "alpha: " + alpha + "\n"
+ "beta: " + beta + "\n"
+ "corner: " + (tag == ProcessPath.POTRACE_CORNER) + "\n"
+ "bezier: " + c[0] + "," + c[1] + "," + c[2];
}
}
/* 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. */
import flash.display.BitmapData;
import flash.geom.*;
class ProcessPath
{
/**
* it suffices that this is longer than any
* path; it need not be really infinite
*/
private static const INFTY:int = 10000000;
public static const POTRACE_CURVETO:int = 1;
public static const POTRACE_CORNER:int = 2;
/**
* On success, returns a Potrace state st with st->status ==
* POTRACE_STATUS_OK. On failure, returns NULL if no Potrace state
* could be created (with errno set), or returns an incomplete Potrace
* state (with st->status == POTRACE_STATUS_INCOMPLETE). Complete or
* incomplete Potrace state can be freed with potrace_state_free().
*/
public static function processPath(pathList:Array):ClosedPathList
{
var curveList:ClosedPathList = new ClosedPathList();
for(var i:int = 0; i < pathList.length; i++)
{
var sums:Array = ProcessPath.calcSums(pathList[i].priv as Array) as Array;
var lons:Array = ProcessPath.calcLon(pathList[i].priv as Array);
var po:Array = ProcessPath.bestPolygon(pathList[i].priv as Array, lons, sums);
var vertex:Array = ProcessPath.adjustVertices(pathList[i].priv as Array, sums, po);
var curve:ClosedPath = ProcessPath.smooth(vertex, pathList[i].sign, .9);
curveList.$a.push(curve);
}
return curveList;
}
/**
* Preparation: fill in the sum* fields of a path (used for later
* rapid summing). Return 0 on success, 1 with errno set on
* failure.
*/
public static function calcSums(pt:Array):Array
{
var n:int = pt.length;
var sums:Array = new Array(n + 1);
// origin
var x0:int = pt[0].x;
var y0:int = pt[0].y;
// preparatory computation for later fast summing
sums[0] = new Sums();
sums[0].x2 = sums[0].xy = sums[0].y2 = sums[0].x = sums[0].y = 0;
for(var i:int = 0; i < n; i++)
{
var x:int = pt[i].x - x0;
var y:int = pt[i].y - y0;
sums[i + 1] = new Sums();
sums[i + 1].x = sums[i].x + x;
sums[i + 1].y = sums[i].y + y;
sums[i + 1].x2 = sums[i].x2 + x*x;
sums[i + 1].xy = sums[i].xy + x*y;
sums[i + 1].y2 = sums[i].y2 + y*y;
}
return sums;
}
/**
* Stage 1: determine the straight subpaths (Sec. 2.2.1). Fill in the
* "lon" component of a path object (based on pt/len). For each i,
* lon[i] is the furthest index such that a straight line can be drawn
* from i to lon[i]. Return 1 on error with errno set, else 0.
*/
public static function calcLon(pt:Array):Array
{
var lon:Array = [];
var n:int = pt.length;
var j:Number;
// initialize the nc data structure. Point from each point to the
// furthest future point to which it is connected by a vertical or
// horizontal segment. We take advantage of the fact that there is
// always a direction change at 0 (due to the path decomposition
// algorithm). But even if this were not so, there is no harm, as
// in practice, correctness does not depend on the word "furthest"
// above.
var nc:Array = [];
var k:int = 0;
for(var i:int = n - 1; i >= 0; i--)
{
if(pt[i].x != pt[k].x && pt[i].y != pt[k].y)
{
k = i + 1; // necessarily i<n-1 in this case
}
nc[i] = k;
}
// determine pivot points: for each i, let pivk[i] be the furthest k
// such that all j with i<j<k lie on a line connecting i,k. */
var pivk:Array = [];
var ct:Array;
var dir:int;
var k1:int;
var constraint0:Point = new Point();
var constraint1:Point = new Point();
var cur:Point = new Point();
var off:Point = new Point();
var dk:Point = new Point();
for(i = n - 1; i >= 0; i--)
{
ct = [0, 0, 0, 0];
// keep track of "directions" that have occurred
dir = (3 + 3 * (pt[mod(i + 1, n)].x - pt[i].x) + (pt[mod(i + 1, n)].y - pt[i].y)) / 2;
ct[dir]++;
constraint0.x = constraint0.y = constraint1.x = constraint1.y = 0;
// find the next k such that no straight line from i to k
k = nc[i];
k1 = i;
var foundk:Boolean = false;
while(true)
{
dir = (3 + 3 * sign(pt[k].x - pt[k1].x) + sign(pt[k].y - pt[k1].y)) / 2;
ct[dir]++;
// if all four "directions" have occurred, cut this path
if(ct[0] && ct[1] && ct[2] && ct[3])
{
pivk[i] = k1;
foundk = true;
break;
}
cur.x = pt[k].x - pt[i].x;
cur.y = pt[k].y - pt[i].y;
// see if current constraint is violated
if(xprod(constraint0, cur) > 0 || xprod(constraint1, cur) < 0)
{
break;
}
// else, update constraint
if (Math.abs(cur.x) <= 1 && Math.abs(cur.y) <= 1)
{
// no constraint
}
else
{
off.x = cur.x + ((-cur.y >= 0 && (-cur.y > 0 || cur.x < 0)) ? 1 : -1);
off.y = cur.y + ((-cur.x <= 0 && (-cur.x < 0 || cur.y < 0)) ? 1 : -1);
if(xprod(constraint0, off) <= 0)
{
constraint0.x = off.x;
constraint0.y = off.y;
}
off.x = cur.x + ((-cur.y <= 0 && (-cur.y < 0 || cur.x < 0)) ? 1 : -1);
off.y = cur.y + ((-cur.x >= 0 && (-cur.x > 0 || cur.y < 0)) ? 1 : -1);
if(xprod(constraint1, off) >= 0)
{
constraint1.x = off.x;
constraint1.y = off.y;
}
}
k1 = k;
k = nc[k1];
if(!cyclic(k, i, k1))
{
break;
}
}
// constraint
if(!foundk)
{
dk.x = sign(pt[k].x-pt[k1].x);
dk.y = sign(pt[k].y-pt[k1].y);
cur.x = pt[k1].x - pt[i].x;
cur.y = pt[k1].y - pt[i].y;
// find largest integer j such that xprod(constraint0, cur+j*dk) >= 0
// and xprod(constraint1, cur+j*dk) <= 0. Use bilinearity of xprod.
var a:int = xprod(constraint0, cur);
var b:int = xprod(constraint0, dk);
var c:int = xprod(constraint1, cur);
var d:int = xprod(constraint1, dk);
// find largest integer j such that a+j*b>=0 and c+j*d<=0.
// This can be solved with integer arithmetic.
j = INFTY;
if(b > 0)
{
j = floordiv(-a, b);
}
if(d < 0)
{
j = Math.min(j, floordiv(c, -d));
}
pivk[i] = mod(k1 + j, n);
}
// foundk
} // for i
// clean up: for each i, let lon[i] be the largest k such that for
// all i' with i<=i'<k, i'<k<=pivk[i'].
j = pivk[n - 1];
lon[n - 1] = j;
for(i = n - 2; i >= 0; i--)
{
if(cyclic(i + 1, pivk[i], j))
{
j = pivk[i];
}
lon[i] = j;
}
for(i = n - 1; cyclic(mod(i + 1, n), j, lon[i]); i--)
{
lon[i] = j;
}
return lon;
}
/**
* Stage 2: calculate the optimal polygon (Sec. 2.2.2-2.2.4).
*
* find the optimal polygon. Fill in the m and po components. Return 1
* on failure with errno set, else 0. Non-cyclic version: assumes i=0
* is in the polygon. Fixme: ### implement cyclic version.
*/
public static function bestPolygon(pt:Array, lon:Array, sums:Array):Array
{
var i:int, j:int, k:int;
var n:int = pt.length;
var clip0:Array = new Array(n); // clip0[n]: longest segment pointer, non-cyclic
var clip1:Array = new Array(n + 1); // clip1[n+1]: backwards segment pointer, non-cyclic
// calculate clipped paths
for(i = 0; i < n; i++)
{
var c:int = mod(lon[mod(i - 1, n)] - 1, n);
if(c == i)
{
c = mod(i + 1, n);
}
if(c < i)
{
clip0[i] = n;
}
else
{
clip0[i] = c;
}
}
// calculate backwards path clipping, non-cyclic. j <= clip0[i] iff clip1[j] <= i, for i,j=0..n.
j = 1;
for(i = 0; i < n; i++)
{
while(j <= clip0[i])
{
clip1[j] = i;
j++;
}
}
var seg0:Array = new Array(n + 1); // seg0[m+1]: forward segment bounds, m<=n
var seg1:Array = new Array(n + 1); // seg1[m+1]: backward segment bounds, m<=n
// calculate seg0[j] = longest path from 0 with j segments
i = 0;
for(j = 0; i < n; j++)
{
seg0[j] = i;
i = clip0[i];
}
seg0[j] = n;
var m:int = j;
// calculate seg1[j] = longest path to n with m-j segments
i = n;
for(j = m; j > 0; j--)
{
seg1[j] = i;
i = clip1[i];
}
seg1[0] = 0;
// now find the shortest path with m segments, based on penalty3
// note: the outer 2 loops jointly have at most n interations, thus
// the worst-case behavior here is quadratic. In practice, it is
// close to linear since the inner loop tends to be short.
var pen:Array = new Array(n + 1); // pen[n+1]: penalty vector
var prev:Array = new Array(n + 1); // prev[n+1]: best path pointer vector
var thispen:Number;
pen[0] = 0;
for(j = 1; j <= m; j++)
{
for(i = seg1[j]; i <= seg0[j]; i++)
{
var best:Number = -1;
for(k = seg0[j - 1]; k >= clip1[i]; k--)
{
thispen = penalty3(pt, k, i, sums) + pen[k];
if(best < 0 || thispen < best)
{
prev[i] = k;
best = thispen;
}
}
pen[i] = best;
}
}
// read off shortest path
var po:Array = new Array(m);
for(i = n, j = m - 1; i > 0; j--)
{
po[j] = i = prev[i];
}
return po;
}
/**
* Auxiliary function: calculate the penalty of an edge from i to j in
* the given path. This needs the "lon" and "sum*" data.
*/
private static function penalty3(pt:Array, i:int, j:int, sums:Array):Number
{
var n:int = pt.length;
// assume 0 <= i < j <= n
var r:int = 0; // rotations from i to j
if(j >= n)
{
j -= n;
r += 1;
}
var x:Number = sums[j + 1].x - sums[i].x + r * sums[n].x;
var y:Number = sums[j + 1].y - sums[i].y + r * sums[n].y;
var x2:Number = sums[j + 1].x2 - sums[i].x2 + r * sums[n].x2;
var xy:Number = sums[j + 1].xy - sums[i].xy + r * sums[n].xy;
var y2:Number = sums[j + 1].y2 - sums[i].y2 + r * sums[n].y2;
var k:Number = j + 1 - i + r * n;
var px:Number = (pt[i].x + pt[j].x) / 2.0 - pt[0].x;
var py:Number = (pt[i].y + pt[j].y) / 2.0 - pt[0].y;
var ey:Number = (pt[j].x - pt[i].x);
var ex:Number = -(pt[j].y - pt[i].y);
var a:Number = ((x2 - 2 * x * px) / k + px * px);
var b:Number = ((xy - x * py - y * px) / k + px * py);
var c:Number = ((y2 - 2 * y * py) / k + py * py);
var s:Number = ex * ex * a + 2 * ex * ey * b + ey * ey * c;
return Math.sqrt(s);
}
/**
/* Stage 3: vertex adjustment (Sec. 2.3.1).
*
* Adjust vertices of optimal polygon: calculate the intersection of
* the two "optimal" line segments, then move it into the unit square
* if it lies outside. Return 1 with errno set on error; 0 on
* success.
*/
public static function adjustVertices(pt:Array, sums:Array, po:Array):Array
{
var m:int = po.length;
var n:int = pt.length;
var i:int, j:int, k:int, l:int;
// represent each line segment as a singular quadratic form; the
// distance of a point (x,y) from the line segment will be
// (x,y,1)Q(x,y,1)^t, where Q=q[i].
var q:Array = [];
var v:Point3D = new Point3D();
var ctr:Point = new Point();
var dir:Point = new Point();
for(i = 0; i < m; i++)
{
// calculate "optimal" point-slope representation for each line segment
j = po[(i + 1) % m];
j = mod(j - po[i], n) + po[i];
ctr.x = ctr.y = dir.x = dir.y = 0;
pointslope(pt, sums, po[i], j, ctr, dir);
q[i] = new QuadraticForm();
var d1:Number = dir.x * dir.x + dir.y * dir.y;
if(d1 != 0.0)
{
v[0] = dir.y;
v[1] = -dir.x;
v[2] = -v[1] * ctr.y - v[0] * ctr.x
q[i].fromVectorMultiply(v).scalar(1 / d1);
}
}
// now calculate the "intersections" of consecutive segments.
// Instead of using the actual intersection, we find the point
// within a given unit square which minimizes the square distance to
// the two lines.
var vertex:Array = [];
var p0:Point = pt[0].clone();
var s:Point = new Point();
var w:Point = new Point();
var _q:QuadraticForm = new QuadraticForm();
var minCoord:Point = new Point;
for(i = 0; i < m; i++)
{
var z:int;
vertex[i] = new Point();
// let s be the vertex, in coordinates relative to x0/y0
s.x = pt[po[i]].x - p0.x;
s.y = pt[po[i]].y - p0.y;
// intersect segments i-1 and i
j = mod(i - 1, m);
// add quadratic forms
var Q:QuadraticForm = q[j].clone().add(q[i]);
while(1)
{
// minimize the quadratic form Q on the unit square
// find intersection
var det:Number = Q[0][0] * Q[1][1] - Q[0][1] * Q[1][0];
if(det != 0.0)
{
w.x = (-Q[0][2] * Q[1][1] + Q[1][2] * Q[0][1]) / det;
w.y = ( Q[0][2] * Q[1][0] - Q[1][2] * Q[0][0]) / det;
break;
}
// matrix is singular - lines are parallel. Add another,
// orthogonal axis, through the center of the unit square
if(Q[0][0] > Q[1][1])
{
v[0] = -Q[0][1];
v[1] = Q[0][0];
}
else if(Q[1][1])
{
v[0] = -Q[1][1];
v[1] = Q[1][0];
}
else
{
v[0] = 1;
v[1] = 0;
}
var d:Number = v[0] * v[0] + v[1] * v[1];
v[2] = - v[1] * s.y - v[0] * s.x;
Q.add(_q.fromVectorMultiply(v)).scalar(1 / d);
}
var dx:Number = Math.abs(w.x - s.x);
var dy:Number = Math.abs(w.y - s.y);
if(dx <= .5 && dy <= .5)
{
vertex[i].x = w.x + p0.x;
vertex[i].y = w.y + p0.y;
continue;
}
// the minimum was not in the unit square; now minimize quadratic
// on boundary of square
var min:Number, cand:Number; // minimum and candidate for minimum of quad. form
minCoord.x = s.x; minCoord.y = s.y; // coordinates of minimum
min = Q.apply(s);
if(Q[0][0] != 0.0)
{
for(z = 0; z < 2; z++) // value of the y-coordinate
{
w.y = s.y - 0.5 + z;
w.x = - (Q[0][1] * w.y + Q[0][2]) / Q[0][0];
dx = (w.x - s.x > 0 ? w.x - s.x : s.x - w.x);
cand = Q.apply(w);
if(dx <= .5 && cand < min)
{
min = cand;
minCoord.x = w.x; minCoord.y = w.y;
}
}
}
if(Q[1][1] != 0.0)
{
for(z = 0; z < 2; z++) // value of the x-coordinate
{
w.x = s.x - 0.5 + z;
w.y = - (Q[1][0] * w.x + Q[1][2]) / Q[1][1];
dy = (w.y - s.y > 0 ? w.y - s.y : s.y - w.y);
cand = Q.apply(w);
if(dy <= .5 && cand < min)
{
min = cand;
minCoord.x = w.x; minCoord.y = w.y;
}
}
}
// check four corners
for(l = 0; l < 2; l++)
{
for(k = 0; k < 2; k++)
{
w.x = s.x - 0.5 + l;
w.y = s.y - 0.5 + k;
cand = Q.apply(w);
if(cand < min)
{
min = cand;
minCoord.x = w.x; minCoord.y = w.y;
}
}
}
vertex[i].x = minCoord.x + p0.x;
vertex[i].y = minCoord.y + p0.y;
continue;
}
return vertex;
}
/**
* Stage 4: smoothing and corner analysis (Sec. 2.3.3)
*
* Always succeeds and returns 0
*/
public static function smooth(vertex:Array, sign:String, alphamax:Number = 1.0):ClosedPath
{
var m:int = vertex.length;
var closedPath:ClosedPath = new ClosedPath();
var i:int;
if(sign == '-')
{
// reverse orientation of negative paths
var tmp:Point;
for(i = 0, j = m - 1; i < j; i++, j--)
{
tmp = vertex[i];
vertex[i] = vertex[j];
vertex[j] = tmp;
}
}
// examine each vertex and find its best fit
var p2:Point = new Point();
var p3:Point = new Point();
var p4:Point = new Point();
for(i = 0; i < m; i++)
{
var j:int = (i + 1) % m;
var k:int = (i + 2) % m;
interval(1 / 2.0, vertex[k], vertex[j], p4);
var curve:Curve = new Curve();
curve.vertex.x =vertex[j].x;
curve.vertex.y =vertex[j].y;
var denom:Number = ddenom(vertex[i], vertex[k]);
var alpha:Number;
if(denom != 0.0)
{
var dd:Number = dpara(vertex[i], vertex[j], vertex[k]) / denom;
dd = dd < 0 ? -dd : dd;
alpha = dd > 1 ? (1 - 1.0 / dd) / 0.75 : 0;
}
else
{
alpha = 4 / 3.0;
}
curve.alpha0 = alpha; // remember "original" value of alpha
if(alpha > alphamax) // pointed corner
{
curve.tag = POTRACE_CORNER;
curve.c[0].x = 0; curve.c[0].y = 0;
curve.c[1].x = vertex[j].x; curve.c[1].y = vertex[j].y;
curve.c[2].x = p4.x; curve.c[2].y = p4.y;
}
else
{
if(alpha < 0.55)
{
alpha = 0.55;
}
else if(alpha > 1)
{
alpha = 1;
}
interval(.5 + .5 * alpha, vertex[i], vertex[j], p2);
interval(.5 + .5 * alpha, vertex[k], vertex[j], p3);
curve.tag = POTRACE_CURVETO;
curve.c[0].x = p2.x; curve.c[0].y = p2.y;
curve.c[1].x = p3.x; curve.c[1].y = p3.y;
curve.c[2].x = p4.x; curve.c[2].y = p4.y;
}
curve.alpha = alpha; // store the "cropped" value of alpha
curve.beta = 0.5;
closedPath.$a[j] = curve;
}
return closedPath;
}
/**
* determine the center and slope of the line i..j. Assume i<j. Needs
* "sum" components of p to be set.
*/
public static function pointslope(pt:Array, sums:Array, i:int, j:int, ctr:Point, dir:Point):void
{
// assume i<j
var n:int = pt.length;
var x:Number, y:Number, x2:Number, xy:Number, y2:Number;
var k:Number;
var a:Number, b:Number, c:Number, lambda2:Number, l:Number;
var r:int = 0; // rotations from i to j
while (j >= n)
{
j -= n;
r += 1;
}
while(i >= n)
{
i -= n;
r -= 1;
}
while(j < 0)
{
j += n;
r -= 1;
}
while(i < 0)
{
i += n;
r += 1;
}
x = sums[j + 1].x - sums[i].x + r * sums[n].x;
y = sums[j + 1].y - sums[i].y + r * sums[n].y;
x2 = sums[j + 1].x2 - sums[i].x2 + r * sums[n].x2;
xy = sums[j + 1].xy - sums[i].xy + r * sums[n].xy;
y2 = sums[j + 1].y2 - sums[i].y2 + r * sums[n].y2;
k = j + 1 - i + r * n;
ctr.x = x / k;
ctr.y = y / k;
a = (x2 - x * x / k) / k;
b = (xy - x * y / k) / k;
c = (y2 - y * y / k) / k;
lambda2 = (a + c + Math.sqrt((a - c)*(a - c) + 4 * b * b)) / 2; // larger e.value
// now find e.vector for lambda2
a -= lambda2;
c -= lambda2;
if(Math.abs(a) >= Math.abs(c))
{
l = Math.sqrt(a * a + b * b);
if(l != 0)
{
dir.x = -b / l;
dir.y = a / l;
}
}
else
{
l = Math.sqrt(c * c + b * b);
if (l != 0)
{
dir.x = -c / l;
dir.y = b / l;
}
}
if(l == 0)
{
dir.x = dir.y = 0; // sometimes this can happen when k=4:
// the two eigenvalues coincide
}
}
/**
* range over the straight line segment [a,b] when lambda ranges over [0,1]
*/
public static function interval(lambda:Number, a:Point, b:Point, ret:Point):void
{
ret.x = a.x + lambda * (b.x - a.x);
ret.y = a.y + lambda * (b.y - a.y);
}
/**
* some useful macros. Note: the "mod" macro works correctly for
* negative a. Also note that the test for a>=n, while redundant,
* speeds up the mod function by 70% in the average case (significant
* since the program spends about 16% of its time here - or 40%
* without the test). The "floordiv" macro returns the largest integer
* <= a/n, and again this works correctly for negative a, as long as
* a,n are integers and n>0.
*/
private static function mod(a:int, n:int):int
{
return a >= n ? a % n : a >= 0 ? a : n - 1 - (-1 - a) % n;
}
private static function floordiv(a:int, n:int):int
{
return a >= 0 ? a / n : -1 - (-1 - a) / n;
}
/**
* calculate p1 x p2
*/
private static function xprod(p1:Point, p2:Point):int
{
return p1.x * p2.y - p1.y * p2.x;
}
/**
* sign
*/
private static function sign(x:Number):int
{
return (x > 0 ? 1 : x < 0 ? -1 : 0);
}
/**
* return a direction that is 90 degrees counterclockwise from p2-p0,
* but then restricted to one of the major wind directions (n, nw, w, etc)
*/
public static function dorth_infty(p0:Point, p2:Point):Point
{
return new Point(
sign(p2.x - p0.x),
-sign(p2.y - p0.y)
);
}
/**
* return (p1-p0)x(p2-p0), the area of the parallelogram
*/
static public function dpara(p0:Point, p1:Point, p2:Point):Number
{
var x1:Number = p1.x - p0.x;
var y1:Number = p1.y - p0.y;
var x2:Number = p2.x - p0.x;
var y2:Number = p2.y - p0.y;
return x1 * y2 - x2 * y1;
}
/**
* ddenom/dpara have the property that the square of radius 1 centered
* at p1 intersects the line p0p2 iff |dpara(p0,p1,p2)| <= ddenom(p0,p2)
*/
public static function ddenom(p0:Point, p2:Point):Number
{
var r:Point = dorth_infty(p0, p2);
return r.y * (p2.x - p0.x) - r.x * (p2.y - p0.y);
}
/**
* return 1 if a <= b < c < a, in a cyclic sense (mod n)
*/
private static function cyclic(a:int, b:int, c:int):Boolean
{
if (a <= c)
{
return (a <= b) && (b < c);
}
else
{
return (a <= b) || (b < c);
}
}
}
internal class Sums
{
public var x:Number;
public var y:Number;
public var x2:Number;
public var xy:Number;
public var y2:Number;
}
import flash.geom.Point;
import flash.utils.Proxy;
import flash.utils.flash_proxy;
import flash.errors.IllegalOperationError;
internal class Point3D extends Proxy
{
private var $v:Array;
public function Point3D(x:Number = 0.0, y:Number = 0.0, z:Number = 0.0):void
{
$v = [x, y, z];
}
flash_proxy override function getProperty(name:*):*
{
if(name == 0 || name == "x") return $v[0];
if(name == 1 || name == "y") return $v[1];
if(name == 2 || name == "z") return $v[2];
return undefined;
}
flash_proxy override function hasProperty(name:*):Boolean
{
return flash_proxy.getProperty(name) != undefined;
}
flash_proxy override function setProperty(name:*, value:*):void
{
if(name == 0 || name == "x"){$v[0] = Number(value); return;}
if(name == 1 || name == "y"){$v[1] = Number(value); return;}
if(name == 2 || name == "z"){$v[2] = Number(value); return;}
throw new IllegalOperationError();
}
public function toString():String
{
return "(" + $v[0] + "," + $v[1] + "," + $v[2] + ")";
}
}
/**
* the type of (affine) quadratic forms, represented as symmetric 3x3
* matrices. The value of the quadratic form at a vector (x,y) is v^t
* Q v, where v = (x,y,1)^t.
*/
internal class QuadraticForm extends Proxy
{
private var $m:Array;
public function QuadraticForm():void
{
$m = [];
$m[0] = new Point3D();
$m[1] = new Point3D();
$m[2] = new Point3D();
}
flash_proxy override function getProperty(name:*):*
{
if(name == 0) return $m[0];
if(name == 1) return $m[1];
if(name == 2) return $m[2];
return undefined;
}
flash_proxy override function hasProperty(name:*):Boolean
{
return flash_proxy.getProperty(name) != undefined;
}
flash_proxy override function setProperty(name:*, value:*):void
{
throw new IllegalOperationError();
}
/**
* Apply quadratic form Q to vector w = (w.x,w.y)
*/
public function apply(w:Point):Number
{
var v:Array = [w.x, w.y, 1];
var sum:Number = 0.0;
for(var i:int = 0; i < 3; i++)
{
for(var j:int = 0; j < 3; j++)
{
sum += v[i] * $m[i][j] * v[j];
}
}
return sum;
}
public function clone():QuadraticForm
{
var ret:QuadraticForm = new QuadraticForm();
for(var i:int = 0; i < 3; i++)
{
for(var j:int = 0; j < 3; j++)
{
ret[i][j] = $m[i][j];
}
}
return ret;
}
public function add(m2:QuadraticForm):QuadraticForm
{
for(var i:int = 0; i < 3; i++)
{
for(var j:int = 0; j < 3; j++)
{
$m[i][j] += m2[i][j];
}
}
return this;
}
public function scalar(s:Number):QuadraticForm
{
for(var i:int = 0; i < 3; i++)
{
for(var j:int = 0; j < 3; j++)
{
$m[i][j] *= s;
}
}
return this;
}
public function fromVectorMultiply(v:Point3D):QuadraticForm
{
for(var i:int = 0; i < 3; i++)
{
for(var j:int = 0; j < 3; j++)
{
$m[i][j] = v[i] * v[j];
}
}
return this;
}
public function toString():String
{
return "[" +
$m[0][0] + "," + $m[0][1] + "," + $m[0][2] + "," +
$m[1][0] + "," + $m[1][1] + "," + $m[1][2] + "," +
$m[2][0] + "," + $m[2][1] + "," + $m[2][2] + "]";
}
}