Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Convex Separator for Box2D Flash
- *
- * This class has been written by Antoan Angelov.
- * It is designed to work with Erin Catto's Box2D physics library.
- *
- * Everybody can use this software for any purpose, under two restrictions:
- * 1. You cannot claim that you wrote this software.
- * 2. You can not remove or alter this notice.
- *
- */
- package Box2DSeparator{
- import Box2D.Collision.Shapes.b2PolygonShape;
- import Box2D.Common.Math.b2Vec2;
- import Box2D.Dynamics.b2Body;
- import Box2D.Dynamics.b2FixtureDef;
- public class b2Separator;
- {
- public function b2Separator() {
- }
- /**
- * Separates a non-convex polygon into convex polygons and adds them as fixtures to the <code>body</code> parameter.<br/>
- * There are some rules you should follow (otherwise you might get unexpected results) :
- * <ul>
- * <li>This class is specifically for non-convex polygons. If you want to create a convex polygon, you don't need to use this class - Box2D's <code>b2PolygonShape</code> class allows you to create convex shapes with the <code>setAsArray()</code>/<code>setAsVector()</code> method.</li>
- * <li>The vertices must be in clockwise order.</li>
- * <li>No three neighbouring points should lie on the same line segment.</li>
- * <li>There must be no overlapping segments and no "holes".</li>
- * </ul> <p/>
- * @param body The b2Body, in which the new fixtures will be stored.
- * @param fixtureDef A b2FixtureDef, containing all the properties (friction, density, etc.) which the new fixtures will inherit.
- * @param verticesVec The vertices of the non-convex polygon, in clockwise order.
- * @param scale <code>[optional]</code> The scale which you use to draw shapes in Box2D. The bigger the scale, the better the precision. The default value is 30.
- * @see b2PolygonShape
- * @see b2PolygonShape.SetAsArray()
- * @see b2PolygonShape.SetAsVector()
- * @see b2Fixture
- * */
- public function Separate(body:b2Body,fixtureDef:b2FixtureDef,verticesVec:Vector.<b2Vec2>,scale:Number=30):void {
- var i:int,n:int=verticesVec.length,j:int,m:int;
- var vec:Vector.<b2Vec2>=new Vector.<b2Vec2> ,figsVec:Array;
- var polyShape:b2PolygonShape;
- for (i=0; i<n; i++) {
- vec.push(new b2Vec2(verticesVec[i].x*scale,verticesVec[i].y*scale));
- }
- figsVec=calcShapes(vec);
- n=figsVec.length;
- for (i=0; i<n; i++) {
- verticesVec=new Vector.<b2Vec2> ;
- vec=figsVec[i];
- m=vec.length;
- for (j=0; j<m; j++) {
- verticesVec.push(new b2Vec2(vec[j].x/scale,vec[j].y/scale));
- }
- polyShape=new b2PolygonShape ;
- polyShape.SetAsVector(verticesVec);
- fixtureDef.shape=polyShape;
- body.CreateFixture(fixtureDef);
- }
- }
- /**
- * Checks whether the vertices in <code>verticesVec</code> can be properly distributed into the new fixtures (more specifically, it makes sure there are no overlapping segments and the vertices are in clockwise order).
- * It is recommended that you use this method for debugging only, because it may cost more CPU usage.
- * <p/>
- * @param verticesVec The vertices to be validated.
- * @return An integer which can have the following values:
- * <ul>
- * <li>0 if the vertices can be properly processed.</li>
- * <li>1 If there are overlapping lines.</li>
- * <li>2 if the points are <b>not</b> in clockwise order.</li>
- * <li>3 if there are overlapping lines <b>and</b> the points are <b>not</b> in clockwise order.</li>
- * </ul>
- * */
- public function Validate(verticesVec:Vector.<b2Vec2>):int {
- var i:int,n:int=verticesVec.length,j:int,j2:int,i2:int,i3:int,d:Number,ret:int=0;
- var fl:Boolean,fl2:Boolean=false;
- for (i=0; i<n; i++) {
- i2=(i<n-1)?i+1:0;
- i3=(i>0)?i-1:n-1;
- fl=false;
- for (j=0; j<n; j++) {
- if (((j!=i)&&j!=i2)) {
- if (! fl) {
- d=det(verticesVec[i].x,verticesVec[i].y,verticesVec[i2].x,verticesVec[i2].y,verticesVec[j].x,verticesVec[j].y);
- if ((d>0)) {
- fl=true;
- }
- }
- if ((j!=i3)) {
- j2=(j<n-1)?j+1:0;
- if (hitSegment(verticesVec[i].x,verticesVec[i].y,verticesVec[i2].x,verticesVec[i2].y,verticesVec[j].x,verticesVec[j].y,verticesVec[j2].x,verticesVec[j2].y)) {
- ret=1;
- }
- }
- }
- }
- if (! fl) {
- fl2=true;
- }
- }
- if (fl2) {
- if ((ret==1)) {
- ret=3;
- }
- else {
- ret=2;
- }
- }
- return ret;
- }
- private function calcShapes(verticesVec:Vector.<b2Vec2>):Array {
- var vec:Vector.<b2Vec2>;
- var i:int,n:int,j:int;
- var d:Number,t:Number,dx:Number,dy:Number,minLen:Number;
- var i1:int,i2:int,i3:int,p1:b2Vec2,p2:b2Vec2,p3:b2Vec2;
- var j1:int,j2:int,v1:b2Vec2,v2:b2Vec2,k:int,h:int;
- var vec1:Vector.<b2Vec2>,vec2:Vector.<b2Vec2>;
- var v:b2Vec2,hitV:b2Vec2;
- var isConvex:Boolean;
- var figsVec:Array=[],queue:Array=[];
- queue.push(verticesVec);
- while (queue.length) {
- vec=queue[0];
- n=vec.length;
- isConvex=true;
- for (i=0; i<n; i++) {
- i1=i;
- i2=(i<n-1)?i+1:i+1-n;
- i3=(i<n-2)?i+2:i+2-n;
- p1=vec[i1];
- p2=vec[i2];
- p3=vec[i3];
- d=det(p1.x,p1.y,p2.x,p2.y,p3.x,p3.y);
- if ((d<0)) {
- isConvex=false;
- minLen=Number.MAX_VALUE;
- for (j=0; j<n; j++) {
- if (((j!=i1)&&j!=i2)) {
- j1=j;
- j2=(j<n-1)?j+1:0;
- v1=vec[j1];
- v2=vec[j2];
- v=hitRay(p1.x,p1.y,p2.x,p2.y,v1.x,v1.y,v2.x,v2.y);
- if (v) {
- dx=p2.x-v.x;
- dy=p2.y-v.y;
- t=dx*dx+dy*dy;
- if ((t<minLen)) {
- h=j1;
- k=j2;
- hitV=v;
- minLen=t;
- }
- }
- }
- }
- if ((minLen==Number.MAX_VALUE)) {
- err();
- }
- vec1=new Vector.<b2Vec2> ;
- vec2=new Vector.<b2Vec2> ;
- j1=h;
- j2=k;
- v1=vec[j1];
- v2=vec[j2];
- if (! pointsMatch(hitV.x,hitV.y,v2.x,v2.y)) {
- vec1.push(hitV);
- }
- if (! pointsMatch(hitV.x,hitV.y,v1.x,v1.y)) {
- vec2.push(hitV);
- }
- h=-1;
- k=i1;
- while (true) {
- if ((k!=j2)) {
- vec1.push(vec[k]);
- }
- else {
- if (((h<0)||h>=n)) {
- err();
- }
- if (! this.isOnSegment(v2.x,v2.y,vec[h].x,vec[h].y,p1.x,p1.y)) {
- vec1.push(vec[k]);
- }
- break;
- }
- h=k;
- if (((k-1)<0)) {
- k=n-1;
- }
- else {
- k--;
- }
- }
- vec1=vec1.reverse();
- h=-1;
- k=i2;
- while (true) {
- if ((k!=j1)) {
- vec2.push(vec[k]);
- }
- else {
- if (((h<0)||h>=n)) {
- err();
- }
- if (((k==j1)&&! this.isOnSegment(v1.x,v1.y,vec[h].x,vec[h].y,p2.x,p2.y))) {
- vec2.push(vec[k]);
- }
- break;
- }
- h=k;
- if (((k+1)>n-1)) {
- k=0;
- }
- else {
- k++;
- }
- }
- queue.push(vec1,vec2);
- queue.shift();
- break;
- }
- }
- if (isConvex) {
- figsVec.push(queue.shift());
- }
- }
- return figsVec;
- }
- private function hitRay(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number,x4:Number,y4:Number):b2Vec2 {
- var t1:Number=x3-x1,t2:Number=y3-y1,t3:Number=x2-x1,t4:Number=y2-y1,t5:Number=x4-x3,t6:Number=y4-y3,t7:Number=t4*t5-t3*t6,a:Number;
- a=(((t5*t2)-t6*t1)/t7);
- var px:Number=x1+a*t3,py:Number=y1+a*t4;
- var b1:Boolean=isOnSegment(x2,y2,x1,y1,px,py);
- var b2:Boolean=isOnSegment(px,py,x3,y3,x4,y4);
- if ((b1&&b2)) {
- return new b2Vec2(px,py);
- }
- return null;
- }
- private function hitSegment(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number,x4:Number,y4:Number):b2Vec2 {
- var t1:Number=x3-x1,t2:Number=y3-y1,t3:Number=x2-x1,t4:Number=y2-y1,t5:Number=x4-x3,t6:Number=y4-y3,t7:Number=t4*t5-t3*t6,a:Number;
- a=(((t5*t2)-t6*t1)/t7);
- var px:Number=x1+a*t3,py:Number=y1+a*t4;
- var b1:Boolean=isOnSegment(px,py,x1,y1,x2,y2);
- var b2:Boolean=isOnSegment(px,py,x3,y3,x4,y4);
- if ((b1&&b2)) {
- return new b2Vec2(px,py);
- }
- return null;
- }
- private function isOnSegment(px:Number,py:Number,x1:Number,y1:Number,x2:Number,y2:Number):Boolean {
- var b1:Boolean=((((x1+0.1)>=px)&&px>=x2-0.1)||(((x1-0.1)<=px)&&px<=x2+0.1));
- var b2:Boolean=((((y1+0.1)>=py)&&py>=y2-0.1)||(((y1-0.1)<=py)&&py<=y2+0.1));
- return ((b1&&b2)&&isOnLine(px,py,x1,y1,x2,y2));
- }
- private function pointsMatch(x1:Number,y1:Number,x2:Number,y2:Number):Boolean {
- var dx:Number=(x2>=x1)?x2-x1:x1-x2,dy:Number=(y2>=y1)?y2-y1:y1-y2;
- return ((dx<0.1)&&dy<0.1);
- }
- private function isOnLine(px:Number,py:Number,x1:Number,y1:Number,x2:Number,y2:Number):Boolean {
- if ((((x2-x1)>0.1)||x1-x2>0.1)) {
- var a:Number=(y2-y1)/(x2-x1),possibleY:Number=a*(px-x1)+y1,diff:Number=(possibleY>py)?possibleY-py:py-possibleY;
- return (diff<0.1);
- }
- return (((px-x1)<0.1)||x1-px<0.1);
- }
- private function det(x1:Number,y1:Number,x2:Number,y2:Number,x3:Number,y3:Number):Number {
- return x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1;
- }
- private function err():void {
- throw new Error("A problem has occurred. Use the Validate() method to see where the problem is.");
- }
- }
- }
Add Comment
Please, Sign In to add comment