Polygoner

/*---------------------------------------
make random points on a canvas: makeNewSet()
Producing polygon with no linecrossing: arrangePolygon()
Producing conveks polygon: produceHull()
Testing inside in both cases: Inside()
Calculation area as precentage of complete frame: Area()
Sedgewicks algoritms
bs 2014
-----------------------------------------*/
// the device content in the canvas
var dc=null;
// dimensions of the area we use (preferable whole canvas)
// see init() at bottom of file;
var W=0;
var H=0;
// set up limits
var radius=8;
var maxcount=100;
// actual points generated
var count=0; 
// actual points describing the hull (convex polygon)
var hullcount=0;
var HullIsSet=false;
var Arranged=false;
// global in inside test
var ps=null;
// coordinates for polygon
var x;
var y;
// coordinates for hit tests
var hitx=null;
var hity=null;
// to hold a point, only used in insidetest
function Point(x,y){
    this.x=x;
    this.y=y;
}
////// set up canvas and make a dataset /////
function init(cid,w,h)
{
    var canvas = document.getElementById(cid);
    if (canvas.getContext){
        W=w;
        H=h;
        dc = canvas.getContext('2d');
        makeNewSet();
   } 
   else 
        alert('cannot do canvas');
}
//// paint what ever is to be painted /////
function paint()
{
   if(dc==null){
      console.log("no dc");
      return;
   }
   var lim;
   dc.fillStyle = "rgb(255,255,255)";
   dc.fillRect(0,0,W,H);
   // points
   for(var ix=0;ix < count;ix++){
      dc.beginPath();
      dc.fillStyle="rgb(0,0,0)";
      dc.arc(x[ix],y[ix],radius/2,0,2*Math.PI,false);
      dc.fill();
   }
   // hull only or all
   var lim=count;
   if(HullIsSet)
      lim=hullcount;
   dc.strokeStyle="rgb(100,100,100)";
   dc.moveTo(x[0],y[0])
   for(var ix=0;ix < lim;ix++)
      dc.lineTo(x[ix],y[ix]);
   // close it
   dc.lineTo(x[0],y[0]);
   dc.stroke();
   
   // mark inside/outside of testpoints
   if((HullIsSet ||Arranged) && (hitx !=null)&&(hitx.length>0) )
   {
        for(var ix=0;ix < hitx.length;ix++){// a point is set
            dc.beginPath();
            if(Inside(new Point(hitx[ix],hity[ix]),lim))
                dc.fillStyle="rgb(0,200,0)";
            else
                dc.fillStyle="rgb(200,0,0)";
            dc.arc(hitx[ix],hity[ix],radius/4,0,2*Math.PI,false);
            dc.fill();
        }
    }
}
  
////////  make a new set of points ////////////
function makeNewSet()
{
    // randomize the number
    count=getRandom(5,maxcount);
    x=new Array();
    y=new Array();
    for(var ix=0;ix < count;ix++)
    {
        // random integer coordinates
        x[ix]=getRandom(radius,W-2*radius);
        y[ix]=getRandom(radius,H-2*radius);
    }
    HullIsSet=false;
    Arranged=false;
    paint();
}
///////// make hitpoints for inside test ////
function makeHitPoints(n){
    if(hitx==null){
        hitx=new Array();
        hity=new Array();
        for(var ix=0;ix < n;ix++)
        {
            // random floats in coordinate range
            hitx[ix]=1.0*getRandom(radius,W-2*radius)+1/Math.random();
            hity[ix]=1.0*getRandom(radius,H-2*radius)+1/Math.random();
        }
    }
    else{
     hitx=null;
     hity=null;
    }
    paint();
}

///////// make random integer /////
function getRandom(min,max){
    return Math.floor((Math.random() * max) + min); 
}

