forked from: ボロノイ図
import net.hires.debug.Stats;
ボロノイ図描画
Quasimondo 先生が 2002 年に書いたコードの写経です。
ステージをクリックしてね。何度も何度もクリックしてね。
オリジナル：http://www.quasimondo.com/archives/000110.php
説明：http://aquioux.blog48.fc2.com/blog-entry-654.html
/**
* Copyright yasnis ( http://wonderfl.net/user/yasnis )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/nlgi
*/
// forked from Aquioux's ボロノイ図
package {
import flash.display.BitmapData;
import flash.display.Bitmap;
import flash.display.Graphics;
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
import flash.text.TextFormat;
import flash.geom.Point;
//import net.hires.debug.Stats;
[SWF(width = "465", height = "465", frameRate = "30", backgroundColor = "#FFFFFF")]
/**
* ボロノイ図描画
* Quasimondo 先生が 2002 年に書いたコードの写経です。
* ステージをクリックしてね。何度も何度もクリックしてね。
* オリジナル：http://www.quasimondo.com/archives/000110.php
* 説明：http://aquioux.blog48.fc2.com/blog-entry-654.html
*/
public class Main extends Sprite {
private const STAGE_WIDTH:uint = stage.stageWidth;
private const STAGE_HEIGHT:uint = stage.stageHeight;
private var dots:Array; // Dot の配列
private var sx:Array; // 線開始座標（X座標）
private var sy:Array; // 線開始座標（Y座標）
private var ex:Array; // 線終了座標（X座標）
private var ey:Array; // 線終了座標（Y座標）
private var dotLayer:Sprite; // ドットのコンテナ
private var lineLayer:Sprite; // 線描画用レイヤ
private var bmpd:BitmapData;
private var colorLayer:Bitmap; // 線描画用レイヤ
private var textField:TextField; // "Click STAGE"
public function Main():void {
// 配列初期化
dots = [];
sx = [];
sy = [];
ex = [];
ey = [];
// コンテナ等
bmpd = new BitmapData(stage.stageWidth,stage.stageHeight,true,0x00000000);
addChild(dotLayer = new Sprite());
addChild(lineLayer = new Sprite());
addChildAt(colorLayer = new Bitmap(bmpd),0);
lineLayer.visible = false;
//addChild(new Stats());
// 最初に Dot を3つ配置
for (var i:int = 0; i < 3; i++) {
addDot(Math.random() * STAGE_WIDTH, Math.random() * STAGE_HEIGHT);
}
// イベントリスナー
addEventListener(Event.ENTER_FRAME, enterFrameHandler);
stage.addEventListener(MouseEvent.CLICK, clickHandler);
}
// ENTER_FRAME
private function enterFrameHandler(event:Event):void {
moveDot(); // Dot の移動
setVoronoi(); // ボロノイ境界線の計算
drawVolonoi(); // ボロノイ境界線の描画
//removeEventListener(Event.ENTER_FRAME, enterFrameHandler);
}
// Dot の移動
private function moveDot():void {
var n:uint = dots.length;
for (var i:int = 0; i < n; i++) {
var dot:Dot = dots[i];
dot.update();
}
}
// ボロノイ境界線の計算
private function setVoronoi():void {
var a:Number;
var b:Number;
var a0:Number;
var b0:Number;
var a1:Number;
var b1:Number;
var x:Number;
var y:Number;
var x0:Number;
var y0:Number;
var x1:Number;
var y1:Number;
var n:uint = dots.length;
var m:uint = n + 3;
for (var i:int = 0; i < n; i++) {
x0 = dots[i].x;
y0 = dots[i].y;
var idx1:int = i * m + i + 1;
for (var j:int = i + 1; j < n; j++) {
x1 = dots[j].x;
y1 = dots[j].y;
if (x1 == x0) {
a = 0;
} else if (y1 == y0) {
a = 10000;
} else {
a = -1 / ((y1 - y0) / (x1 - x0));
}
b = (y0 + y1) / 2 - a * (x0 + x1) / 2;
if (a > -1 && a <= 1) {
sx[idx1] = 0;
sy[idx1] = a * sx[idx1] + b;
ex[idx1] = STAGE_WIDTH - 1;
ey[idx1] = a * ex[idx1] + b;
} else {
sy[idx1] = 0;
sx[idx1] = (sy[idx1] - b) / a;
ey[idx1] = STAGE_HEIGHT - 1;
ex[idx1] = (ey[idx1] - b) / a;
}
idx1++;
}
sx[idx1] = 0;
sy[idx1] = 0;
ex[idx1] = STAGE_WIDTH;
ey[idx1] = 0;
idx1++;
sx[idx1] = 0;
sy[idx1] = 0;
ex[idx1] = 0;
ey[idx1] = STAGE_HEIGHT;
idx1++;
sx[idx1] = STAGE_WIDTH;
sy[idx1] = 0;
ex[idx1] = STAGE_WIDTH;
ey[idx1] = STAGE_HEIGHT;
idx1++;
sx[idx1] = 0;
sy[idx1] = STAGE_HEIGHT;
ex[idx1] = STAGE_WIDTH;
ey[idx1] = STAGE_HEIGHT;
}
for (i = 0; i < n; i++) {
x0 = dots[i].x;
y0 = dots[i].y;
for (j = 0; j < m + 1; j++) {
if (j != i) {
if (j > i) {
idx1 = i * m + j;
} else {
idx1 = j * m + i;
}
if (sx[idx1] > -Number.MAX_VALUE) {
a0 = (ey[idx1] - sy[idx1]) / (ex[idx1] - sx[idx1]);
b0 = sy[idx1] - a0 * sx[idx1];
for (var k:int = i + 1; k < m + 1; k++) {
if (k != j) {
var idx2:int = i * m + k;
if (sx[idx2] > -Number.MAX_VALUE) {
a1 = (ey[idx2] - sy[idx2]) / (ex[idx2] - sx[idx2]);
b1 = sy[idx2] - a1 * sx[idx2];
x = -(b1 - b0) / (a1 - a0);
y = a0 * x + b0;
if ((a0 * x0 + b0 - y0) * (a0 * sx[idx2] + b0 - sy[idx2]) < 0) {
sx[idx2] = x;
sy[idx2] = y;
}
if ((a0 * x0 + b0 - y0) * (a0 * ex[idx2] + b0 - ey[idx2]) < 0) {
if (sx[idx2] == x) {
sx[idx2] = -Number.MAX_VALUE;
} else {
ex[idx2] = x;
ey[idx2] = y;
}
}
}
}
}
}
}
}
}
}
// ボロノイ境界線の描画
private function drawVolonoi():void {
lineLayer.graphics.clear();
//lineLayer.graphics.lineStyle(0, 0xffffff,);
lineLayer.graphics.lineStyle(0,0xffffff );
var n:uint = dots.length;
var m:uint = n + 3;
var g:Graphics = lineLayer.graphics;
for (var i:int = 0; i < n; i++) {
var idx:uint = i * m + i + 1;
for (var j:int = i + 1; j < m + 1; j++) {
if (sx[idx] > -Number.MAX_VALUE) {
//g.lineStyle(1,getLineColor(new Point(sx[idx], sy[idx]),new Point(ex[idx], ey[idx])));
g.moveTo(sx[idx], sy[idx]);
g.lineTo(ex[idx], ey[idx]);
}
idx++;
}
}
bmpd.fillRect(bmpd.rect,0xff000000);
bmpd.draw(lineLayer);
for(i = 0;i<dots.length;i++){
//
bmpd.floodFill(dots[i].x,dots[i].y,dots[i].color);
}
}
private function getLineColor(p1:Point,p2:Point):uint {
var dx:Number = 100000;
var c:uint = 0;
for(var i:int = 0;i<dots.length;i++){
var d:Number = getDistance(p1,p2,dots[i]);
if(d<dx){
dx = d;
c = dots[i].color;
}
}
trace(c.toString(16));
return c;
}
private function getDistance(p1:Point, p2:Point, t:Point):Number{
var aa:Point = new Point(p1.x-p1.x,p1.y-p1.y);
var ab:Point = new Point(p1.x-p2.x,p1.y-p2.y);
var ba:Point = new Point(p2.x-p1.x,p2.y-p1.y);
var ca:Point = new Point(t.x-p1.x,t.y-p1.y);
var cb:Point = new Point(t.x-p2.x,t.y-p2.y);
if ( dot(ba,ca) < 0) return ca.length;
if ( dot(ab, cb) < 0 ) return cb.length;
return Math.abs(cross(ba, ca)) / ba.length;
}
/*
double distance_ls_p(P a, P b, P c) {
if ( dot(b-a, c-a) < EPS ) return abs(c-a);
if ( dot(a-b, c-b) < EPS ) return abs(c-b);
return abs(cross(b-a, c-a)) / abs(b-a);
}
*/
public function cross(v1:Point, v2:Point):Number {
return v1.x * v2.y - v2.x * v1.y;
}
public function ccw(v1:Point, v2:Point, v3:Point):Number {
return cross(new Point(v2.x-v1.x,v2.y-v1.y),new Point(v3.x-v2.x,v3.y-v2.y));
}
public function dot(v1:Point, v2:Point):Number {
return v1.x * v2.x + v1.y * v2.y;
}
// マウスイベント
private function clickHandler(e:MouseEvent):void {
if(e.target as Dot){
return;
}
addDot(mouseX, mouseY);
}
// Dot をコンテナ上に追加する
private function addDot(x:Number, y:Number):void {
var dot:Dot = new Dot();
dot.x = x;
dot.y = y;
dots.push(dot);
dotLayer.addChild(dot);
}
}
}
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
class Dot extends Sprite {
private const RADIUS:uint = 5;
private var vx:Number = 0.0; // X軸ベロシティ
private var vy:Number = 0.0; // Y軸ベロシティ
private var sw:Number; // ステージ幅
private var sh:Number; // ステージ高
public var color:uint = Math.random()*0xffffffff;
public function Dot() {
graphics.lineStyle(2,0xff0000);
graphics.beginFill(0xff0000,0.5);
graphics.drawCircle(0, 0, RADIUS);
graphics.endFill();
addEventListener(Event.ADDED_TO_STAGE, addHandler);
buttonMode = true;
addEventListener(MouseEvent.MOUSE_DOWN,mouseDownHandler);
addEventListener(MouseEvent.MOUSE_UP,mouseUpHandler);
}
private function mouseDownHandler(e:MouseEvent):void{
startDrag();
}
private function mouseUpHandler(e:MouseEvent):void{
stopDrag();
}
private function addHandler(event:Event):void {
removeEventListener(Event.ADDED_TO_STAGE, addHandler);
sw = stage.stageWidth;
sh = stage.stageHeight;
if (Math.random() < 0.5) {
vx *= -1;
}
if (Math.random() < 0.5) {
vy *= -1;
}
}
// 移動
public function update():void {
x += vx;
y += vy;
if (x < RADIUS) {
x = RADIUS;
vx *= -1;
}
if (x > sw - RADIUS) {
x = sw - RADIUS;
vx *= -1;
}
if (y < RADIUS) {
y = RADIUS;
vy *= -1;
}
if (y > sh - RADIUS) {
y = sh - RADIUS;
vy *= -1;
}
}
}
import flash.geom.Point;
class GeomUtils {
public static function cross(v1:Point, v2:Point):Number {
return v1.x * v2.y - v2.x * v1.y;
}
public static function ccw(v1:Point, v2:Point, v3:Point):Number {
return cross(new Point(v2.x-v1.x,v2.y-v1.y),new Point(v3.x-v2.x,v3.y-v2.y));
}
public static function dot(v1:Point, v2:Point):Number {
return v1.x * v2.x + v1.y * v2.y;
}
}
class LineSegment {
private var v1:Point;
private var v2:Point;
public function LineSegment(v1:Point,v2:Point){
this.v1 = v1;
this.v2 = v2;
}
public function toLine():Line {
return Line.fromPoints(v1,v2);
}
//直線との交差チェック
public function intersectsToLine(line:Line):Boolean {
var t1:Number = line.a * v1.x + line.b * v1.y + line.c; // 端点1の座標を直線の式に代入
var t2:Number = line.a * v2.x + line.b * v2.y + line.c; // 端点2の座標を直線の式に代入
return t1 * t2 <= 0; // 不等式の判定
}
//セグメントとの交差チェック
public function intersectsToSegment(seg:LineSegment):Boolean {
return intersectsToLine(seg.toLine()) && seg.intersectsToLine(toLine());
}
//
public function getIntersectionPointByLine(line:Line):Point {
if (!intersectsToLine(line)) {
return null; // 交差しない場合はnullを返す
}
return line.getIntersectionPoint(toLine());
}
//
public function getIntersectionPointBySeg(seg:LineSegment):Point {
if (!intersectsToSegment(seg)) {
return null; // 交差しない場合はnullを返す
}
return seg.toLine().getIntersectionPoint(toLine());
}
// sが自線分の「両側」にあるかどうかを調べる
private function bothSides(seg:LineSegment):Boolean {
var ccw1:Number = GeomUtils.ccw(v1, seg.v1, v2);
var ccw2:Number = GeomUtils.ccw(v1, seg.v2, v2);
if (ccw1 == 0 && ccw2 == 0) { // sと自線分が一直線上にある場合
// sのいずれか1つの端点が自線分を内分していれば，sは自線分と共有部分を持つので
// trueを返す
return isInternal(seg.v1.x, seg.v1.y) || isInternal(seg.v2.x, seg.v2.y);
} else { // それ以外の場合
// CCW値の符号が異なる場合にtrueを返す
return ccw1 * ccw2 <= 0;
}
}
// (x, y)が自線分を内分しているかどうかを調べる
private function isInternal(x:Number,y:Number):Boolean {
// (x, y)から端点に向かうベクトルの内積がゼロ以下であれば内分と見なす
return GeomUtils.dot(new Point(v1.x - x, v1.y - y), new Point(v2.x - x, v2.y - y)) <= 0;
}
}
class Line {
public var a:Number;
public var b:Number;
public var c:Number;
static public function fromPoints(v1:Point,v2:Point):Line{
var dx:Number = v2.x - v1.x;
var dy:Number = v2.y - v1.y;
return new Line(dy, -dx, dx * v1.y - dy * v1.x);
}
public function Line(a:Number, b:Number, c:Number) {
this.a = a;
this.b = b;
this.c = c;
}
public function getIntersectionPoint(line:Line):Point {
var d:Number = a * line.b - line.a * b;
if (d == 0) {
return null; // 直線が平行の場合はnullを返す
}
var x:Number = (b * line.c - line.b * c) / d;
var y:Number = (line.a * c - a * line.c) / d;
return new Point(x, y);
}
}