distanceStars
複雑な線分集合における最短距離。
/**
* Copyright medadotter ( http://wonderfl.net/user/medadotter )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/v83S
*/
package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
/**
* ...
* @author DT
*/
[SWF(width="465",height="465")]
public class distanceStars extends Sprite
{
private var counter:int = 0;
public function distanceStars()
{
//stage.addEventListener(MouseEvent.CLICK, testStar);
addEventListener(Event.ENTER_FRAME, testStarsDistance);
}
private function turnFlag(event:MouseEvent):void {
}
private function testStarsDistance(event:Event):void {
var star1:Star = new Star(new Point(stage.stageWidth / 2, stage.stageHeight / 2), 2.5 * counter, 150);
var star2:Star = new Star(new Point(mouseX, mouseY), 0, 30);
++counter;
graphics.clear();
Star.intersect(star1, star2) ? graphics.lineStyle(0, 0xff0000) : graphics.lineStyle(0);
star1.draw(graphics);
star2.draw(graphics);
graphics.lineStyle(0, 0x0000ff, 0.25);
var dPoint1:Point = star1.points[0];
var distVekt1:Point = star2.segments[0].distanceVektor(star1.points[0]);
var dPoint2:Point = star2.points[0];
var distVekt2:Point = star1.segments[0].distanceVektor(star2.points[0]);
for (var i:int = 0; i < 5; i++) {
var point1:Point = star1.points[i];
var point2:Point = star2.points[i];
for (var j:int = 0; j < 5; j++) {
var segment1:Segment = star1.segments[j];
var segment2:Segment = star2.segments[j];
var dVekt1:Point = segment2.distanceVektor(point1);
var dVekt2:Point = segment1.distanceVektor(point2);
var dSeg1:Segment = new Segment(point1, new Point(point1.x + dVekt1.x, point1.y + dVekt1.y));
var dSeg2:Segment = new Segment(point2, new Point(point2.x + dVekt2.x, point2.y + dVekt2.y));
if (distVekt1.normSQ > dVekt1.normSQ) {
dPoint1 = point1;
distVekt1 = dVekt1;
}
if (distVekt2.normSQ > dVekt2.normSQ) {
dPoint2 = point2;
distVekt2 = dVekt2;
}
dSeg1.draw(graphics);
dSeg2.draw(graphics);
}
}
graphics.lineStyle(3, 0x000000);
if (distVekt1.normSQ < distVekt2.normSQ) {
var distSeg1:Segment = new Segment(dPoint1, new Point(dPoint1.x + distVekt1.x, dPoint1.y + distVekt1.y));
distSeg1.draw(graphics);
}else {
var distSeg2:Segment = new Segment(dPoint2, new Point(dPoint2.x + distVekt2.x, dPoint2.y + distVekt2.y));
distSeg2.draw(graphics);
}
//trace(distVekt1.norm - distVekt2.norm);
}
private function testPointSegmentDistance(event:Event):void {
var mouse:Point = new Point(mouseX, mouseY);
var begin:Point = new Point(stage.stageWidth / 2 - 100, stage.stageHeight / 2 - 50);
var end:Point = new Point(stage.stageWidth / 2 + 100, stage.stageHeight / 2 + 50);
var segment:Segment = new Segment(begin, end);
var dVekt:Point = segment.distanceVektor(mouse);
var dSegment:Segment = new Segment(mouse, new Point(mouse.x + dVekt.x, mouse.y + dVekt.y));
graphics.clear();
graphics.lineStyle(0);
mouse.draw(graphics);
segment.draw(graphics);
graphics.lineStyle(0, 0xff0000);
dSegment.draw(graphics);
trace(dVekt.norm - segment.distance(mouse));
}
private function testStarIntersect(event:Event):void {
var star1:Star = new Star(new Point(stage.stageWidth / 2 - 30, stage.stageHeight / 2), 2.5 * counter, 40);
var star2:Star = new Star(new Point(stage.stageWidth / 2 + 30, stage.stageHeight / 2), 0, 40);
++counter;
trace( Star.intersect(star1, star2) );
graphics.clear();
Star.intersect(star1, star2) ? graphics.lineStyle(0, 0xff0000) : graphics.lineStyle(0);
star1.draw(graphics);
star2.draw(graphics);
}
private function testIntersect(event:MouseEvent):void {
var seg1:Segment = makeSegment();
var seg2:Segment = makeSegment();
graphics.clear();
if (Segment.intersect(seg1, seg2)) {
graphics.lineStyle(0, 0xff0000);
}
else {
graphics.lineStyle(0);
}
seg1.draw(graphics);
seg2.draw(graphics);
}
private function makeSegment():Segment {
var begin:Point = new Point(Math.random() * stage.stageWidth,
Math.random() * stage.stageHeight);
var end:Point = new Point(Math.random() * stage.stageWidth,
Math.random() * stage.stageHeight);
var segment:Segment = new Segment(begin, end);
return segment;
}
}
}
import flash.display.Graphics;
class Point
{
private var _x:Number;
private var _y:Number;
public function Point(x:Number = 0, y:Number = 0)
{
this.x = x;
this.y = y;
}
/**
* ccw:counter clockwise 反時計回り（ただしX軸からY軸への方向を反時計回りのデフォルトとしている）。
* 三点が同一直線上にない場合：
* 反時計回り：+1
* 時計回り ：-1
* 三点が同一直線上にある場合：
* aがbとcの間にあれば：-1
* bがcとaの間にあれば：+1
* cがaとbの間にあれば：0
* 参考：sedgwickの本。
*/
static public function ccwSed(a:Point, b:Point, c:Point):int {
var ab:Point = new Point(b.x - a.x, b.y - a.y);
var ac:Point = new Point(c.x - a.x, c.y - a.y);
//傾きの比較ないしは外積。
if (ab.x * ac.y > ab.y * ac.x) return +1;
if (ab.x * ac.y < ab.y * ac.x) return -1;
//以下、三点は同一直線上にある。
if ((ab.x * ac.x < 0) || (ab.y * ac.y < 0)) return -1;//abとacは逆方向。
if ((ab.x * ab.x + ab.y * ab.y) < (ac.x * ac.x + ac.y * ac.y)) return -1;//abとacが同方向でabよりacの方が短い。
return 0;
}
/**
* 上記のccwSedを幾何演算で可読的に書き直したもの。
* 参考：http://www.prefield.com/algorithm/geometry/ccw.html
*/
static public function ccw(a:Point, b:Point, c:Point):int {
var ab:Point = new Point(b.x - a.x, b.y - a.y);
var ac:Point = new Point(c.x - a.x, c.y - a.y);
//外積。crossをキャッシュするのは僅かな効率のために可読性を犠牲にする。
if (cross(ab,ac) > 0) return +1;
if (cross(ab,ac) < 0) return -1;
//以下、三点は同一直線上にある。
if (dot(ab,ac) < 0) return -1;//abとacは逆方向。
if (ab.normSQ < ac.normSQ) return -1;//abとacが同方向でabよりacの方が短い。
return 0;
}
static public function dot(lhs:Point, rhs:Point):Number {
return lhs.x * rhs.x + lhs.y * rhs.y;
}
static public function cross(lhs:Point, rhs:Point):Number {
return lhs.x * rhs.y - lhs.y * rhs.x;
}
public function get normSQ():Number {
return x * x + y * y;
}
public function get norm():Number {
return Math.sqrt(normSQ);
}
public function draw(graphics:Graphics):void {
graphics.drawCircle(x, y, 1);
}
public function get x():Number {
return _x;
}
public function set x(value:Number):void {
_x = value;
}
public function get y():Number {
return _y;
}
public function set y(value:Number):void {
_y = value;
}
}
class Segment
{
private var _begin:Point;
private var _end:Point;
public function Segment(begin:Point, end:Point)
{
this.begin = begin;
this.end = end;
}
public function draw(graphics:Graphics):void {
graphics.drawCircle(begin.x, begin.y, 4);
graphics.moveTo(begin.x, begin.y);
graphics.lineTo(end.x, end.y);
}
/**
* 二線分のそれぞれに対して、一方の線分の両端点がもう一方の線分の異なる側にあれば（Point.ccwによって判定）両線文は交差する。
* @param seg1
* @param seg2
* @return Boolean 交差していればtrue、していなければfalse
*/
static public function intersect(seg1:Segment, seg2:Segment):Boolean {
return ((Point.ccw(seg1.begin, seg1.end, seg2.begin)
*Point.ccw(seg1.begin, seg1.end, seg2.end)) <= 0)
&& ((Point.ccw(seg2.begin, seg2.end, seg1.begin)
*Point.ccw(seg2.begin, seg2.end, seg1.end)) <= 0);
}
public function distanceVektor(point:Point):Point {
var AB:Point = new Point(end.x - begin.x,end.y - begin.y);
var CA:Point = new Point(begin.x - point.x, begin.y - point.y);
var CB:Point = new Point(end.x - point.x, end.y -point.y);
if (Point.dot(AB, CA) > 0) return CA;
if (Point.dot(AB, CB) < 0) return CB;
var project:Number = -Point.dot(AB, CA) / AB.normSQ;
var CH:Point = new Point(CA.x + project * AB.x, CA.y + project * AB.y);
return CH;
}
public function distance(point:Point):Number {
var AB:Point = new Point(end.x - begin.x,end.y - begin.y);
var CA:Point = new Point(begin.x - point.x, begin.y - point.y);
var CB:Point = new Point(end.x - point.x, end.y -point.y);
if (Point.dot(AB, CA) > 0) return CA.norm;
if (Point.dot(AB, CB) < 0) return CB.norm;
return Math.abs(Point.cross(AB,CA)/AB.norm);
}
public function get begin():Point {
return _begin;
}
public function set begin(value:Point):void {
_begin = value;
}
public function get end():Point {
return _end;
}
public function set end(value:Point):void {
_end = value;
}
}
class Star {
private var _center:Point;
private var _points:Vector.<Point> = new Vector.<Point>();
private var _segments:Vector.<Segment> = new Vector.<Segment>();
public function Star(center:Point, degree:int, radius:Number):void {
this.center = center;
makePoints(degree, radius);
makeSegments();
}
private function makeSegments():void {
for (var i:int = 0; i < 5; i++) {
var segment:Segment = new Segment(points[i], points[(i + 2) % 5]);
segments.push(segment);
}
}
public function draw(graphics:Graphics):void {
//drawPoints(graphics);
drawSegments(graphics);
}
static public function intersect(star1:Star, star2:Star):Boolean {
for (var i:int = 0; i < 5; i++) {
for (var j:int = i; j < 5; j++) {
if ( Segment.intersect(star1.segments[i], star2.segments[j]) ) return true;
}
}
return false;
}
private function makePoints(degree:int, radius:Number):void {
for (var i:int = 0; i < 5; i++) {
var angle:Number = (degree + 90 + 72 * i) / 180 * Math.PI;
var point:Point = new Point(center.x + radius * Math.cos(angle),
center.y + radius * Math.sin(angle));
points.push(point);
}
}
private function drawPoints(graphics:Graphics):void {
for each (var point:Point in points) {
point.draw(graphics);
}
}
private function drawSegments(graphics:Graphics):void {
for each (var segment:Segment in segments) {
segment.draw(graphics);
}
}
public function get points():Vector.<Point> {
return _points;
}
public function set points(value:Vector.<Point>):void {
_points = value;
}
public function get segments():Vector.<Segment> {
return _segments;
}
public function set segments(value:Vector.<Segment>):void {
_segments = value;
}
public function get center():Point {
return _center;
}
public function set center(value:Point):void {
_center = value;
}
}