AS3: Random Point on Irregular Shape


I have a MovieClip holding an irregular shape such as this one:

enter image description here

I need to generate a random point on this shape.

I can use brute force by generating points within the bounding box and then hitTesting to see if they reside on the irregular shape. However, I'm sure there's a more efficient way to tackle this problem.

What is the most efficient way to generate a random point on an irregular shape?


Answers:


You mentioned hitTest, but I assume you meant hitTestPoint().

If so, a function go get the random points you mention, would look a bit like this:

function getRandomPointsInClip(target:MovieClip,numPoints:int):Vector.<Point>{
    var points:Vector.<Point> = new Vector.<Point>(numPoints,true);
    var width:Number = target.width,height:Number = target.height;
    for(var i:int =  0; i < numPoints ; i++){
        var point:Point = new Point(target.x+Math.random() * width,target.y+Math.random() * height);
        if(target.hitTestPoint(point.x,point.y,true)) points[i] = point;//is the random coord inside ?
        else i = i-1;//nope, go back one step - > retry above until it is inside
    }
    return points;
}

The other I hinted at in my comment involves looping through non transparent pixels in a bitmap data of your object. This method would insure you don't have many duplicates, as opposed to the previous method, but it also means, you have less control over the number of points created and there's extra memory used for creating the bitmap. Still, for documentation purposes, here is the function:

function getGridPointsInClip(target:MovieClip,res:int,offset:Number = 3):Vector.<Point>{
    var points:Vector.<Point> = new Vector.<Point>();
    var x:int,y:int,alpha:int,w:int = int(target.width),h:int = int(target.height);
    var bmd:BitmapData = new BitmapData(w,h,true,0x00FFFFFF);bmd.draw(target);
    var pixels:Vector.<uint> = bmd.getVector(bmd.rect),numPixels:int = w*h;
    for(var i:int = 0; i < numPixels; i+=res) {
        x = i%bmd.width;
        y = int(i/bmd.width);
        alpha = pixels[i] >>> 24;
        if(alpha > 0) points.push(new Point(x+random(-offset,offset),y+random(-offset,offset)));
    }
    return points;
}
function random(from:Number,to:Number):Number {
    if (from >= to) return from;
    var diff:Number = to - from;
    return (Math.random()*diff) + from;
}

And here'a very basic test:

var pts:Vector.<Point> = getRandomPointsInClip(mc,300);
//var pts:Vector.<Point> = getGridPointsInClip(mc,100,4);
for(var i:int = 0 ; i < pts.length; i++) drawCircle(pts[i].x,pts[i].y,3,0x009900);

function getRandomPointsInClip(target:MovieClip,numPoints:int):Vector.<Point>{
    var points:Vector.<Point> = new Vector.<Point>(numPoints,true);
    var width:Number = target.width,height:Number = target.height;
    for(var i:int =  0; i < numPoints ; i++){
        var point:Point = new Point(target.x+Math.random() * width,target.y+Math.random() * height);
        if(target.hitTestPoint(point.x,point.y,true)) points[i] = point;//is the random coord inside ?
        else i = i-1;//nope, go back one step - > retry above until it is inside
    }
    return points;
}
function getGridPointsInClip(target:MovieClip,res:int,offset:Number = 3):Vector.<Point>{
    var points:Vector.<Point> = new Vector.<Point>();
    var x:int,y:int,alpha:int,w:int = int(target.width),h:int = int(target.height);
    var bmd:BitmapData = new BitmapData(w,h,true,0x00FFFFFF);bmd.draw(target);
    var pixels:Vector.<uint> = bmd.getVector(bmd.rect),numPixels:int = w*h;
    for(var i:int = 0; i < numPixels; i+=res) {
        x = i%bmd.width;
        y = int(i/bmd.width);
        alpha = pixels[i] >>> 24;
        if(alpha > 0) points.push(new Point(x+random(-offset,offset),y+random(-offset,offset)));
    }
    return points;
}
function random(from:Number,to:Number):Number {
    if (from >= to) return from;
    var diff:Number = to - from;
    return (Math.random()*diff) + from;
}
function drawCircle(x:Number,y:Number,radius:Number,color:uint):void{
    graphics.lineStyle(1,color);
    graphics.drawCircle(x-radius,y-radius,radius);
}

HTH