/////////// helper for rough angle-equiv.  //////////////
function theta(x1,y1,x2,y2)
{
        // calculates a pseudo angle for the line p1->p2
        // according to Sedgewick
        var t;
        var dx=x2-x1; var ax=Math.abs(dx);
        var dy=y2-y1; var ay=Math.abs(dy);
        if((dx==0)&&(dy==0))
            t=0.0;
        else
            t=(1.0*dy)/(1.0*(ax+ay));
        if(dx<0)
            t=2.0-t;
        else 
            if(dy<0)
                t=4.0+t;
        return t*90.0;
}
//////  swap coordinates //////////////////
function swap(ix1,ix2){
    var tmpx=x[ix1];  var tmpy=y[ix1]; 
    x[ix1]=x[ix2]; y[ix1]=y[ix2];
    x[ix2]=tmpx; y[ix2]=tmpy;
}
//////// make a convex hull ///////////////////
function makeHull()
{
    // reorganize the points in p such
    // that the first ones are the convex hull
    // according to Sedgewick
    if(count<=3)
        return;
    //int ix,minix,M,tmpx,tmpy;
    //float minangle,v;
    // find a place to start: the lowest y-value
    // which is necessarily a part of the convex hull border
    var minix=0;
    for(var ix=1;ix<count;ix++)
        if(y[ix] < y[minix])
            minix=ix;
    // close the curve
    // add sentinel
    x[count]=x[minix];
    y[count]=y[minix];
    var minangle=0.0;
    var M=-1;        // upper index for hullnodes
    do
    {
        M+=1;
        // swap elements at M and minix
        swap(M,minix);
        minix=count;
        var v=minangle; 
        // start hi
        minangle=360.1;
        for(var ix=M+1;ix < count+1;ix++)
        {
            var teta=theta(x[M],y[M],x[ix],y[ix]);
            if((teta > v) && (teta < minangle))
            {
                minix=ix;
                minangle=teta;
             }
         }
    } while(minix != count);

    hullcount=M+1;
    HullIsSet=true;
    Arranged=false;
    paint();
}
//////////// arrange polygon without crossings ////////
function arrangePolygon()
{
    // reorganize the points in x,y such
    // that they constitute a polygon with 
    // non-crossing edges
    if(count<=3)
        return;
    //int ix,minix,M,tmpx,tmpy;
    var minangle;
    // find an anchor: the lowest y-value
    var minix=0;
    for(ix=1;ix<count;ix++)
        if(y[ix] < y[minix])
            minix=ix;
    // put the anchor as point 0
    swap(0,minix);
   
    // make a simple selectsort for 
    // the rest of the swarm based on
    // quasi angles with startpoint
    for(M=1;M<count-1;M++)
    {
        minix=M;
        minangle=theta(x[0],y[0],x[M],y[M]);
        for(ix=M+1;ix<count;ix++)
        {
            if(minangle > theta(x[0],y[0],x[ix],y[ix]))
            {
                minangle=theta(x[0],y[0],x[ix],y[ix]);
                minix=ix;
            }
        }
        swap(minix,M);
    }
    HullIsSet=false;
    Arranged=true;
    paint();
}
/////// calculate area ///////////////////////
function Area()
{
    // calculates the area of the polygon as 
    // percentage of available space
    if(count<3)
        return 0.0;
    // assume y=0 is lower than any point in pol
    // close the polygon temporarily
    // x[count]=x[0];y[count]=y[0];// sentinel
    var a=0.0;
    // add or subtract a rectangle and a triangle
    var lim;
    if(!HullIsSet)
        lim=count;
    else
        lim=hullcount;
    for(var ix=0;ix<lim;ix++)
    {
        // close the path
        if(ix==lim-1)
            a+=(x[0]-x[ix])*
                (Math.min(y[0],y[ix])
                +0.5*Math.abs((y[0]-y[ix])));
        else
            a+=(x[ix+1]-x[ix])*
                (Math.min(y[ix+1],y[ix])
                +0.5*Math.abs((y[ix+1]-y[ix])));
    }
    return Math.abs(a)*100.0/(1.0*(W*H));
}

//////// intersection between lines ///////////////
function Intersection(p1,p2,p3,p4,ps)
{
  // finds the intersecton between lines p1-p2 and p3-p4
  // return TRUE if intersection, FALSE else
  // result in ps, if intersection
  // use parametric equations for the lines
    
  var dx1=1.0*(p2.x-p1.x);
  var dx2=1.0*(p4.x-p3.x);
  var dy1=1.0*(p2.y-p1.y);
  var dy2=1.0*(p4.y-p3.y);
  var n=1.0*(dx2*dy1-dy2*dx1);
  if(n==0) return false;
  var s=1.0*(dx1*(p3.y-p1.y)-dy1*(p3.x-p1.x))/(1.0*n);
  if ((s<0.0)||(s>1.0)) return false;
  var t=1.0*(dy2*(p1.x-p3.x)-dx2*(p1.y-p3.y))/(1.0*n);
  if((t<0.0)||(t>1.0)) return false;
  ps.x=(dx1*t+p1.x);
  ps.y=(dy1*t+p1.y);
  return true;
}
////// testing inside point in polygon //////////////
function Inside(p, npnts)
{
  // Have we hit the polygon described int arrays x,y (npnts) ?
  if(npnts<3)
     return false;
  // Count intersections to the left of p
  // odd is hit, even is miss
  var p1=new Point(-100000,p.y);
  var p2=new Point(100000,p.y);
  var isInside=false;
  for(var pix=0;pix< npnts;pix++)
  {
     var p3= new Point(x[pix],y[pix]);
     var p4= new Point(x[pix+1],y[pix+1]);
        if(pix==npnts-1)
            p4=new Point(x[0],y[0]);
        
        ps= new Point(0,0);
     if(Intersection(p1,p2,p3,p4,ps))
        if (ps.x < p.x ) 
                isInside=!isInside;
  }
  return isInside;
}
/////  where it all starts //////
init('poly',300,300);