Efficient Line Intersection Detection
Algebra based line intersection collision. This is the proof of the modified version I use to do collision detection between polygons.
For many lines this can be easily optimized to check for bounding box collision first, making collision detection between any 2 polygons (of almost any complexity) very fast. Everything is calculated using addition, subtraction, and less-than/greater-than checks, making it very quick.
/**
* Copyright Highly ( http://wonderfl.net/user/Highly )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/6ry8
*/
package {
import flash.display.Sprite;
public class FlashTest extends Sprite {
public function FlashTest() {
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.events.Event;
import flash.geom.Point;
import flash.text.*;
import flashx.textLayout.elements.InlineGraphicElement;
var cSize:int = 5;
var smod:int = 125;
var sw:int = stage.stageWidth;
var sh:int = stage.stageHeight;
var ln:Sprite = new Sprite();
addChild(ln);
var form:TextFormat = new TextFormat();
form.size = 10.5;
var omod:int = 20;
var out1:TextField = new TextField();
out1.defaultTextFormat=form;
out1.width = sw - (omod * 2);
out1.height = sh - (omod * 2);
out1.x = omod;
out1.y = omod;
out1.selectable = false;
addChild(out1);
var out2:TextField=new TextField();
out2.width=120;
out2.height=20;
out2.selectable=false;
addChild(out2);
var output:String="";
var s10:Sprite = new Sprite();
var s10b:Boolean = false;
s10.graphics.beginFill(0xE0AFE9);
s10.graphics.lineStyle(1,0x000000);
s10.graphics.drawCircle(0,0,cSize);
s10.graphics.endFill();
s10.x = smod;
s10.y = smod;
s10.addEventListener(MouseEvent.MOUSE_DOWN, mDown);
s10.addEventListener(MouseEvent.MOUSE_UP, mUp);
addChild(s10);
var s11:Sprite = new Sprite();
var s11b:Boolean = false;
s11.graphics.beginFill(0xAFBDE9);
s11.graphics.lineStyle(1,0x000000);
s11.graphics.drawCircle(0,0,cSize);
s11.graphics.endFill();
s11.x = sw - smod;
s11.y = sh - smod;
s11.addEventListener(MouseEvent.MOUSE_DOWN, mDown);
s11.addEventListener(MouseEvent.MOUSE_UP, mUp);
addChild(s11);
var s20:Sprite = new Sprite();
var s20b:Boolean = false;
s20.graphics.beginFill(0x4CE759);
s20.graphics.lineStyle(1,0x000000);
s20.graphics.drawCircle(0,0,cSize);
s20.graphics.endFill();
s20.x = sw - smod;
s20.y = smod;
s20.addEventListener(MouseEvent.MOUSE_DOWN, mDown);
s20.addEventListener(MouseEvent.MOUSE_UP, mUp);
addChild(s20);
var s21:Sprite = new Sprite();
var s21b:Boolean = false;
s21.graphics.beginFill(0xFAE237);
s21.graphics.lineStyle(1,0x000000);
s21.graphics.drawCircle(0,0,cSize);
s21.graphics.endFill();
s21.x = smod;
s21.y = sh - smod;
s21.addEventListener(MouseEvent.MOUSE_DOWN, mDown);
s21.addEventListener(MouseEvent.MOUSE_UP, mUp);
addChild(s21);
var L1:Array = new Array(new Point(s10.x,s10.y),new Point(s11.x,s11.y));
var L2:Array = new Array(new Point(s20.x,s20.y),new Point(s21.x,s21.y));
function step(e:Event):void {
//Clear the line sprite
ln.graphics.clear();
//clear output
output="";
//Set individual sprites to be dragged when their drag boolean is true;
var tmx:int=mouseX;
var tmy:int=mouseY;
var mMax:int = 50;
if(tmx>sw-mMax){
tmx = sw-mMax;
}
if(tmx<mMax){
tmx=mMax;
}
if(tmy>sh-mMax){
tmy=sh-mMax;
}
if(tmy<mMax){
tmy=mMax;
}
if (s10b) {
s10.x = tmx;
s10.y = tmy;
}
if (s11b) {
s11.x = tmx;
s11.y = tmy;
}
if (s20b) {
s20.x = tmx;
s20.y = tmy;
}
if (s21b) {
s21.x = tmx;
s21.y = tmy;
}
//Set line segment points to the coords of the sprites
L1[0].x = s10.x;
L1[0].y = s10.y;
L1[1].x = s11.x;
L1[1].y = s11.y;
L2[0].x = s20.x;
L2[0].y = s20.y;
L2[1].x = s21.x;
L2[1].y = s21.y;
//draw the lines
ln.graphics.lineStyle(1,0x000000,0.4);
ln.graphics.moveTo(L1[0].x,L1[0].y);
ln.graphics.lineTo(L1[1].x,L1[1].y);
ln.graphics.moveTo(L2[0].x,L2[0].y);
ln.graphics.lineTo(L2[1].x,L2[1].y);
var intersect:Object=new Object();
intersect = inBoundsIntersect(L1,L2);
output+="COLLISION: ";
if (intersect!=null) {
output += "True";
var Imod:int = 5;
ln.graphics.lineStyle(1,0xE02727);
ln.graphics.drawCircle(intersect.x,intersect.y,Imod);
var out2mod:int=5;
out2.visible=true;
out2.x=intersect.x+out2mod;
out2.y=intersect.y+out2mod;
out2.text = "("+decR(intersect.x,2)+", "+decR(intersect.y,2)+")";
} else {
out2.visible=false;
output+= "False";
}
output+="\n\nL1[0] = ("+L1[0].x+", "+L1[0].y+")\nL1[1] = ("+L1[1].x+", "+L1[1].y+")\n\nL2[0] = ("+L2[0].x+", "+L2[0].y+")\nL2[1] = ("+L2[1].x+", "+L2[1].y+")";
//set textfield to output string
out1.text=output;
}
function inBoundsIntersect(L1:Array,L2:Array):Point {
var m1:Number=(L1[1].y-L1[0].y)/(L1[1].x-L1[0].x);
var b1:Number = -1 * (m1 * L1[0].x) + L1[0].y;
var m2:Number=(L2[1].y-L2[0].y)/(L2[1].x-L2[0].x);
var b2:Number = -1 * (m2 * L2[0].x) + L2[0].y;
var I:Point = new Point((b2-b1)/(m1-m2),(m1*((b2-b1)/(m1-m2)))+b1);
var L1lb:Number,L1rb:Number,L1db:Number,L1ub:Number,L2lb:Number,L2rb:Number,L2db:Number,L2ub:Number;
var L1b:Boolean,L2b:Boolean;
if (L1[0].x < L1[1].x) {
L1lb = L1[0].x;
L1rb = L1[1].x;
} else {
L1lb = L1[1].x;
L1rb = L1[0].x;
}
if (L1[0].y < L1[1].y) {
L1db = L1[0].y;
L1ub = L1[1].y;
} else {
L1db = L1[1].y;
L1ub = L1[0].y;
}
if (L2[0].x < L2[1].x) {
L2lb = L2[0].x;
L2rb = L2[1].x;
} else {
L2lb = L2[1].x;
L2rb = L2[0].x;
}
if (L2[0].y < L2[1].y) {
L2db = L2[0].y;
L2ub = L2[1].y;
} else {
L2db = L2[1].y;
L2ub = L2[0].y;
}
if ((I.x>L1lb&&I.x<L1rb)&&(I.y>L1db&&I.y<L1ub)) {
L1b = true;
} else {
L1b = false;
}
if ((I.x>L2lb&&I.x<L2rb)&&(I.y>L2db&&I.y<L2ub)) {
L2b = true;
} else {
L2b = false;
}
if (L1b&&L2b) {
return I;
} else {
return null;
}
}
function decR(n:Number, dec:int):Number{
var p:Number=Math.pow(10,dec);
var temp:Number=Math.round(n*p);
return temp/p;
}
function mDown(e:MouseEvent):void {
if (e.currentTarget == s10) {
s10b = true;
}
if (e.currentTarget == s11) {
s11b = true;
}
if (e.currentTarget == s20) {
s20b = true;
}
if (e.currentTarget == s21) {
s21b = true;
}
}
function mUp(e:MouseEvent):void {
s10b = false;
s11b = false;
s20b = false;
s21b = false;
}
stage.addEventListener(Event.ENTER_FRAME,step);
}
}
}