Random Points In N-polygon
What inPolygon() does is that divide n-polygon into n-3 triangles and pick one of them(by putting weight according to each triangle's area), finally calls inTriangle() with that triangle.
/**
* Copyright codeonwort ( http://wonderfl.net/user/codeonwort )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/ejiM
*/
// forked from codeonwort's Random Points In Triangle
package {
import flash.events.MouseEvent
import flash.display.Graphics
import flash.display.Sprite
import flash.geom.Point
public class FlashTest extends Sprite {
private var a:Point, b:Point, c:Point, d:Point
private var vertices:Vector.<Point> = new <Point>[]
public function FlashTest() {
point(60, 50)
point(30, 250)
point(170, 450)
point(360, 430)
point(440, 280)
point(400, 100)
function point(px:Number, py:Number):void { vertices.push(new Point(px, py)) }
draw(graphics)
stage.addEventListener("mouseDown", redraw)
}
private function redraw(e:MouseEvent):void {
graphics.clear()
draw(graphics)
}
private function draw(g:Graphics):void {
var p:Point
g.lineStyle(1, 0x000000, 1)
g.moveTo(vertices[0].x, vertices[0].y)
for(var k:int=1 ; k<vertices.length ; k++) g.lineTo(vertices[k].x, vertices[k].y)
g.lineTo(vertices[0].x, vertices[0].y)
g.lineStyle()
for(var i:int=0 ; i<1500 ; i++){
p = inPolygon(vertices)
g.beginFill(0xff0000, 1)
g.drawCircle(p.x, p.y, 1)
g.endFill()
}
}
}
}
import flash.geom.Point
// ps.length >= 3
function inPolygon(ps:Vector.<Point>):Point {
var a:Point, b:Point, c:Point = ps[0]
var areas:Vector.<Number> = new Vector.<Number>(ps.length-2, true)
var areasTotal:Number = 0
var j:int = 1
for(var i:int=0 ; i<ps.length-2 ; i++){
a = ps[j]
j++
b = ps[j]
areas[i] = Math.abs((a.x-b.x)*(c.y-b.y) - (c.x-b.x)*(a.y-b.y)) // * 0.5 is not needed
areasTotal += areas[i]
}
for(i=0 ; i<areas.length ; i++) areas[i] /= areasTotal
for(i=1 ; i<areas.length ; i++) areas[i] += areas[i-1]
var r:Number = Math.random()
for(i=areas.length-1 ; i>0 ; i--) if(areas[i] >= r && r >= areas[i-1]) break
return inTriangle(ps[rotate(i+1)], ps[rotate(i+2)], ps[0])
function rotate(n:int):int { return n % ps.length }
}
function inTriangle(p0:Point, p1:Point, p2:Point):Point {
var p3:Point = p0.add(p2.subtract(p1))
var v:Point = p0.subtract(p1), w:Point = p2.subtract(p1)
var p:Number = Math.random(), q:Number = Math.random()
var R:Point = new Point
R.x = p1.x + v.x * p + w.x * q
R.y = p1.y + v.y * p + w.y * q
var a:Number = p2.y - p0.y
var b:Number = p0.x - p2.x
var c:Number = -(p0.y * b + p0.x * a)
if(sign(a*p1.x + b*p1.y + c) != sign(a*R.x + b*R.y + c)){
return inTriangle(p0, p1, p2)
}
return R
}
function sign(n:Number):int { return n > 0 ? 1 : n < 0 ? -1 : 0 }